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

performance significantly for very wide lines.

5 files changed, 150 insertions, 45 deletions

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();