F4.06 · part 3 of 3
Canonical equality
Because a CHAMP forbids redundant nodes — entries are inlined as high as they can go, and never share a slot with children — a given set of entries has exactly one tree shape. That canonical form is what makes equality cheap: two equal maps are structurally identical, so a comparison can short-circuit on shared sub-trees, and a hash can be cached per node. The same sharing makes a one-entry change touch only the path to it.
Two registry snapshots as CHAMP maps. Select what to read — the canonical shape, an equality check, or a one-entry diff.
One shape, cheap comparison
Equal maps are the same tree; an unequal pair differs only where its entries differ. Select the canonical shape, a full equality test, or a single-entry diff between two snapshots.
What to read · select one
role: one canonical shape per map
result: equal maps are identical trees
A canonical shape collapses equality from “compare every key” to “compare the trees,” and a change to one entry leaves the rest of the tree shared. Cheap equality and cheap diffs are the same property seen twice.
Advanced: snapshots & the branded trie
On the BEAM, == already compares maps by contents, but for a hand-built persistent
map the canonical shape is what keeps that comparison fast: equal sub-trees can be the same term in memory,
so equality and a cached per-node hash short-circuit instead of re-walking every key. Structural sharing
then turns versioning into a cheap operation — each edit yields a new root that reuses every untouched
node, so keeping a history of registry snapshots costs only what actually changed. That is precisely the
shape of the stack’s BrandedChamp trie, whose keys are branded Snowflake ids,
and it is where F4.07 picks up: the same CHAMP, keyed by ids like PGE0NbWMtkolM0
that double as cross-system pivots.
# canonical form: equal maps are structurally identical v1 = Registry.snapshot() v2 = Registry.put(v1, "/elixir/algorithms/champ", page) v1 == v1 # true — same tree v1 == v2 # false — differ on one path only # structural sharing: v2 reuses every untouched node from v1 # a history of snapshots costs only the changed sub-trees
F4.06.1–2 · compact, canonical nodes
Packed entries and one shape per map.
F4.07 · the branded CHAMP
The same trie, keyed by branded Snowflake ids — the stack’s data layer.
That completes F4.06: a CHAMP packs each node into two arrays, walks them cache-friendly, and keeps one canonical shape so equality and diffs are cheap. Next module: F4.07 — Branded CHAMP maps, where the keys become branded Snowflake ids and the trie becomes the cross-system data layer — the close of the chapter spine.
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: canonicalisation, the compact node, and cheap equality.
- Bagwell, “Ideal Hash Trees” (2001) — the HAMT the CHAMP refines.