The data structure behind terminals
Grids - two-dimensional arrays of characters - are the universal building blocks of terminals. The basic operations we expect from our terminals - entering a command, receiving output, scrolling through a file - are, at their core, operations on grids. This piece is an attempt at explaining the terminal from the bottom up, starting from the grid. The goal is to spell out some of the not-so-obvious performance calculus behind terminal grids: what are the operations being optimized and at what cost?
If a terminal session is really some conversation history between the terminal and the commands it has executed or is currently executing, then it’s the grid that provides some agreed-upon format or ledger to converse. It’s not just that grids are a convenient choice for terminal builders; the grid is actually what’s required by the program the terminal is layered over, the shell. The shell moves a cursor and outputs characters within a defined two-dimensional space, and the terminal is responsible for storing and rendering the contents of that space to the end-user. This makes the concept of the grid a – if not the – fundamental engineering specification of terminals.
(If you’re curious to learn more about the dependencies between terminals and shells, I recommend this blog post.)
In Warp, the grid is especially important because it’s everywhere. Warp separates commands into blocks, and each block consists of three grids: one for the prompt, one for the command input, and one for the command output. Even opening full-screen programs like vim and emacs are themselves instances of this same grid, just with expanded dimensions.
Even more interesting are the trade-offs the grid must make between the most basic terminal operations. Some examples of these operations are reading in data from the shell, scrolling through content, and resizing the screen or splitting panes. Warp’s implementation of the grid is itself an opinionated stance on which of these operations a terminal should be most efficient at, with the reality being that optimizing for one almost always means not optimizing for another. Should we be excellent at one thing if it means being just okay at something else? The grid is the layer at which this type of performance calculus is baked in and shipped to our users.
The conversion between the screen index and the vector index is a really, really important one. When the grid renders to the screen, we’ll want to locate the contents of screen index 0 and then 1 and then 2 and so on. To optimize for this, the grid stores two integers that allow us to efficiently translate between screen space and vector space.
Using these indices, we can convert from screen space to vector space like this:
Nevertheless, the whole process of index conversions presupposes that the grid needs to be rotated in the first place. Why is that the case? Why not skip the silly conversions and enforce equivalence between the screen indices and the vector indices, meaning that “As You Like It,” the first row on screen, is also stored as the first row in the vector? Not surprisingly, this is because the grid is heavily optimizing for something else entirely: scrolling!
Scrolling the grid
What would this look like at the grid layer? To start off, the underlying vector is unrotated. It looks like this, with bottom_row = 8 and the conceptual “top row” = 0.
The first step to scrolling up is to extend bottom_row by one while keeping length the same. When we wrap bottom_row, it becomes 0 and top row becomes 1.
From there, we overwrite the contents of the bottom row with whatever the shell feeds to Warp as the next line in the file – in this case, “Tempest”. After that, the scroll operation is finished and the resulting grid looks like this:
What’s noteworthy is that Warp completes this scroll operation without moving any data in the vector, besides overwriting the exiting row with the entering row. The scroll operation succeeded solely by changing the metadata of the grid, specifically the index of the bottom_row. The result is an extremely efficient scroll operation at the cost of leaving the grid in a rotated state.
One of the penalties of the now-rotated grid is the added complexity of index conversion that we discussed above. Broadly speaking, this penalty is relatively minor and is more than compensated for by the efficiency we gain during scrolling. Where this becomes a little bit more harrowing as a performance calculation is when we actually receive output from the shell and find ourselves needing an extra row. At that time, having a grid that’s rotated leaves us no choice but to move memory.
Extending the grid
A lot of terminal commands print content to the screen rapidly and require the size of the grid to grow dynamically.
Here, the terminal reads content from the shell (via the receiving end of a pipe known as the PTY, short for pseudo-TTY) and writes it to a grid. This is a fundamental operation for the terminal: how efficiently can we read streamed input from an open file descriptor and write it character-by-character to the specified grid location?
Specifically, the problem becomes interesting in the common case where the shell issues a newline – this is the shell warning the terminal that the command requires more than the current size of the grid, implying the vertical grid dimension needs to be expanded by one row. From the terminal’s perspective, let’s consider this request under the worst-case grid configuration: the underlying vector is already at capacity and the grid is rotated (again, index on screen != index in vector).
Because the penalty under the worst-case grid configuration is very high, Warp does its best to make this circumstance as infrequent as possible. As an example, we only allocate new rows in chunks of 1000, opting to make the resize slightly more heavyweight with the benefit of amortizing the cost to every 1000 newlines.
Resizing a grid
A final, essential piece to this weaving narrative about grid optimizations and their externalities is the process of resizing a grid. Importantly, grids in Warp are always stored at the dimensions of the pane in which they render, which are not necessarily equivalent to the dimensions at which we received them from the shell. Said differently, we always rewrite the grid so any horizontal limit is imposed at the time of resizing and not at the time of rendering. This makes more sense with a visual:
We permit this considerable performance penalty – for now – because, although resizing is an essential operation, it’s hard designing optimizations that won’t slow down everything else: doing index conversions, scrolling, adding a new line to the grid, etc. From a holistic standpoint about overall performance priorities in the app, it’s also not clear that resizing should take precedence over any of those things.
All told, an intelligent, intentional design of the terminal grid should recognize that oftentimes the most important operations are in competition with one another. Every block in Warp is a careful calculus about where to excel and how to minimize the resulting cost: that the rotated vector streamlines scrolling but costs us the amortized “re-zero” every 1000 lines, that allocating new rows in chunks means we’re willing to risk some bloat for fewer memory allocations, that storing the grid in its renderable dimensions is optimal but leaves us vulnerable at resize, to name but a few.
If you have opinions on what our performance priorities should be – or any insights about the trade-offs discussed here – we’d love to hear from you! Better yet, if you find this type of problem interesting, come work with us!
Experience the power of Warp
- Write with an IDE-style editor
- Easily navigate through output
- Save commands to reuse later
- Ask Warp AI to explain or debug
- Customize keybindings and launch configs
- Pick from preloaded themes or design your own