Most of a scroll was spent on blank cells

The default tuios build runs its own pure Go terminal emulator, internal/vt, for every pane. It started as a fork of charmbracelet/x/vt. The other option is libghostty-vt behind a build tag, and nothing in this post applies to that backend. In September I did a performance pass over it: the parser, the print path and the scroll path. Five commits came out of it. One of them matters much more than the others, so most of this post is about that one.

The benchmark it moved is the most boring one in the package. BenchmarkEmulatorShortLineScroll makes a 207x55 emulator with 10,000 lines of scrollback and writes this, over and over:

tuiosflood\r\n

Ten characters and a newline. The screen is full, so every newline scrolls it: the top row goes into the scrollback and a fresh blank row appears at the bottom. That is what a shell does all day. It is ls, a build log, tail -f.

Where the time went

The profile of that benchmark said 72% of the time was the blank part of each row. Two functions:

• isBlankCell, 39%. Before a row goes into the scrollback, PushLine trims its trailing blanks, so the scrollback does not store 197 spaces after every short line. It found the end of the text by starting at column 206 and walking left until it met a non-blank cell. For tuiosflood that is 198 cells read to find one.
• blankRows, 33%. The screen scrolls by rotating its rows, so the row that left the top is reused as the new bottom row. It has to be blanked first, and blankRows wrote a blank into all 207 of its cells.

A cell here is a uv.Cell, 112 bytes with pointers in it. 207 of them is about 22 KB. So a ten-character line cost two walks over 22 KB of cells, one reading and one writing, and nearly all of it was over cells that were already blank.

A lever I had already written down

This was not a surprise, and that is the embarrassing part. In August I had looked at exactly this blanking loop. An earlier pass had tried replacing it with one bulk copy from a prototype row and reverted it, and I wanted a number instead of an inherited conclusion. So I wrote BenchmarkBlankFill. It said the plain loop that stores one blank per cell was already the fastest arrangement I could find:

The note I left in docs/perf.md ended with: the only lever left is moving fewer bytes, a smaller uv.Cell (an upstream type) or not blanking eagerly. Then I left it there for a month. The profile in September was the same conclusion from the other side. The loop was as fast as a loop can be. It just did not need to run over most of the row.

One int per row

The fix is small. The grid now keeps, for every row, an extent: a column past which every cell is a plain blank.

• A write raises it. SetCell raises it to the end of the cell it wrote, and handing out a row for arbitrary writes raises it to the full width.
• A full-width line shift, and the whole-screen rotation, carry each extent with its row.
• Blanking a whole row resets it to zero. Nothing else lowers it.

It is an upper bound, not the exact end of the text. Overwriting the last letter of a line with a space leaves the extent where it was. That is fine: the trim still checks the cells it reads, it just starts closer to them.

The two walks now start or stop at the extent. The blanking:

row := g.rows[i]
for x := range row[:g.ext[i]] {
    row[x] = uv.EmptyCell
}
g.ext[i] = 0

and the push into the scrollback:

n := min(ext, len(line))
for n > 0 && isBlankCell(&line[n-1]) {
    n--
}
sb.push(line[:n], len(line))

Try it. The row below is one line of the 207-column benchmark screen as it leaves the top. Type a line, or pick one, and press Enter to scroll it. The top strip is what the old code touched, the bottom one what it touches now.

The widget counts cells, not time. For tuiosflood it says 405 cells before and 11 after, but the scroll does other work that did not change: parsing the bytes, writing the ten letters, encoding them for the scrollback, rotating the rows. That is why the benchmark below got about 4.7 times faster and not 37.

The clock checkbox is the honest case. A prompt that draws something at the right edge raises that row's extent to the full width, and then the blanking costs what it always did. The extent does not make wide rows cheaper. It makes short rows cost what they hold.

The numbers

Everything that scrolls short lines moved with it:

All at p=0.002. No other vt benchmark moved. The cost is one int per row.

Measuring on a machine that would not sit still

The machine was shared with other agents the whole time. The load average sat between 13 and 18 on 11 cores, and wall time swung by as much as 100% between identical runs. A go test -bench number from that machine means nothing.

So nothing above is wall time. Each figure is process CPU time, user plus sys, per iteration. I built the test binary for the commit before and the commit after, ran each benchmark at a fixed iteration count (-test.benchtime Nx) on one CPU (-test.cpu 1), alternated the old and new binaries for six rounds each, and compared them with benchstat.

CPU time still counts the process start and the benchmark setup. That dilutes a change towards zero. It never makes one look bigger.

Before believing any of it I measured the noise floor: the base binary against a copy of itself, under the same alternation. All fifteen benchmarks came out as no change (~, p=0.37 to 1.00), geomean -1.0%, with confidence intervals from +/-4% to +/-43%. I only quote a result that clears that at p < 0.05. Allocation counts are exact, so they need none of this.

One thing this does not give you is a stable absolute number across comparisons. EmulatorWriteHeavyOutput/colored-log read 56.7 us after the plain scrollback change and 54.2 us before the ASCII run change, the very next commit, with nothing in between. BackendScroll is worse: 86.7 ms after the plain scrollback change and 71.3 ms before the extent one. The ASCII run commit sits between those, and its own comparison put BackendScroll at ~. That means its interval was too wide to say, not that it did not move. From two numbers in different pairs I cannot tell a change from a shift in load. Each before and after pair ran interleaved, so the pair is comparable. Two numbers from different pairs are not.

Keeping it right

Skipping work is a correctness claim. The extent is only safe if every path that writes a non-blank cell raises it. Miss one, and the scroll blanks too little of a row, so old text comes back, or leaves the end of a line out of the scrollback.

Two tests hold the invariant directly. The random grid test, which already drove the grid and ultraviolet's buffer side by side, now also checks the extents after every grid operation. A new test, TestGridExtentHoldsUnderGeneratedInput, runs the vtgen input generator through a whole emulator and checks the invariant on both screens after every step. The first one covers the grid's own methods. The second covers the writes that reach a row from outside the grid.

There is one of those that worried me. The commit just before this one made a run of ASCII store its cells straight into the row, without going through SetCell. That store has to raise the extent itself:

// Written behind the grid's back, so its extent is raised here
// (see grid.ext).
e.scr.buf.raiseExt(y, x+n)

While writing this post I deleted that line in a copy of the tree and ran the suite, to see what would notice. The conformance corpus passed. The tmux differential test passed, all 63 cases. That was not because the screen was right. None of their cases scrolls a row that the direct store wrote, so they never reached the bug.

Six tests failed:

• TestGridExtentHoldsUnderGeneratedInput, at seed 0, step 9: a cell holding e past its row's extent.
• TestScrollUpFillsScrollback: scrollback line 8 was "", want "line-08". The lines had left the screen and arrived in the scrollback empty.
• The test that scrollback storage is reused when the ring is full failed the same way.
• TestASCIIRunMatchesPerCharacterPath, because the run path and the per-character path now drew different screens.
• TestVTGen_Metamorphic, the split-equivalence test from the fuzzer post, reduced to two steps: 42 x characters and a full reset (ESC c). Fed in one piece, the reset cleared the screen. Split at a different boundary, an x survived it, because the reset stops clearing at the extent and the extent was stale.
• FuzzEmulatorWriteChunked, on its seed corpus.

I also removed the rotation of the extents in the whole-screen scroll. That one is loud: blankRows panics with a slice out of range, and one of the 63 tmux cases disagrees.

The quiet failure is the one I care about, and it is not quiet on screen. I fed a 20x4 emulator twelve lines, alternating long-line-NN and a short sN. With the line gone, the bottom row, where the cursor sits, showed long-line-08 again. Without the mutation it is blank. A recycled row keeps extent 0, so the blanking skips it and the old text comes back. Five of the nine lines in the scrollback were empty. Anyone scrolling a shell would see it within a screen.

The tests that check what the screen looks like, the corpus and tmux, still passed. That is a coverage gap: none of their cases recycles a row the direct store wrote. The tests that check what the emulator believes about itself did not need such a case.

The rest of the pass

The other four commits are smaller, and each one is a fast path held to the slow path it skips by a test that runs both on random input.

CSI parameters skip the transition table. Every byte of 38;2;r;g;b went through the parser's transition table and an action switch to reach three lines of arithmetic. In a truecolor repaint those bytes are most of the stream. In the CSI parameter state the table maps 0 to ; to a parameter update and leaves the state alone, so the parser now does that update directly. TestSeqParserCsiParamsMatchUpstream feeds random CSI input to this parser and to upstream's and requires the same action, state and dispatch for every byte.

A plain letter enters the scrollback as its byte. Encoding a line for the scrollback packed the style and compared the link of every cell, about 20 ns a cell, to find nothing had changed. While no style or link is in force, a narrow unstyled ASCII cell now appends its byte, which is exactly what the full path wrote. TestEncodeLinePlainShortcutWritesTheSameBytes compares the two on random mixed lines.

An ASCII run is stored straight into its row. Printing a run of ASCII went through three calls and two bounds-checked reads per byte. When every cell under the run is one column wide, no wide character can be cut, and all of that comes down to one store. Anything wide under the run takes the old path. This is the direct store the extent had to learn about.

SGR colours stop allocating. A truecolor repaint made four allocations per cell. Two were a color.RGBA boxed into a color.Color, for the foreground and the background. The exact 38;2;r;g;b shapes now take the boxed value from a small cache on the emulator. A third was a string made from the open grapheme cluster, to test whether the next character extends it. That test now runs on a reused byte buffer. TestRGBParamsMatchReadStyleColor and TestHandleSgrMatchesReadStyle hold the colour path to the upstream readers on random parameter lists.

The SGR change is the one where CPU time is the wrong number to look at:

The fourth allocation per truecolor cell is still there. It keeps the open cluster's text across an escape sequence. Removing the other three saved 6% of CPU, so this one is worth a third of that at most, and the fix is one more piece of state on every emulator. I measured it and left it.

What I keep from this

The August benchmark was right, and it even named the fix. It said the loop could not go faster, which I read as "leave the loop alone" when it meant "run it less". When the work is already at the speed of memory, the only thing left is to touch less memory, and on a terminal full of short lines most of the memory is blanks.

The other part is the negative control. The extent itself is a small change. Trusting it took a test that watches the emulator's own bookkeeping, because the tests that watch the screen passed with the bookkeeping broken. The screen was wrong. They just never looked at a screen where it showed.