Bits, not bytes: where byte-aligned integer codes leave space on the table
Byte-aligned integer encodings waste most of a byte on small numbers. A 2-bit width selector recovers most of it, and you can try it yourself below.
Related: Small integers at bit granularity
Most compact serialization formats work at byte granularity. That made sense when CPUs, disks and network buffers all spoke bytes. But many numbers inside JSON are structurally small: indexes, counts, lengths, enum-like flags. Rounding each of them up to 8 bits throws away space that adds up quickly. This article looks at the integer codes of a bit-level columnar encoding I have been studying; Small integers at bit granularity treats the same codes more formally.
LEB128 and the cost of small numbers
LEB128 is the usual variable-length integer. Each byte carries 7 bits of payload, and its most significant bit says whether another byte follows.
| value | LEB128 |
|---|---|
3 | 00000011 |
120 | 01111000 |
150 | 10010110 00000001 |
The integer 3 only needs two bits, 11, but LEB128 spends eight.
- selector / continuation (c)
- payload
- unused
A 2-bit width selector
The encoding puts a 2-bit selector in front of its counts and lengths. The selector picks one of four widths:
| selector | meaning |
|---|---|
00 | 2-bit integer (0 to 3) |
01 | 3-bit integer (4 to 7) |
10 | 4-bit integer (8 to 15) |
11 | fall back to LEB128 (16 and up) |
3 therefore becomes 0011: four bits, half of what LEB128 uses. Across 1,000 integers below 4 that is 4,000 bits, or 500 bytes, saved before any other trick.
The same selector idea appears in three variants, chosen by context. Short (2, 3 or 4 bits) is used for counts and lengths. Uint (3, 4 or 6 bits) is used inside a top-level single value, for example the magnitude of a negative integer or the precision of a float. Num is used for the number column, where the 00 selector means “small delta from the previous number” and the other selectors pick a 4-bit, 6-bit or LEB128 literal.
Try it
Drag the slider. Below 16 the selector code wins by 2 to 4 bits: 4 against 8 for values 0 to 3, 5 for 4 to 7, 6 for 8 to 15. From 16 upward it falls back to LEB128, and the selector becomes a fixed 2-bit overhead at every size. The scheme pays off only when small values dominate. Counts, lengths and tags in small documents are exactly such values.
When the width is already known
Some fields have a fixed range. The encoding has seven value types plus the reserved code 000, eight codes in all, so a type tag always fits in 3 bits. For fields like this the selector is dropped completely.
That saves 5 bits against LEB128’s 8-bit minimum on every tag. Because the encoder writes fields in a fixed, deterministic order, the decoder always knows which kind of field comes next. Bit positions carry the meaning, so no field tags or delimiters are needed.
Next: how the encoder reorganizes a JSON tree into columns so that these small integers show up as often as possible.