F4.06 · part 1 of 3
Compressed node layout
A CHAMP node describes its 32 slots with two bitmaps. The datamap has a
bit set for each slot holding an inline entry; the nodemap has a bit set for each
slot holding a child node. The entries live in one packed array and the children in another, each holding only
what is present — no empty cells. To find a slot’s position in its array you take a
popcount: the number of set bits below it.
An 8-slot node (32 in reality) with entries at slots 1 and 4 and children at slots 2 and 6. Select what to read.
Two bitmaps, two arrays
The bitmaps say which slots are used; the arrays hold the contents densely. Reading a slot is two steps: check the bit, then index into the array by the popcount of the lower bits. Select a bitmap, or watch the index get computed.
What to read · select one
role: which slots hold entries
result: datamap → 2 packed entries
A bitmap plus a popcount replaces a 32-wide array of mostly-empty slots with a compact one. The node stores two small arrays and two integers, and still finds any slot in constant time.
Advanced: against the HAMT node
A HAMT node typically carries one bitmap and one array, and that array mixes entries with child pointers;
distinguishing them needs a tag or a side table, and to stay shallow the tree tolerates nodes that wrap a
single entry. CHAMP’s two-bitmap split removes both compromises: entries and children never share a
cell, each array is gap-free, and the node is smaller. The index trick is the same popcount on whichever
bitmap applies, expressed with Bitwise — and popcount
is a single CPU instruction on modern hardware, so the lookup stays cheap. This compact node is exactly what
the stack’s BrandedChamp trie stores, one per level of a key’s hash.
import Bitwise # is slot i an inline entry? a child? — test the two bitmaps def entry?(datamap, i), do: (datamap &&& (1 <<< i)) != 0 def child?(nodemap, i), do: (nodemap &&& (1 <<< i)) != 0 # position in the packed array = popcount of the lower bits def data_index(datamap, i), do: popcount(datamap &&& ((1 <<< i) - 1)) # data_index(datamap, 4) = popcount(bits 0..3) = 1 -> entries[1]
F4.04 · one bitmap, one mixed array
A HAMT node mixes entries and child pointers in a single array.
F4.06.1 · two bitmaps, two packed arrays
Entries and children are separated and gap-free; popcount still finds any slot.
Next: cache-friendly iteration — what the packed entry array buys when you walk the whole map.
References
Primary sources for the CHAMP node layout, and where it connects in the course.
Sources
- Steindorfer & Vinju, “Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections” (OOPSLA 2015) — the CHAMP paper, DOI 10.1145/2814270.2814312.
- The Morning Paper, “CHAMP — optimizing hash-array mapped tries” (2015) — a walkthrough of the structure.