How tmux Stores Grid Cells in Five Bytes

A terminal grid cell is not small. In the “in-memory” representation it holds a UTF-8 character (up to four bytes), a foreground colour, a background colour, an underline colour, a set of attribute bits, a hyperlink id and some flags. That is comfortably 32 bytes per cell.

Multiply by 80x24 and you get 61 KB per screen. Multiply by 10,000 lines of scrollback and 200 panes, and it is gigabytes.

tmux’s answer is a split representation: the common case is packed into five bytes, and the rare case lives in a side table.

The two representations

The in-memory form (tmux.h) is the “fat” one:

/* Grid cell data. */
struct grid_cell {
	struct utf8_data	data;
	u_short			attr;
	u_char			flags;
	int			fg;
	int			bg;
	int			us;
	u_int			link;
};

struct utf8_data alone is six bytes, and the three int colours are twelve. So the fat cell is around 32 bytes.

The stored form is the packed one:

/* Grid cell entry. */
struct grid_cell_entry {
	union {
		u_int		offset;
		struct {
			u_char	attr;
			u_char	fg;
			u_char	bg;
			u_char	data;
		} data;
	};
	u_char			flags;
} __packed;

The union is the trick. The same five bytes are either:

• data.attr (8 bits of attributes), data.fg (8-bit colour), data.bg (8-bit colour), data.data (the character), plus flags — the packed form, or
• offset — an index into the line’s array of grid_extd_entry — the extended form.

__packed matters: without it the compiler would pad the struct to eight bytes and the whole optimisation would evaporate.

The extended form:

/* Grid extended cell entry. */
struct grid_extd_entry {
	utf8_char		data;
	u_short			attr;
	u_char			flags;
	int			fg;
	int			bg;
	int			us;
	u_int			link;
} __packed;

has room for everything: RGB colours, wide characters, more than eight attribute bits, hyperlinks.

Deciding which form to use

The decision is made by grid_need_extended_cell():

/* Check if a cell should be an extended cell. */
static int
grid_need_extended_cell(const struct grid_cell_entry *gce,
    const struct grid_cell *gc)
{
	if (gce->flags & GRID_FLAG_EXTENDED)
		return (1);
	if (gc->attr > 0xff)
		return (1);
	if (gc->data.size > 1 || gc->data.width > 1)
		return (1);
	if ((gc->fg & (COLOUR_FLAG_RGB|COLOUR_FLAG_THEME)) ||
	    (gc->bg & (COLOUR_FLAG_RGB|COLOUR_FLAG_THEME)))
		return (1);
	if (gc->us != 8) /* only supports 256 or RGB */
		return (1);
	if (gc->link != 0)
		return (1);
	if (gc->flags & GRID_FLAG_TAB)
		return (1);
	return (0);
}

So a cell is extended if it has:

• more than eight attribute bits,
• a multi-byte or double-width character,
• an RGB or theme colour,
• an underline colour other than the default,
• a hyperlink,
• or is a tab.

Everything else — plain ASCII, 8-bit colours, standard attributes — is packed.

For a typical terminal session that is nearly every cell. The 256-colour palette fits in eight bits, and the eight standard attribute bits (bold, underline, reverse, and so on) fit in eight bits.

Note the first line: once a cell is extended, it stays extended. That simplifies the code enormously — you never have to convert back — at the cost of not being able to compact a cell that has become simple again.

256 colours in eight bits

The colour packing is slightly more subtle than “eight bits of colour”:

/* Store cell in entry. */
static void
grid_store_cell(struct grid_cell_entry *gce, const struct grid_cell *gc,
    u_char c)
{
	gce->flags = (gc->flags & ~GRID_FLAG_CLEARED);

	gce->data.fg = gc->fg & 0xff;
	if (gc->fg & COLOUR_FLAG_256)
		gce->flags |= GRID_FLAG_FG256;

	gce->data.bg = gc->bg & 0xff;
	if (gc->bg & COLOUR_FLAG_256)
		gce->flags |= GRID_FLAG_BG256;

	gce->data.attr = gc->attr;
	gce->data.data = c;
}

The colour value is 0-255 in the byte, and the flags record whether it came from the 256-colour palette or the 16-colour one, because “bright black” means different things in the two palettes. The RGB flag lives in COLOUR_FLAG_RGB, which is above 8 bits and therefore forces the extended form.

Lazy line growth

Lines are not allocated at full width up front. grid_expand_line() grows them in geometric steps:

/* Expand line to fit to cell. */
static void
grid_expand_line(struct grid *gd, u_int py, u_int sx, u_int bg)
{
	struct grid_line	*gl;
	u_int			 xx;

	gl = &gd->linedata[py];
	if (sx <= gl->cellsize)
		return;

	if (sx < gd->sx / 4)
		sx = gd->sx / 4;
	else if (sx < gd->sx / 2)
		sx = gd->sx / 2;
	else if (gd->sx > sx)
		sx = gd->sx;

	gl->celldata = xreallocarray(gl->celldata, sx,
	    sizeof *gl->celldata);
	...
	gl->cellsize = sx;
}

The sizes are 1/4 width, 1/2 width, full width. So a program that prints one character on a fresh line allocates a quarter of a line, not a whole one, and a program that prints a few characters does not repeatedly realloc.

The grid_line struct tracks cellused and cellsize separately, so the trailing cells of a mostly-empty line do not need to be stored at all.

This was a deliberate change; the CHANGES file records:

“Create every line as zero length and only expand it as data is written, rather than creating at full size immediately.”

Not leaking extended cells

Extended cells are allocated from a per-line array. When a cell is overwritten with something simple, the extended entry it used would normally be leaked — the line’s extended array would grow forever as a program repaints the same line with different colours.

grid_clear_cell() reuses the existing slot:

/* Copy default into a cell. */
static void
grid_clear_cell(struct grid *gd, u_int px, u_int py, u_int bg, int moved)
{
	struct grid_line	*gl = &gd->linedata[py];
	struct grid_cell_entry	*gce = &gl->celldata[px];
	struct grid_extd_entry	*gee;
	u_int			 old_offset = gce->offset;
	int			 had_extd = (gce->flags & GRID_FLAG_EXTENDED);

	memcpy(gce, &grid_cleared_entry, sizeof *gce);
	if (!moved && had_extd && old_offset < gl->extdsize) {
		gce->flags |= GRID_FLAG_EXTENDED;
		gce->offset = old_offset;
		gee = grid_extended_cell(gl, gce, &grid_cleared_cell);
		if (bg != 8)
			gee->bg = bg;
	} else if (bg != 8) {
		...

Note old_offset being saved and restored: the cell keeps its extended form and its slot in the extended array, it just gets reset to the cleared state. The commit message for this was:

“Reuse extended entry when clearing RGB cell, to prevent memory growth.”

And the extended array itself is compacted when the line shrinks:

/* Free up unused extended cells. */
static void
grid_compact_line(struct grid_line *gl)
{
	int			 new_extdsize = 0;
	...
	for (px = 0; px < gl->cellsize; px++) {
		gce = &gl->celldata[px];
		if (gce->flags & GRID_FLAG_EXTENDED)
			new_extdsize++;
	}
	...
	idx = 0;
	for (px = 0; px < gl->cellsize; px++) {
		gce = &gl->celldata[px];
		if (gce->flags & GRID_FLAG_EXTENDED) {
			gee = &gl->extddata[gce->offset];
			memcpy(&new_extddata[idx], gee, sizeof *gee);
			gce->offset = idx++;
		}
	}

	free(gl->extddata);
	gl->extddata = new_extddata;
	gl->extdsize = new_extdsize;
}

This is a mark-and-sweep compaction: count the live extended cells, allocate a new array of exactly that size, copy them over, and fix up the offsets. The old array is freed. The cell’s offset changes, which is why this cannot be done while the grid is being read by anything else.

History trimming

Scrollback is the other place memory grows without bound. When the history hits the limit, tmux frees the oldest 10% rather than one line at a time:

/*
 * Collect lines from the history if at the limit. Free the top (oldest) 10%
 * and shift up.
 */
void
grid_collect_history(struct grid *gd, int all)

and the shift itself is a memmove() of the line array:

void
grid_trim_history(struct grid *gd, u_int ny)
{
	u_int	remaining;

	grid_free_lines(gd, 0, ny);
	remaining = gd->hsize + gd->sy - ny;
	memmove(&gd->linedata[0], &gd->linedata[ny],
	    remaining * (sizeof *gd->linedata));
	memset(&gd->linedata[remaining], 0, ny * (sizeof *gd->linedata));
}

Trimming one line at a time would be O(n) per line of output, which is O(n²) over a full history. Trimming 10% at a time is O(n) per 10% of the history.

The CHANGES file dates this to 2007:

“Rather than shifting up one line at a time once the history is full, shift by 10% of the history each time. This is faster.”

The allocation helpers

All of this depends on allocation being cheap and safe. xmalloc.c provides xmalloc, xcalloc, xreallocarray, xrecallocarray and xmemdup, all of which abort the process on failure rather than returning NULL:

void *
xcalloc(size_t nmemb, size_t size)
{
	void *ptr;

	if (size == 0 || nmemb == 0)
		fatalx("xcalloc: zero size");
	if (SIZE_MAX / nmemb < size)
		fatalx("xcalloc: nmemb * size > SIZE_MAX");
	ptr = calloc(nmemb, size);
	if (ptr == NULL)
		fatal("xcalloc: allocating %zu bytes", size * nmemb);
	return (ptr);
}

The overflow check is the interesting part: nmemb * size is computed in calloc() too, but the check has to happen first, in a form that cannot itself overflow.

Because allocation never returns NULL, no hot path has to check for it, and the xreallocarray() variants make the “array of n things” case safe by default.

The numbers

For an 80x24 pane of plain text:

With 10,000 lines of scrollback per pane and 20 panes, the difference is about 1 GB versus 160 MB.

The lesson

The general technique here — a packed common case and an out-of-line rare case — is the same one used by Python’s compact dicts, PostgreSQL’s varlena headers, and the Linux kernel’s struct file_operations. The key insight is that the in-memory representation used during manipulation and the stored representation used for retention do not have to be the same.

tmux gets to have both, because the fat form is only materialised one cell at a time, on the stack, while parsing and drawing. The grid — the thing that lives for hours and grows without bound — is the packed one.