lshaz: a possibly useful static optimization analysis tool?

[clin1234]

I’ve come across this tool: GitHub - abokhalill/lshaz: Find the microarchitectural performance bugs hiding in your C++ code · GitHub

It claims to detect latency hazards at compile-time: struct layouts that span cache lines, atomics that trigger cross-core invalidation storms, heap allocations in hot loops, virtual dispatch that defeats branch prediction, etc.

Granted, it seems oriented towards x64, but it claims to also support arm64. In addition, it has GH workflow files to run this tool on PRs.

[lhecker]

It is fairly rare that software needs fixes to such low-level performance issues (cache layout, etc.). I found that almost all of the time when people were investigating perf issues this way, they failed to make major improvements. Those instead came from actually rewriting the bad code from scratch. But that takes a lot of effort, so people rarely try, and what could've been a 10x improvement ends up being a 10% micro-optimization.

I say this, because Windows Terminal is one such case. Rewriting the text buffer and VT parser would yield a ~10x perf improvement according to my investigation. I do not believe that this can be achieved any other way.

[lhecker]

If we look at the fundamental architecture of a terminal it is:
Client application --> Pipe --> Terminal VT Parser --> Text Buffer --> (periodically:) Text Renderer

As is almost always the case we have severe deficiencies in every single one of these steps

• The "Pipe" is a LPC pipe (called condrv; a NT kernel component), which only supports fully synchronous writes: A client only finishes a write() when the terminal has read it. If it was overlapped/async, the client could prepare the next write while the terminal concurrently reads it. (This issue can only be fixed by Microsoft employees while all of the ones after this can be fixed in this repository, albeit with great effort only.)
• The VT parser is currently of the push architecture using virtual dispatch which is naturally slow. It should be an incremental pull parser with static dispatch. This would permit for adding optimized batch processing for common VT sequences, such as SGR.
• The text buffer is a simple UTF16 line buffer with separate run-length compressed metadata. It should be a single UTF8 ring buffer with metadata embedded in between runs of text as byte blobs. (I.e. it should look like a ring buffer of text with VT sequences, where the VT sequences are encoded in a machine-readable byte format.) This would permit for extremely fast dumping of raw text (simple memcpy) and VT sequences (no run-length encoding needed).
• The text renderer currently locks the text buffer mutex for the entire duration of text analysis (expensive). It should instead create a snapshot of the text buffer and unlock the mutex as quickly as possible.

Just fixing the last 3 should yield something in the magnitude of a 10x improvement for large writes (e.g. cat; towards 4GB/s). But fixing the first one would be the nicest as it would reduce the latency of small writes which is much more common in practice (likely to be >100x, if done right).

[clin1234]

For the "Pipe" stage, do you think there are equally-performant or better substitutes for an async LPC pipe that outside contributors to this repo can provide?

For the text buffer idea, could you elaborate on how embedding VT sequences and other metadata embedded in a UTF-8 ring buffer would allow simple memcpy of raw text? Additionally, do you think using SIMD intrinics would help at all here?

For the VT parser, forgive my naiveness, but would an approach a la tree-sitter even be viable?

For the text renderer, what are the steps of text analysis, and what critical sections are held by the text buffer mutex? Additionally, should the renderer, in your opinion, snapshot just differences between each "frame," or the entire buffer?

[lhecker]

For the "Pipe" stage, do you think there are equally-performant or better substitutes for an async LPC pipe that outside contributors to this repo can provide?

No. It is tightly integrated into condrv (a kernel component, depending on lots of internal code) and conclnt (a component of kernelbase.dll, also lots of internal code).

For the text buffer idea, could you elaborate on how embedding VT sequences and other metadata embedded in a UTF-8 ring buffer would allow simple memcpy of raw text?

A terminal is basically a 2D grid of "cells", right? So, a basic object-oriented terminal would use a 2D matrix of "cells", like std::vector<std::vector<Cell>>, where Cell is a struct that stores 1 character and its corresponding metadata (color, underline, etc.). This is the worst possible solution and many terminals do this, resulting in their poor performance. To store incoming text, you now need to split it up into cells and fill each Cell struct one by one.

The next best solution is to split this into Row structs: std::vector<Row> where each Row contains a std::string of text and a std::vector<Metadata> separately. Now you can copy incoming strings of text into each row's std::string batchwise. If you got 15 characters with the same metadata, you only need to do 1 copy for the text and 1 "memset" to fill the corresponding metadata.

The two designs above are often called Array of Structs (AoS; the former) and Struct of Arrays (SoA; the latter). SoA is not always better, but if it can be used, it can bring significant advantages. See: https://en.wikipedia.org/wiki/AoS_and_SoA

However, neither is a good solution, because you're still split into rows! The logical conclusion is that you just have 1 flat ring buffer of text. You don't need to split into rows of text anymore; you just store the text as-is. Only during rendering you'll try to figure out where you have to break the text into lines. If you have 100000 characters of text coming in, it's not hundreds of copies (one per row) but still just one. The problem is that you need some way to store the metadata. If you stored it in a separate metadata buffer, you'd destroy your data locality (related to the tool you mentioned). So, you just store it in the same buffer you store your text in, exactly how VT sequences work. To make parsing metadata faster, you'd store in some binary format instead, however.

Additionally, do you think using SIMD intrinics would help at all here?

For VT parsing, yes. In fact, we already use SIMD for parsing. But for text storage you don't need any, because you can use those metadata blobs to store arbitrary information. You can for instance store information to make buffer navigation faster. The sky is the limit.

For the VT parser, forgive my naiveness, but would an approach a la tree-sitter even be viable?

tree-sitter is something completely different. VT parsing is extremely simple. You'd write a tokenizer like this: https://github.com/microsoft/edit/blob/fa709bade0c51430db208998a770b8b8c55d9007/crates/edit/src/vt.rs#L150
...and then a parser like this: https://github.com/microsoft/edit/blob/fa709bade0c51430db208998a770b8b8c55d9007/crates/edit/src/input.rs#L308

For the text renderer, what are the steps of text analysis, ...

That's too complex to explain here. The logic is somewhat complex, and you can read AtlasEngine.cpp for that. The tl;dr is that it needs to perform something called "text shaping" which is expensive.

...and what critical sections are held by the text buffer mutex?

We only have a coarse mutex at the moment that locks the entire terminal. That doesn't need to be changed because the fundamental issue is not the granularity of mutexes but for how long they're held. The renderer should not hold it during the entire text shaping process.

Additionally, should the renderer, in your opinion, snapshot just differences between each "frame," or the entire buffer?

It should just snapshot the entire viewport on each frame. Making these algorithms "smart" by doing differential snapshots is the wrong way to treat modern CPUs. It is likely faster to emit a single memcpy for the entire viewport than it is to calculate the differences between frames. You can see this by calculating the latency and throughput of modern L3 cache and DDR4 RAM respectively. The overhead for copying 500kB is tiny and negligible and requires just one round-trip.

But I suspect that both approaches are viable and we should simply pick whatever is easier. If done well, both approaches will be extremely fast.

[clin1234]

Is "text shaping" related to an OpenType feature related to glyphs or kerning?

[lhecker]

While I'm happy to answer your complex questions, that is a question you can trivially Google. It even has a brief Wikipedia article.