Opensource internals

tmux Redraws Only What Changed: Five Layers of Less Work

11 min read Jay Hubbert

tmux keeps a complete internal model of every pane and works out the minimum set of bytes to send: cell-level comparison, damage rectangles, a cached scene of spans, and a dirty-line bitmap for synchronized output.

TL;DR: tmux never redraws “the screen” — it redraws the difference. Five stacked mechanisms each remove work: skip unchanged cells, skip untouched regions, skip recomputing the layout, coalesce runs into spans, and during synchronized updates redraw only the lines that actually changed.

A terminal multiplexer that redraws the whole screen on every keystroke is unusable. tmux avoids it with a stack of increasingly precise mechanisms:

  1. cell comparison — don’t emit a cell that has not changed,
  2. damage rectangles — don’t even look at the parts of a window that were not touched,
  3. a cached scene — don’t recompute the layout of the screen if nothing about the layout changed,
  4. span coalescing — don’t emit one escape sequence per cell,
  5. a dirty-line bitmap — during a synchronized update, redraw only the lines that changed.

Here’s how each of those works, in the OpenBSD-flavoured tmux tree at commit 6f655f48.

The starting point: tmux knows what the screen looks like

Unlike a program that just writes bytes to a terminal, tmux maintains a full model of each pane: struct grid in grid.c, a two-dimensional array of cells with a history of scrolled-off lines above it.

That’s what makes diffing possible. To know whether a cell needs to be redrawn, you need to know what it should look like versus what the terminal does look like. tmux keeps the “should” in the grid and tracks the “does” in a second grid per client that is only updated when something is actually sent.

Without that second grid, none of the rest of this article is possible.

Level 1: comparing cells

grid.c has two comparison functions, and the split between them matters:

c 
/* Check if two styles are (visibly) the same. */
int
grid_cells_look_equal(const struct grid_cell *gc1, const struct grid_cell *gc2)
{
	int flags1 = gc1->flags, flags2 = gc2->flags;

	if (gc1->fg != gc2->fg || gc1->bg != gc2->bg)
		return (0);
	if (gc1->attr != gc2->attr)
		return (0);
	if ((flags1 & ~GRID_FLAG_CLEARED) != (flags2 & ~GRID_FLAG_CLEARED))
		return (0);
	if (gc1->link != gc2->link)
		return (0);
	return (1);
}

/* Compare grid cells. Return 1 if equal, 0 if not. */
int
grid_cells_equal(const struct grid_cell *gc1, const struct grid_cell *gc2)
{
	if (!grid_cells_look_equal(gc1, gc2))
		return (0);
	if (gc1->data.width != gc2->data.width)
		return (0);
	if (gc1->data.size != gc2->data.size)
		return (0);
	return (memcmp(gc1->data.data, gc2->data.data, gc1->data.size) == 0);
}

grid_cells_look_equal() compares style only: foreground, background, attributes, hyperlink. grid_cells_equal() additionally compares the character data itself.

The ~GRID_FLAG_CLEARED masking is a nice piece of care. GRID_FLAG_CLEARED is bookkeeping — it marks a cell that has been explicitly cleared — and it isn’t visible to the user. Masking it out means a cleared cell still compares equal to a cell with the same style, so a redundant clear doesn’t force a redraw.

The two levels get used for different things. Style comparison decides whether a run of cells can be emitted as one SGR change; full comparison decides whether a cell needs to be written at all.

Level 2: the per-cell skip

The hot path is screen_write_cell1() in screen-write.c. When tmux writes a character into the grid, it checks whether the terminal already shows that character:

c 
	/* If no change, do not draw. */
	if (skip) {
		if (s->cx >= gl->cellsize)
			skip = grid_cells_equal(gc, &grid_default_cell);
		else {
			gce = &gl->celldata[s->cx];
			if (gce->flags & GRID_FLAG_EXTENDED)
				skip = 0;
			else if (gc->flags != gce->flags)
				skip = 0;
			else if (gc->attr != gce->data.attr)
				skip = 0;
			else if (gc->fg != gce->data.fg)
				skip = 0;
			else if (gc->bg != gce->data.bg)
				skip = 0;
			else if (gc->data.width != 1)
				skip = 0;
			else if (gc->data.size != 1)
				skip = 0;
			else if (gce->data.data != gc->data[0])
				skip = 0;
		}
	}

This is deliberately not a call to grid_cells_equal(). It’s a hand-unrolled comparison against the packed representation, because this is the innermost loop of the whole program: it runs for every character of every program that outputs anything.

The packed comparison can’t handle every case, so it bails out to the slow path:

  • GRID_FLAG_EXTENDED cells (RGB colours, wide characters, hyperlinks,

    8-bit attributes) aren’t stored packed, so they’re always redrawn,

  • a wide character (width != 1) spans several cells and its padding has to be redrawn with it,
  • a multi-byte character can’t be compared with a single byte.

For plain ASCII in the default colours — the overwhelming majority of terminal output — this is four integer compares and one byte compare.

Level 3: damage rectangles

Even with per-cell skipping, tmux would have to walk every cell of every pane on every redraw. Damage rectangles avoid the walk.

A window accumulates a list of damaged regions (screen-redraw.c):

c 
/* A damaged rectangle in a window. */
struct redraw_damage {
	u_int				 x;
	u_int				 y;
	u_int				 sx;
	u_int				 sy;

	int				 flags;
#define REDRAW_DAMAGE_SCROLL 0x1

	TAILQ_ENTRY(redraw_damage)	 entry;
};

/*
 * If there are more damage rectangles than this, they are collapsed into
 * one.
 */
#define REDRAW_DAMAGE_MAX 16

Damage is recorded when a pane writes (redraw_damage_window() in screen-write.c), when an image is drawn (image-grid.c), and when a floating pane moves (window.c).

The interesting part is how damage is merged. redraw_apply_window_damage() walks the existing list and tries to fold a new rectangle into an existing one:

c 
		x0 = (x < rd->x) ? x : rd->x;
		y0 = (y < rd->y) ? y : rd->y;
		x1 = (x + sx > rd->x + rd->sx) ? x + sx : rd->x + rd->sx;
		y1 = (y + sy > rd->y + rd->sy) ? y + sy : rd->y + rd->sy;

		area = sx * sy + rd->sx * rd->sy;
		union_area = (x1 - x0) * (y1 - y0);
		if (union_area > 2 * area)
			continue;

The union_area > 2 * area test is the interesting one. Merging two rectangles that are far apart creates a bounding box that covers a lot of undamaged area. If the union is more than twice the size of the two rectangles combined, the merge is rejected and the new rectangle is added as a separate entry instead.

That keeps the list small without letting a scattered set of changes turn into “redraw everything”.

And past 16 rectangles, everything collapses into one bounding box:

c 
	TAILQ_INSERT_TAIL(&w->damage, rd, entry);
	if (++w->damage_count > REDRAW_DAMAGE_MAX)
		redraw_collapse_damage(w);

The same idea shows up in the damage flags: REDRAW_DAMAGE_SCROLL marks damage that the terminal can satisfy with a scroll rather than with repainted text, and redraw_client_damage() skips those regions when the terminal has already been told to scroll.

This whole mechanism is relatively new. The commit that introduced it says:

“Instead of redrawing the entire pane or scene when moving or redrawing a pane, add damage rectangles and redraw only the affected spans.”

Level 4: the cached scene

Damage tells you what changed. The scene tells you where everything is, and it is expensive to compute: pane positions, border positions, status line spans, scrollbars, the regions outside the window.

screen-redraw.c caches it per client and invalidates it with a generation counter:

c 
/* Get the cached redraw scene, rebuilding it if needed. */
static struct redraw_scene *
redraw_get_scene(struct client *c)
{
	struct redraw_scene	*scene = c->redraw_scene;
	struct window		*w = c->session->curw->window;
	const char		*reason = NULL;
	u_int			 ox, oy, sx, sy;

	redraw_get_window_offset(c, &ox, &oy, &sx, &sy);
	if (scene == NULL)
		reason = "missing";
	else if (scene->w != w)
		reason = "window changed";
	else if (scene->generation != w->redraw_scene_generation)
		reason = "generation changed";
	else if (scene->ox != ox || scene->oy != oy)
		reason = "offset changed";
	else if (scene->sx != sx || scene->sy != sy)
		reason = "size changed";
	if (reason != NULL) {
		log_debug("%s: @%u scene invalid: %s", c->name, w->id, reason);
		redraw_free_scene(scene);
		scene = redraw_make_scene(c);
		c->redraw_scene = scene;
	}
	return (scene);
}

The reason string is a nice touch — it’s logged, so you can see why the scene was rebuilt. When something feels slow, log_debug will tell you whether you were paying for geometry or for pixels.

The generation counter is a uint64_t assigned from a single global counter, so it’s unique across all windows:

c 
/*
 * Mark a window's cached redraw scenes as out of date. Generations are unique
 * across all windows so a scene can never match a new window that reuses the
 * address of a freed one.
 */
void
redraw_invalidate_scene(struct window *w)
{
	static uint64_t	next_generation;

	w->redraw_scene_generation = ++next_generation;
}

The comment on the counter explains why: a freed window’s address could otherwise be reused by a new window and the generation counter would accidentally match. This is the same class of bug as the ABA problem in lock-free data structures.

Building the scene allocates a temporary grid of cells. That grid is a single static buffer that is grown, never freed per frame:

c 
	ncells = (size_t)bctx->sx * bctx->sy;
	if (ncells > redraw_ncells) {
		redraw_cells = xreallocarray(redraw_cells, ncells, sizeof *redraw_cells);
		redraw_ncells = ncells;
	}

Level 5: spans

The scene isn’t a grid of cells when it’s finished; it’s a list of spans. The file’s own comment explains the pipeline:

text 
 * 1) redraw_build_cells fills a temporary grid of struct redraw_build_cell
 *    objects, one per visible cell. It marks pane contents, scrollbars,
 *    borders, pane status lines and any cells outside the window.
 * 2) redraw_make_scene takes the grid ... and converts them into spans
 *    by joining adjacent cells that have the same type and data.

The span types are:

c 
/* Type of span in the scene. */
enum redraw_span_type {
	REDRAW_SPAN_PANE,	/* inside a pane */
	REDRAW_SPAN_OUTSIDE,	/* outside the window */
	REDRAW_SPAN_EMPTY,	/* inside the window but nothing visible */
	REDRAW_SPAN_STATUS,	/* pane status line */
	REDRAW_SPAN_BORDER,	/* pane border */
	REDRAW_SPAN_SCROLLBAR,	/* pane scrollbar */
	REDRAW_SPAN_MENU,	/* window menu */
};
#define REDRAW_SPAN_TYPES 7

A span is “a run of cells that are all the same kind of thing”. A whole pane line becomes one span, and a whole status line becomes one span.

Level 6: writing the spans

The final stage is tty_draw_line() in tty-draw.c, a state machine that walks a line of cells and produces terminal output. Two things matter here.

First, runs of cells with the same style are accumulated into a buffer and flushed in one go:

c 
	if (grid_cells_look_equal(gcp, &last)) {
		...
		buf[len++] = ...;
		...
	}

with a fixed char buf[1000] — a stack buffer, no allocation, sized so that a full line of ordinary text fits without spilling.

Second, empty cells aren’t written as spaces. They’re cleared with the terminal’s own erase sequence, which is both shorter and correct for background colours:

c 
static void
tty_draw_line_clear(struct tty *tty, struct tty_ctx *ctx, u_int py, u_int px,
    u_int nx, u_int ny)

using EL, EL1 or ECH depending on what the terminal supports and where the run is.

Level 7: synchronized output and the dirty-line bitmap

The last mechanism is for applications that use synchronized output (the DECSET 2026 mode) — vim with set t_RV and friends. In that mode the terminal buffers everything until it receives an end-of-synchronised-update, so tmux can defer output.

tmux tracks which lines changed with a bitmap (screen-write.c):

c 
	if (bs != NULL && wp->sync_dirty_size == sy)
		return (bs);

The bitmap is allocated once per pane size and reused, and it’s what screen_write_sync_flush_dirty() uses to redraw only the lines that changed when the sync frame ends.

The commit that added scroll tracking to it is a good illustration of the kind of thinking that makes this fast:

“As well as tracking modified (dirty) lines during a synchronized update, also track scrolled lines. This means they can be scrolled as one instead of forcing each line to be redrawn — much less expensive for a very common operation.”

Scrolling is by far the most common thing a terminal program does. Being able to express it as “one scroll” rather than “80 repainted lines” is worth a lot.

Putting it together

The full path for a keystroke in a pane is roughly:

text 
program writes to pty
  → input.c parses the bytes into a screen_write context
    → screen-write.c updates the grid, marking damage
      → damage rectangles accumulate on the window
        → next event loop iteration, the client's scene is looked up
          → the scene is reused if nothing structural changed
            → spans are drawn, comparing against the client's grid
              → unchanged cells emit nothing
                → changed cells are batched into runs
                  → the whole thing is one write() to the client's tty

Each layer removes work rather than adding it. The two most impactful single decisions are probably the hand-unrolled packed cell comparison (level 2) and the damage rectangle merging with the 2x area cutoff (level 3): the first makes the common case cheap, the second keeps the common case from happening at all.

The overall design goal is stated in the commit that introduced the scene cache:

“A scene is generated and cached in the client: it holds positions and sizes of panes, borders and so on. The scene is invalidated when a pane is moved or resized.”

Everything else follows from that: if the geometry hasn’t changed, there’s no reason to recompute the geometry.

TmuxPerformanceInternalsRedraw