Research··2 min read

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

#encoding#integer codes

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.

valueLEB128
300000011
12001111000
15010010110 00000001

The integer 3 only needs two bits, 11, but LEB128 spends eight.

  • selector / continuation (c)
  • payload
  • unused
Fig. 1Encoding 3. LEB128 uses one continuation bit, five unused bits and two payload bits. The selector code uses a 2-bit width selector and the two payload bits.

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:

selectormeaning
002-bit integer (0 to 3)
013-bit integer (4 to 7)
104-bit integer (8 to 15)
11fall 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.

Fig. 2Live comparison of LEB128 and the 2-bit selector code for counts and lengths.

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.

Fig. 3A value-type tag such as 'non-negative integer'. The range is known, so it needs neither a selector nor a continuation bit.

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.