Why Expanse's Memory Comes in Teeth

In the Expanse launch post I published a memory footprint of 7.92 bytes per key for one million uniform random 64-bit keys. Then I doubled the population to two million and measured 13.60 bytes per key. Same build, same deterministic allocator accounting, no code change. At 100,000 keys the figure had been 14.78. A number that goes 14.78 → 7.92 → 13.60 as you add keys is neither a bug nor noise. It is the shape of the data structure, and I had been quoting one point on it.

Where does that curve come from? It comes down to three mechanics: how the adaptive node ladder grows a node, why occupancy per expanse is the only variable that matters on random keys, and what that forced me to change in my benchmarks once I understood it. Every number below is a committed measurement from the orieg/expanse repository, taken with the engine’s own byte accounting (mem_used()), which counts the bytes of every node the structure holds. It is machine-independent and reproduces byte for byte. It is not allocator-held memory; I’ll come back to that difference at the end.

How the Adaptive Node Ladder Grows a Node

For readers who skipped the launch post, a short refresher. Judy arrays are Doug Baskins’s early-2000s design from HP: a 256-ary digital trie that consumes a key one byte at a time, so each node covers a fixed range of the key space. Baskins called that range an expanse, and the design partitions by expanse rather than by population the way a B-tree does. Expanse is my clean-room rebuild of that idea in Rust for current CPUs.

Partitioning by expanse has one consequence that this whole post rests on: a node never decides how many keys it covers. The keys decide, by landing in its range. The only thing a node controls is which physical form it takes for the population it received. That choice is the adaptive node ladder.

Every node is reached through a 16-byte edge. From the bottom up, the rungs are:

• Immediate: a key with 15 or fewer undecoded bytes left is stored inside the edge itself. No node at all.
• Linear leaf: a handful of keys become a packed array of their remaining bytes. A leaf below a 2-byte prefix (Leaf6) stores 6 bytes per key and has no header in the set flavor. It holds at most LEAF_CAP = 32 keys.
• BranchL3, BranchL7: linear branches holding up to 3, then 7, child edges, packed into one and two cache lines.
• BranchB: a 128-byte branch with a 256-bit bitmap over its sub-expanses and eight packed subarrays of child edges.
• BranchU: past 192 populated sub-expanses, a flat 256-slot array of edges, 4 KiB plus one line.

Each rung is picked by the population of that one expanse and nothing else. Delete walks back down one rung behind insert, so a key hovering at a boundary does not thrash the node between two forms.

The launch post stopped there. The step it did not cover is the one this post is about: what the 33rd insert does to a full leaf.

A Leaf6 holding 32 keys costs 192 bytes plus its 16-byte edge, 6.5 bytes per key. The 33rd key does not open a second leaf. There is nowhere for one to go: the expanse is fixed, and the leaf is already the most compact form that covers it. So the leaf cascades into a branch whose children are the 256 sub-expanses one byte further down. At these densities almost all of those children hold a single key, and a single key is stored as an immediate, in its own 16-byte edge. Thirty-one boxes at 16 bytes, a 128-byte branch to hold them, the parent edge: about 20 bytes per key for the same 33 keys that cost 6.5 a moment ago.

The mental model that captures this best is egg cartons. A carton is a leaf: it holds 32 eggs, and the cardboard is the edge plus the leaf’s bytes. Cardboard per egg drops as the carton fills. The 33rd egg does not get a second carton. The carton is torn up and every egg gets boxed alone, one 16-byte box each, on a shelf. Much later, once each shelf slot has collected enough eggs of its own, the boxes get packed back into cartons. That is the next tooth, and I measured it too.

Why Occupancy Is the Only Variable

In Judy and Expanse terminology, an expanse is simply the numerical range of key space covered by a node. The trie itself is unbounded and dynamically subdivides into smaller and smaller sub-expanses as keys are added.

The 65,536 figure is not a limit on the trie; it is simply the geometry of the first leaf level on 64-bit keys. Because Expanse decodes keys byte-by-byte, a 64-bit key descends through two branch levels (byte 7, then byte 6) to reach the initial leaf level (Leaf6). Those top two bytes (16 bits) partition the 64-bit key space into 256 × 256 = 65,536 two-byte expanses, each covering a range of 2⁴⁸ keys.

At this depth, each populated expanse starts as a single leaf holding up to 32 keys. If you insert a total of N uniform random keys, they scatter at random across these 65,536 expanses, averaging:

λ = N ÷ 65,536 keys per 2-byte expanse

When λ approaches 32, those 65,536 expanses begin overflowing and cascade into deeper branch levels—each creating 256 smaller 3-byte sub-expanses. That is why the teeth occur: not at an arbitrary population, but whenever an entire level’s expanses approach the 32-key leaf cap.

If the ladder picks node forms by occupancy, then the keyspace width and the population are one parameter, not two. Clearing the top bit of every key halves the number of expanses, which is arithmetically the same as doubling N. The sweep confirms it. Same ExpanseSet, same PRNG and seed, the keyspace narrowed by masking the top bits:

Populations that differ by 4× agree within 0.05 bytes per key when their occupancy matches. Three sweeps, one curve. Bytes per key is not a function of N. It is a function of λ.

Memory Density vs. Keys per 2-Byte Expanse

Here is the curve, 45 measurements from 1.5 to 15,625 keys per 2-byte expanse, redrawn from the committed sweep. The x axis is logarithmic because the second tooth sits 256× to the right of the first.

Under density alone, with no code change, the same structure spans 6.71 to 21.02 bytes per key. The first tooth bottoms out at 7.59 (λ = 19.8), has its knee around λ = 27, and peaks at 21.02 (λ = 48.8). The 1M figure I published sits at λ = 15.26, one step from the bottom of the trough. It was the most flattering point on the curve, and I picked it by accident: one million is simply the population everyone benchmarks at.

The second tooth is the first one repeated one byte level down. Below a cascaded 2-byte expanse the 256 sub-expanses hold λ ÷ 256 keys each, in Leaf5 leaves under the same cap, so the cascade fires again when λ ÷ 256 approaches 32. Four measurements at 58- to 55-bit keyspaces put the sub-expanses at the same four occupancies as the 400k, 1M, 2M, and 4M populations of the first tooth, and they reproduce its shape:

The second trough is lower (6.71 at λ = 4,688) because a Leaf5 stores 5 bytes per key rather than 6, and the 4,160-byte BranchU above it is amortized over thousands of keys. The second peak is the first peak’s number to two decimals, because at λ = 15,625 every one of the sub-expanses has cascaded into a bitmap branch of single-key immediates, which is exactly the structure the first tooth has at λ = 61.

Anatomy of One Tooth

The cliff is a ramp rather than a step because occupancy is not uniform across expanses. Random keys land where they land; the population per expanse is Poisson with mean λ. At λ = 15.26, about 3 expanses out of 65,536 are predicted to hold more than 32 keys. At λ = 30.52 it is 35% of the expanses, and those hold 42% of the keys. Between roughly λ = 26 and λ = 40, the cascade goes from a tenth of the expanses to nine-tenths. The model is committed in the repo as scripts/density_poisson.py with its reference values pinned by tests.

The engine’s own node census agrees with the model. Walking the two-million-key structure counts 22,970 cascaded expanses against 22,945 predicted, a residual of 0.11%. The 13.60 bytes per key at that population is the weighted mix of two regimes: 42,566 packed leaves holding 27% of the bytes, and 22,970 cascaded branches with their 780,905 single-key edges holding 69%. A second PRNG seed moves any of these measurements by at most 0.03 bytes per key.

After the peak, the curve falls again, but not because leaves come back. Between λ = 49 and λ = 122 the cost drops from 21.02 to 15.58 because the fixed branch cost is spread over more and more single-key children. The cartons only return when the sub-expanses fill toward 32 keys of their own, thousands of keys per 2-byte expanse later, and that is where the second tooth begins.

Where the Cliff Comes From: LEAF_CAP

If the tooth is the leaf cascade, then moving LEAF_CAP should move the tooth. So I changed that one constant from 32 to 48 by a build-time patch, changed nothing else, and re-ran the whole sweep.

The tooth moves; it does not flatten. The run below the cliff is unchanged, since nothing cascades at λ = 15 under either cap. The trough drops to 6.99 and slides right to λ = 30.5, exactly where the shipped build sits in the middle of its cliff. The ramp starts where the Poisson model says a cap of 48 should start cascading, 10% at λ = 40.3 and 90% at λ = 58.2, and the peak reappears at λ = 61. The second tooth moves the same way: 5.99 at λ = 7,812 instead of 12.98. Point being, the tooth is the cascade, and the cascade is this constant.

I did not ship 48, and it took a second benchmark to say why.

The first one looked like a clean bill. At the one-million-key population, Callgrind counts an identical 6,139,088 instructions for set_contains under both caps, and wall clock on the reference host agrees within its intervals. It proves almost nothing. At that occupancy no leaf ever reaches either cap, so the two builds hold the same structure, and all the comparison shows is that the constant by itself does not change a descent.

The regime that matters needed its own harness, at an occupancy where the two builds genuinely differ. At 30.52 keys per 2-byte expanse, roughly a third of the expanses cascade into single-key immediate branches under cap 32, compared to fewer than one in a thousand under cap 48. Measured there, cap 48 retires 17 to 19% more instructions per lookup, and on the reference host it runs 14 to 18% slower on every arm: hit and miss, set and map. The structure fits the host’s cache under either cap, so no memory-traffic saving gives that back.

So the trade is a measured pair rather than an argument. At that occupancy, cap 48 halves the set’s bytes per key and costs about a sixth more instructions per probe. LEAF_CAP stays 32 on the strength of that pair, which rules on nothing beyond this occupancy and the read path.

The write path is not free of the constant either. The insert benchmarks retire 7 to 8% more instructions under cap 48 at a population where no leaf ever holds 33 keys, for a reason I have not found.

Which Key Distributions Are Affected

The launch post’s memory table listed five key distributions. Revisited by occupancy, they sort into three groups.

Sequential and clustered keys never move. Consecutive keys compress into bitmap and full-expanse leaves at 0.07 to 0.36 bytes per key, and adding keys adds more of the same. Their occupancy is fixed by construction, so they have no λ to vary.

Sparse keys are permanently past the cascade. The i << 40 distribution puts exactly one key in each leaf-level expanse, so every key pays a full 16-byte edge plus its share of a 4,160-byte BranchU over 256 children: 16.25 bytes, plus the tiers above, 16.31 measured. That is the all-singletons floor of the cascaded regime, not a different curve, and the random curve actually drops below it at λ = 122 (15.58) because by then a fifth of the sub-expanses hold two or more keys.

Random keys are the only committed distribution whose occupancy moves with N. So they are the only ones with a tooth. In short, teeth need occupancy near the leaf cap, and most real key sets sit well below it (identifiers, timestamps, anything clustered) or well above it (hashes at scale). The band in between is where a single bytes-per-key number lies to you.

What I Changed in the Benchmarks

First, the memory-budget gate in the repo was calibrated at one million random keys against a 9.00 bytes-per-key ceiling. At 7.92 that looked like 14% headroom. On the curve, the ceiling is crossed somewhere between 1.6 and 1.8 million keys, so the headroom was about 1.6× in population, not 14% in bytes. At two million the gate fails by 51% with the engine doing exactly what the code says. The gate now records the occupancy it was calibrated at, and the repo’s benchmarking rules require λ next to every memory figure on random keys. I no longer publish a single bytes-per-key number for that distribution.

The second change is how I read comparisons. Against HOT, in its own comparison suite where both arms are measured the same way, Expanse wins at every measured occupancy from λ = 8 to 23 (1.42× at 15) and loses from λ = 30 up (1.76× at 38). HOT sits between 11.7 and 12.1 bytes per key the whole way. The same engine reads as a clear win or a clear loss depending on which population you happen to sample. Compare curves, not points.

The third is the difference between structural and allocator-held memory, which I promised to come back to. mem_used() is the engine adding up its own nodes, and it does not depend on the order keys arrive in. What the C allocator holds does. The same one million random keys hold 8.14 bytes per key from the allocator when inserted in sorted order and 12.62 when inserted in generator order, at 7.92 mem_used() either way. The committed counts show the observable difference: generator order retires 12,150 allocations against 8,318 frees (3,832 live chunks in the allocator), while sorted order retires 11,821 allocations against 9,077 frees (2,744 live chunks)—759 more allocations freed and returned. The code makes the mechanism visible: scattering across 65,536 expanses keeps more mid-growth leaves in flight across slab pages at once, even though the internal free lists themselves were not instrumented directly. Two published figures I could not reconcile for a week (8.27 and 12.62) turned out to be that, not a measurement error on either side.

The practical lesson for anyone loading a trie is older than Judy: sort your bulk loads.

Looking Ahead

The slope of each tooth is amortization—a fixed edge spread over a filling leaf. Only the cliff is the ladder changing node form. Seen from the memory side, that is all the adaptive node ladder is.

The unexplained 7–8% insert instruction regression under cap 48 is the one thing here I still cannot account for, and it will be the next measurement.

If you run Expanse, or any expanse-partitioned trie, on your own keys: count the distinct top-two-byte prefixes in your key set and divide N by that. The result is your λ, and the chart above tells you what it costs. ExpanseSet::stats() will give you the per-leaf population histogram if you want to see the Poisson spread for yourself.

Sources: the density sweep and census in docs/ARCHITECTURE.md §3.5, the full tables in docs/benchmarks/hot_comparison/METHODOLOGY.md §9.10, the measurement run in PR #712, and the archived release on Zenodo ( 10.5281/zenodo.22152112). What are your thoughts?