F4 · Persistent maps · module 6
CHAMP maps
A CHAMP — Compressed Hash-Array Mapped Prefix-tree — is the
compressed successor to the HAMT from F4.04. It keeps the same log₃₂ n
lookup, but lays each node out differently: instead of one array mixing entries and sub-nodes, a node holds
two bitmaps and two densely packed arrays — one for inline entries, one
for sub-nodes — with no empty slots.
That compression buys two things this course leans on: cache-friendly iteration, and a single canonical shape per map, which makes equality and snapshot diffs cheap. It is the structure under a persistent page registry, and the basis for the branded-CHAMP trie (F4.09) used as the data layer in the stack.
Two compartments, two bitmaps
datamap: 1 entry · nodemap: 1 sub-node
A free slot lands an entry in the data array; a collision promotes both into a sub-node, moving the bit datamap→nodemap.
Inside a CHAMP node
A node splits its 32 slots into two groups. The datamap bitmap marks the slots
holding inline key/value entries; the nodemap marks the slots holding child nodes.
Each kind lives in its own packed array, so there are never gaps to skip. Select an angle.
The angle · select one (8 of 32 slots shown)
role: two bitmaps, two dense arrays
in short: datamap + nodemap mark the present slots
The split is the whole idea. Keeping entries apart from sub-nodes, each packed with no gaps, is what makes a CHAMP smaller than a HAMT, quicker to walk, and canonical — the three dives take each consequence in turn.
Three deep dives
In order: how a node is laid out, why iteration is cache-friendly, and how a canonical shape makes equality and diffs cheap — each tied to the course’s persistent registry.
datamap and nodemap — and two packed arrays, with a slot’s position found by popcount.Advanced: why compression pays
A HAMT node carries a single array sized to its bitmap, mixing entries and child pointers; to stay shallow it tolerates nodes that hold a single entry. A CHAMP forbids that. By separating the two kinds and packing each, a node stores only what it has, and the tree has a canonical form: for a given set of entries there is exactly one shape. Smaller nodes and contiguous entries mean better cache behaviour on every walk; the canonical shape means structural equality and hashing can short-circuit on shared sub-trees.
The BEAM’s built-in map is HAMT-like, so CHAMP here is a structure you build rather than one the
runtime hands you — which is exactly what the stack does for its BrandedChamp
trie, a CHAMP whose keys are branded Snowflake ids. For a persistent page registry that is edited and
re-read constantly, the canonical shape is what lets two snapshots be compared cheaply — the same
instinct behind a LiveView diffing its assigns.
# a CHAMP node: two bitmaps, two packed arrays — no empty slots defmodule Champ.Node do defstruct datamap: 0, nodemap: 0, entries: {}, nodes: {} end # HAMT: one array mixes entries + child pointers, sized to a single bitmap # CHAMP: entries and children are separate and packed → canonical, cache-friendly
F4.04 · a 32-way HAMT
One bitmap, one array per node, mixing entries and children.
F4.06 · the compressed CHAMP
Two bitmaps, two packed arrays — canonical, smaller, faster to walk.
Start with compressed node layout, then cache-friendly iteration, then canonical equality. Predecessor: F4.05 — Hash Array Mapped Tries. Next module: F4.07 — Branded CHAMP maps, where the keys become branded Snowflake ids and the trie turns into the stack’s data layer.
References
Primary sources for this lesson, 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 HAMT compression this lesson builds on.
- The Morning Paper — CHAMP summary — a walkthrough of the OOPSLA 2015 result.