Feature [feature-requests:#1427] Add multithreaded layout which improves

performance significantly for very wide lines.

13 files changed, 194 insertions, 45 deletions

diff --git a/call/ScintillaCall.cxx b/call/ScintillaCall.cxx
index 4fe782af5..53b4e0cf7 100644
--- a/call/ScintillaCall.cxx
+++ b/call/ScintillaCall.cxx
@@ -2568,6 +2568,14 @@ int ScintillaCall::PositionCache() {
 	return static_cast<int>(Call(Message::GetPositionCache));
 }
 
+void ScintillaCall::SetLayoutThreads(int threads) {
+	Call(Message::SetLayoutThreads, threads);
+}
+
+int ScintillaCall::LayoutThreads() {
+	return static_cast<int>(Call(Message::GetLayoutThreads));
+}
+
 void ScintillaCall::CopyAllowLine() {
 	Call(Message::CopyAllowLine);
 }
diff --git a/doc/ScintillaDoc.html b/doc/ScintillaDoc.html
index 58e8da944..932d26de8 100644
--- a/doc/ScintillaDoc.html
+++ b/doc/ScintillaDoc.html
@@ -7449,6 +7449,8 @@ sptr_t CallScintilla(unsigned int iMessage, uptr_t wParam, sptr_t lParam){
      <a class="message" href="#SCI_GETLAYOUTCACHE">SCI_GETLAYOUTCACHE &rarr; int</a><br />
      <a class="message" href="#SCI_SETPOSITIONCACHE">SCI_SETPOSITIONCACHE(int size)</a><br />
      <a class="message" href="#SCI_GETPOSITIONCACHE">SCI_GETPOSITIONCACHE &rarr; int</a><br />
+     <a class="message" href="#SCI_SETLAYOUTTHREADS">SCI_SETLAYOUTTHREADS(int threads)</a><br />
+     <a class="message" href="#SCI_GETLAYOUTTHREADS">SCI_GETLAYOUTTHREADS &rarr; int</a><br />
      <a class="message" href="#SCI_LINESSPLIT">SCI_LINESSPLIT(int pixelWidth)</a><br />
      <a class="message" href="#SCI_LINESJOIN">SCI_LINESJOIN</a><br />
      <a class="message" href="#SCI_WRAPCOUNT">SCI_WRAPCOUNT(line docLine) &rarr; line</a><br />
@@ -7687,6 +7689,21 @@ sptr_t CallScintilla(unsigned int iMessage, uptr_t wParam, sptr_t lParam){
      so that their layout can be determined more quickly if the run recurs.
      The size in entries of this cache can be set with <code>SCI_SETPOSITIONCACHE</code>.</p>
 
+    <p><b id="SCI_SETLAYOUTTHREADS">SCI_SETLAYOUTTHREADS(int threads)</b><br />
+     <b id="SCI_GETLAYOUTTHREADS">SCI_GETLAYOUTTHREADS &rarr; int</b><br />
+     The time taken to measure text runs on wide lines can be improved by performing the task
+     concurrently on multiple threads when
+     <a class="seealso" href="#SCI_SUPPORTSFEATURE">SC_SUPPORTS_THREAD_SAFE_MEASURE_WIDTHS</a>
+     is available.
+     This can be a dramatic improvement - a 4 core processor is often able to reduce text layout time to just over one
+     quarter of the single-threaded time.</p>
+     <p>The default is to use just the main thread but applications may call <code>SCI_SETLAYOUTTHREADS</code>
+     to specify the maximum number of threads to use.
+     The number of threads is limited to the hardware concurrency of the system -
+     for a 4 core processor with hyper-threading that would be 8.
+     If an application just wants maximum concurrency then call with a large number
+     <code>SCI_SETLAYOUTTHREADS(1000)</code> and that will be reduced to a reasonable value.</p>
+
     <p><b id="SCI_LINESSPLIT">SCI_LINESSPLIT(int pixelWidth)</b><br />
      Split a range of lines indicated by the target into lines that are at most pixelWidth wide.
      Splitting occurs on word boundaries wherever possible in a similar manner to line wrapping.
diff --git a/doc/ScintillaHistory.html b/doc/ScintillaHistory.html
index 9809d7b87..28c02b434 100644
--- a/doc/ScintillaHistory.html
+++ b/doc/ScintillaHistory.html
@@ -580,6 +580,10 @@
 	Released 7 December 2021.
 	</li>
 	<li>
+	Added multithreaded layout which improves performance significantly for very wide lines.
+	<a href="https://sourceforge.net/p/scintilla/feature-requests/1427/">Feature #1427</a>.
+	</li>
+	<li>
 	Made compatible with Qt 6.
 	</li>
 	<li>
diff --git a/include/Scintilla.h b/include/Scintilla.h
index 7ab0e3560..fbd2bf3f3 100644
--- a/include/Scintilla.h
+++ b/include/Scintilla.h
@@ -924,6 +924,8 @@ typedef sptr_t (*SciFnDirectStatus)(sptr_t ptr, unsigned int iMessage, uptr_t wP
 #define SCI_INDICATOREND 2509
 #define SCI_SETPOSITIONCACHE 2514
 #define SCI_GETPOSITIONCACHE 2515
+#define SCI_SETLAYOUTTHREADS 2775
+#define SCI_GETLAYOUTTHREADS 2776
 #define SCI_COPYALLOWLINE 2519
 #define SCI_GETCHARACTERPOINTER 2520
 #define SCI_GETRANGEPOINTER 2643
diff --git a/include/Scintilla.iface b/include/Scintilla.iface
index a98a310ab..88e375e74 100644
--- a/include/Scintilla.iface
+++ b/include/Scintilla.iface
@@ -2535,6 +2535,12 @@ set void SetPositionCache=2514(int size,)
 # How many entries are allocated to the position cache?
 get int GetPositionCache=2515(,)
 
+# Set maximum number of threads used for layout
+set void SetLayoutThreads=2775(int threads,)
+
+# Get maximum number of threads used for layout
+get int GetLayoutThreads=2776(,)
+
 # Copy the selection, if selection empty copy the line with the caret
 fun void CopyAllowLine=2519(,)
 
diff --git a/include/ScintillaCall.h b/include/ScintillaCall.h
index d16f2aff0..272345489 100644
--- a/include/ScintillaCall.h
+++ b/include/ScintillaCall.h
@@ -682,6 +682,8 @@ public:
 	Position IndicatorEnd(int indicator, Position pos);
 	void SetPositionCache(int size);
 	int PositionCache();
+	void SetLayoutThreads(int threads);
+	int LayoutThreads();
 	void CopyAllowLine();
 	void *CharacterPointer();
 	void *RangePointer(Position start, Position lengthRange);
diff --git a/include/ScintillaMessages.h b/include/ScintillaMessages.h
index 95ed09530..33a875f0a 100644
--- a/include/ScintillaMessages.h
+++ b/include/ScintillaMessages.h
@@ -607,6 +607,8 @@ enum class Message {
 	IndicatorEnd = 2509,
 	SetPositionCache = 2514,
 	GetPositionCache = 2515,
+	SetLayoutThreads = 2775,
+	GetLayoutThreads = 2776,
 	CopyAllowLine = 2519,
 	GetCharacterPointer = 2520,
 	GetRangePointer = 2643,
diff --git a/scripts/HeaderOrder.txt b/scripts/HeaderOrder.txt
index 33beb4d7e..9001736ed 100644
--- a/scripts/HeaderOrder.txt
+++ b/scripts/HeaderOrder.txt
@@ -57,7 +57,10 @@
 #include <sstream>
 #include <fstream>
 #include <iomanip>
+#include <atomic>
 #include <mutex>
+#include <thread>
+#include <future>
 
 // GTK headers
 #include <glib.h>
diff --git a/src/EditView.cxx b/src/EditView.cxx
index ca78f9bad..9f77b33f0 100644
--- a/src/EditView.cxx
+++ b/src/EditView.cxx
@@ -25,6 +25,9 @@
 #include <iterator>
 #include <memory>
 #include <chrono>
+#include <atomic>
+#include <thread>
+#include <future>
 
 #include "ScintillaTypes.h"
 #include "ScintillaMessages.h"
@@ -193,6 +196,7 @@ EditView::EditView() {
 	llc.SetLevel(LineCache::Caret);
 	posCache = CreatePositionCache();
 	posCache->SetSize(0x400);
+	maxLayoutThreads = 1;
 	tabArrowHeight = 4;
 	customDrawTabArrow = nullptr;
 	customDrawWrapMarker = nullptr;
@@ -218,6 +222,14 @@ bool EditView::LinesOverlap() const noexcept {
 	return phasesDraw == PhasesDraw::Multiple;
 }
 
+void EditView::SetLayoutThreads(unsigned int threads) noexcept {
+	maxLayoutThreads = std::clamp(threads, 1U, std::thread::hardware_concurrency());
+}
+
+unsigned int EditView::GetLayoutThreads() const noexcept {
+	return maxLayoutThreads;
+}
+
 void EditView::ClearAllTabstops() noexcept {
 	ldTabstops.reset();
 }
@@ -373,6 +385,61 @@ bool ViewIsASCII(std::string_view text) {
 	return std::all_of(text.cbegin(), text.cend(), IsASCII);
 }
 
+void LayoutSegments(IPositionCache *pCache,
+	Surface *surface,
+	const ViewStyle &vstyle,
+	LineLayout *ll, 
+	const std::vector<TextSegment> &segments,
+	std::atomic<uint32_t> &nextIndex,
+	const bool textUnicode,
+	const bool multiThreaded) {
+	while (true) {
+		const uint32_t i = nextIndex.fetch_add(1, std::memory_order_acq_rel);
+		if (i >= segments.size()) {
+			break;
+		}
+		const TextSegment &ts = segments[i];
+		if (vstyle.styles[ll->styles[ts.start]].visible) {
+			if (ts.representation) {
+				XYPOSITION representationWidth = vstyle.controlCharWidth;
+				if (ll->chars[ts.start] == '\t') {
+					// Tab is a special case of representation, taking a variable amount of space
+					// which will be filled in later.
+					representationWidth = 0;
+				} else {
+					if (representationWidth <= 0.0) {
+						assert(ts.representation->stringRep.length() <= Representation::maxLength);
+						XYPOSITION positionsRepr[Representation::maxLength + 1];
+						// ts.representation->stringRep is UTF-8 which only matches cache if document is UTF-8
+						// or it only contains ASCII which is a subset of all currently supported encodings.
+						if (textUnicode || ViewIsASCII(ts.representation->stringRep)) {
+							pCache->MeasureWidths(surface, vstyle, StyleControlChar, ts.representation->stringRep,
+								positionsRepr, multiThreaded);
+						} else {
+							surface->MeasureWidthsUTF8(vstyle.styles[StyleControlChar].font.get(), ts.representation->stringRep, positionsRepr);
+						}
+						representationWidth = positionsRepr[ts.representation->stringRep.length() - 1];
+						if (FlagSet(ts.representation->appearance, RepresentationAppearance::Blob)) {
+							representationWidth += vstyle.ctrlCharPadding;
+						}
+					}
+				}
+				for (int ii = 0; ii < ts.length; ii++) {
+					ll->positions[ts.start + 1 + ii] = representationWidth;
+				}
+			} else {
+				if ((ts.length == 1) && (' ' == ll->chars[ts.start])) {
+					// Over half the segments are single characters and of these about half are space characters.
+					ll->positions[ts.start + 1] = vstyle.styles[ll->styles[ts.start]].spaceWidth;
+				} else {
+					pCache->MeasureWidths(surface, vstyle, ll->styles[ts.start],
+						std::string_view(&ll->chars[ts.start], ts.length), &ll->positions[ts.start + 1], multiThreaded);
+				}
+			}
+		}
+	}
+}
+
 }
 
 /**
@@ -383,7 +450,6 @@ bool ViewIsASCII(std::string_view text) {
 void EditView::LayoutLine(const EditModel &model, Surface *surface, const ViewStyle &vstyle, LineLayout *ll, int width) {
 	if (!ll)
 		return;
-
 	const Sci::Line line = ll->LineNumber();
 	PLATFORM_ASSERT(line < model.pdoc->LinesTotal());
 	PLATFORM_ASSERT(ll->chars);
@@ -462,58 +528,74 @@ void EditView::LayoutLine(const EditModel &model, Surface *surface, const ViewSt
 
 		// Layout the line, determining the position of each character,
 		// with an extra element at the end for the end of the line.
-		std::fill(&ll->positions[0], &ll->positions[lineLength + 1], 0.0);
+		ll->positions[0] = 0;
 		bool lastSegItalics = false;
 
+		std::vector<TextSegment> segments;
 		BreakFinder bfLayout(ll, nullptr, Range(0, numCharsInLine), posLineStart, 0, BreakFinder::BreakFor::Text, model.pdoc, &model.reprs, nullptr);
 		while (bfLayout.More()) {
+			segments.push_back(bfLayout.Next());
+		}
 
-			const TextSegment ts = bfLayout.Next();
+		std::fill(&ll->positions[0], &ll->positions[numCharsInLine], 0.0f);
 
-			if (vstyle.styles[ll->styles[ts.start]].visible) {
-				if (ts.representation) {
-					XYPOSITION representationWidth = vstyle.controlCharWidth;
-					if (ll->chars[ts.start] == '\t') {
-						// Tab is a special case of representation, taking a variable amount of space
-						const XYPOSITION x = ll->positions[ts.start];
-						representationWidth = NextTabstopPos(line, x, vstyle.tabWidth) - ll->positions[ts.start];
-					} else {
-						if (representationWidth <= 0.0) {
-							assert(ts.representation->stringRep.length() <= Representation::maxLength);
-							XYPOSITION positionsRepr[Representation::maxLength+1];
-							// ts.representation->stringRep is UTF-8 which only matches cache if document is UTF-8
-							// or it only contains ASCII which is a subset of all currently supported encodings.
-							if ((CpUtf8 == model.pdoc->dbcsCodePage) || ViewIsASCII(ts.representation->stringRep)) {
-								posCache->MeasureWidths(surface, vstyle, StyleControlChar, ts.representation->stringRep,
-									positionsRepr);
-							} else {
-								surface->MeasureWidthsUTF8(vstyle.styles[StyleControlChar].font.get(), ts.representation->stringRep, positionsRepr);
-							}
-							representationWidth = positionsRepr[ts.representation->stringRep.length() - 1];
-							if (FlagSet(ts.representation->appearance, RepresentationAppearance::Blob)) {
-								representationWidth += vstyle.ctrlCharPadding;
-							}
-						}
-					}
-					for (int ii = 0; ii < ts.length; ii++)
-						ll->positions[ts.start + 1 + ii] = representationWidth;
-				} else {
-					if ((ts.length == 1) && (' ' == ll->chars[ts.start])) {
-						// Over half the segments are single characters and of these about half are space characters.
-						ll->positions[ts.start + 1] = vstyle.styles[ll->styles[ts.start]].spaceWidth;
-					} else {
-						posCache->MeasureWidths(surface, vstyle, ll->styles[ts.start],
-							std::string_view(&ll->chars[ts.start], ts.length), &ll->positions[ts.start + 1]);
-					}
-				}
-				lastSegItalics = (!ts.representation) && ((ll->chars[ts.end() - 1] != ' ') && vstyle.styles[ll->styles[ts.start]].italic);
+		if (!segments.empty()) {
+
+			const size_t threadsForLength = std::max(1, numCharsInLine / bytesPerLayoutThread);
+			size_t threads = std::min<size_t>({ segments.size(), threadsForLength, maxLayoutThreads });
+			if (!surface->SupportsFeature(Supports::ThreadSafeMeasureWidths)) {
+				threads = 1;
 			}
 
-			for (int posToIncrease = ts.start + 1; posToIncrease <= ts.end(); posToIncrease++) {
-				ll->positions[posToIncrease] += ll->positions[ts.start];
+			std::atomic<uint32_t> nextIndex = 0;
+
+			const bool textUnicode = CpUtf8 == model.pdoc->dbcsCodePage;
+			const bool multiThreaded = threads > 1;
+			IPositionCache *pCache = posCache.get();
+
+			// If only 1 thread needed then use the main thread, else spin up multiple
+			const std::launch policy = (multiThreaded) ? std::launch::async : std::launch::deferred;
+
+			std::vector<std::future<void>> futures;
+			for (size_t th = 0; th < threads; th++) {
+				// Find relative positions of everything except for tabs
+				std::future<void> fut = std::async(policy,
+					[pCache, surface, &vstyle, &ll, &segments, &nextIndex, textUnicode, multiThreaded]() {
+					LayoutSegments(pCache, surface, vstyle, ll, segments, nextIndex, textUnicode, multiThreaded);
+				});
+				futures.push_back(std::move(fut));
+			}
+			for (const std::future<void> &f : futures) {
+				f.wait();
 			}
 		}
 
+		// Accumulate absolute positions from relative positions within segments and expand tabs
+		XYPOSITION xPosition = 0.0;
+		size_t iByte = 0;
+		ll->positions[iByte++] = xPosition;
+		for (const TextSegment &ts : segments) {
+			if (vstyle.styles[ll->styles[ts.start]].visible &&
+				ts.representation &&
+				(ll->chars[ts.start] == '\t')) {
+				// Simple visible tab, go to next tab stop
+				const XYPOSITION startTab = ll->positions[ts.start];
+				const XYPOSITION nextTab = NextTabstopPos(line, startTab, vstyle.tabWidth);
+				xPosition += nextTab - startTab;
+			}
+			const XYPOSITION xBeginSegment = xPosition;
+			for (int i = 0; i < ts.length; i++) {
+				xPosition = ll->positions[iByte] + xBeginSegment;
+				ll->positions[iByte++] = xPosition;
+			}
+		}
+
+		if (!segments.empty()) {
+			// Not quite the same as before which would effectively ignore trailing invisible segments
+			const TextSegment &ts = segments.back();
+			lastSegItalics = (!ts.representation) && ((ll->chars[ts.end() - 1] != ' ') && vstyle.styles[ll->styles[ts.start]].italic);
+		}
+
 		// Small hack to make lines that end with italics not cut off the edge of the last character
 		if (lastSegItalics) {
 			ll->positions[numCharsInLine] += vstyle.lastSegItalicsOffset;
diff --git a/src/EditView.h b/src/EditView.h
index c9364ad30..199a174b9 100644
--- a/src/EditView.h
+++ b/src/EditView.h
@@ -83,6 +83,9 @@ public:
 	LineLayoutCache llc;
 	std::unique_ptr<IPositionCache> posCache;
 
+	unsigned int maxLayoutThreads;
+	static constexpr int bytesPerLayoutThread = 1000;
+
 	int tabArrowHeight; // draw arrow heads this many pixels above/below line midpoint
 	/** Some platforms, notably PLAT_CURSES, do not support Scintilla's native
 	 * DrawTabArrow function for drawing tab characters. Allow those platforms to
@@ -103,6 +106,9 @@ public:
 	bool SetPhasesDraw(int phases) noexcept;
 	bool LinesOverlap() const noexcept;
 
+	void SetLayoutThreads(unsigned int threads) noexcept;
+	unsigned int GetLayoutThreads() const noexcept;
+
 	void ClearAllTabstops() noexcept;
 	XYPOSITION NextTabstopPos(Sci::Line line, XYPOSITION x, XYPOSITION tabWidth) const noexcept;
 	bool ClearTabstops(Sci::Line line) noexcept;
diff --git a/src/Editor.cxx b/src/Editor.cxx
index 342e7de1c..ccf07b6a8 100644
--- a/src/Editor.cxx
+++ b/src/Editor.cxx
@@ -6813,6 +6813,13 @@ sptr_t Editor::WndProc(Message iMessage, uptr_t wParam, sptr_t lParam) {
 	case Message::GetPositionCache:
 		return view.posCache->GetSize();
 
+	case Message::SetLayoutThreads:
+		view.SetLayoutThreads(static_cast<unsigned int>(wParam));
+		break;
+
+	case Message::GetLayoutThreads:
+		return view.GetLayoutThreads();
+
 	case Message::SetScrollWidth:
 		PLATFORM_ASSERT(wParam > 0);
 		if ((wParam > 0) && (wParam != static_cast<unsigned int>(scrollWidth))) {
diff --git a/src/PositionCache.cxx b/src/PositionCache.cxx
index 4025ec651..23733c3a0 100644
--- a/src/PositionCache.cxx
+++ b/src/PositionCache.cxx
@@ -21,6 +21,7 @@
 #include <algorithm>
 #include <iterator>
 #include <memory>
+#include <mutex>
 
 #include "ScintillaTypes.h"
 #include "ScintillaMessages.h"
@@ -822,6 +823,7 @@ public:
 
 class PositionCache : public IPositionCache {
 	std::vector<PositionCacheEntry> pces;
+	std::mutex mutex;
 	uint16_t clock;
 	bool allClear;
 public:
@@ -837,7 +839,7 @@ public:
 	void SetSize(size_t size_) override;
 	size_t GetSize() const noexcept override;
 	void MeasureWidths(Surface *surface, const ViewStyle &vstyle, unsigned int styleNumber,
-		std::string_view sv, XYPOSITION *positions) override;
+		std::string_view sv, XYPOSITION *positions, bool needsLocking) override;
 };
 
 PositionCacheEntry::PositionCacheEntry() noexcept :
@@ -934,7 +936,7 @@ size_t PositionCache::GetSize() const noexcept {
 }
 
 void PositionCache::MeasureWidths(Surface *surface, const ViewStyle &vstyle, unsigned int styleNumber,
-	std::string_view sv, XYPOSITION *positions) {
+	std::string_view sv, XYPOSITION *positions, bool needsLocking) {
 	const Style &style = vstyle.styles[styleNumber];
 	if (style.monospaceASCII) {
 		if (AllGraphicASCII(sv)) {
@@ -954,6 +956,10 @@ void PositionCache::MeasureWidths(Surface *surface, const ViewStyle &vstyle, uns
 		// Two way associative: try two probe positions.
 		const size_t hashValue = PositionCacheEntry::Hash(styleNumber, sv);
 		probe = hashValue % pces.size();
+		std::unique_lock<std::mutex> guard(mutex, std::defer_lock);
+		if (needsLocking) {
+			guard.lock();
+		}
 		if (pces[probe].Retrieve(styleNumber, sv, positions)) {
 			return;
 		}
@@ -971,6 +977,10 @@ void PositionCache::MeasureWidths(Surface *surface, const ViewStyle &vstyle, uns
 	surface->MeasureWidths(fontStyle, sv, positions);
 	if (probe < pces.size()) {
 		// Store into cache
+		std::unique_lock<std::mutex> guard(mutex, std::defer_lock);
+		if (needsLocking) {
+			guard.lock();
+		}
 		clock++;
 		if (clock > 60000) {
 			// Since there are only 16 bits for the clock, wrap it round and
diff --git a/src/PositionCache.h b/src/PositionCache.h
index aeede7058..ad6caea78 100644
--- a/src/PositionCache.h
+++ b/src/PositionCache.h
@@ -253,7 +253,7 @@ public:
 	virtual void SetSize(size_t size_) = 0;
 	virtual size_t GetSize() const noexcept = 0;
 	virtual void MeasureWidths(Surface *surface, const ViewStyle &vstyle, unsigned int styleNumber,
-		std::string_view sv, XYPOSITION *positions) = 0;
+		std::string_view sv, XYPOSITION *positions, bool needsLocking) = 0;
 };
 
 std::unique_ptr<IPositionCache> CreatePositionCache();