Dive C4.06.3

HAMT vs CHAMP

Same lookup depth, smaller node, one shape per map — and that last property is what the bus's registry is after.

A HAMT and a CHAMP both branch 32 ways on hash fragments, so they share the same O(log₃₂ n) lookup depth. The node is where they differ. A HAMT node carries one array sized to one bitmap, mixing entries and child pointers, and to stay shallow it tolerates nodes that hold a single entry. A CHAMP forbids that: two bitmaps, two packed arrays, and a canonical shape — for a given set of entries there is exactly one tree. That buys smaller nodes, contiguous entries, and cheap equality. This dive makes the comparison concrete and ties it to why the F# bus port keeps its registry ready for a CHAMP. Every // val it: echo came from dotnet fsi.

Compare the nodes Module hub

C4.06.3 · part 1

Same depth, a different node

The lookup walks the same number of levels in both, because both split the 32-bit hash into 5-bit fragments and branch on each. What changes is the node. A HAMT keeps one array, so it must store entries and child pointers together and distinguish them by the bitmap and a tag. A CHAMP keeps two arrays, so a node holds exactly its entries in one and exactly its children in the other. The CHAMP node is therefore smaller for the same contents, and — crucially — it never needs a node that wraps a single entry, because an entry can live inline in its parent.

// HAMT node: one bitmap, one array mixing entries and child pointers
type Hamt<'K,'V> =
    | HNode of bitmap: int * slots: HamtSlot<'K,'V>[]   // a slot is an Entry OR a Child

// CHAMP node: two bitmaps, two packed arrays — entries and children kept apart
type Champ<'K,'V> =
    | Leaf of hash: int * key: 'K * value: 'V
    | Node of datamap: int * nodemap: int * data: ('K * 'V)[] * nodes: Champ<'K,'V>[]

F#'s built-in Map is a balanced tree, not a HAMT or a CHAMP, so on .NET both are structures you build. The point of this dive is the difference between the two designs, and which one a persistent registry calls for.

C4.06.3 · part 2

One canonical shape

Because a CHAMP forbids single-entry nodes and packs every array, a given set of entries has exactly one shape. Equal maps are structurally identical trees, so equality and hashing can short-circuit on shared sub-trees, and a one-entry change touches only the path to it. F#'s Map carries the same value-equality property — two maps with the same contents compare equal whatever order the inserts arrived in — which is the behaviour a canonical CHAMP gives at the node level.

let a = Map.empty |> Map.add 1 "a" |> Map.add 2 "b"
let b = Map.empty |> Map.add 2 "b" |> Map.add 1 "a"

a = b   // val it: bool = true   (value equality, order-independent)

C4.05 · the HAMT

One array per node, single-entry nodes allowed; shape can depend on history, so equality must walk the whole tree.

C4.06 · the CHAMP

Two packed arrays, no single-entry nodes; one shape per set of entries, so equality short-circuits on shared sub-trees.

The same contents, two node shapes

The same three entries and one child, laid out as a HAMT node and as a CHAMP node. Toggle between them and the readout names the array count and what each cell holds. The HAMT mixes the four in one array; the CHAMP splits them into a 3-entry data array and a 1-child node array — fewer bytes for the same contents, and a shape fixed by the entries alone.

One node, two designs · select one

CHAMP node · two packed arrays · data[a→1, b→2, c→3] and nodes[●] · no single-entry node, so the shape is canonical and equality can short-circuit.

Same lookup, same contents — fewer bytes and a fixed shape. The canonical shape is the prize: it is what makes two snapshots comparable without a re-sort, which is exactly what a registry edited and re-read all day needs.

C4.06.3 · EchoMQ in F#

Why the bus's registry calls for CHAMP — and the swap-in discipline

The bus's registry is edited on every enqueue and claim, and read on every browse. A canonical shape lets two snapshots be compared cheaply, which is why the production registry is a branded CHAMP. The F# port keeps the registry behind a fixed surface so that compact form can take over without a caller change — the README states the discipline outright.

EchoMQ in F# · the swap-in discipline

From echo_fs/README.md, verbatim: “The in-memory Store stands in for the branded CHAMP / Valkey rows behind the same enqueue/claim/complete/retry/promote/reap surface, so the durable backing swaps in with no caller change”. The same README's module map lists the Valkey wire (Connector) as coming soon.

// callers touch the surface, not the backing — so the backing can change
let st, verdict = Store.enqueue id payload st     // today: Rows is a Map
let st, job     = Store.claim now leaseMs st        // next: a branded CHAMP, same call
let st, result  = Store.complete id token st       // then: Valkey via Connector, same call

Living status. The production Elixir bus (echo_data) is backed by a branded CHAMP. echo_fs does not implement a CHAMP yet — its Store.Rows is an F# Map standing in for it, kept behind the enqueue/claim/complete surface. The compact CHAMP, then the Valkey transport (EchoMQ.Connector), slot in behind that surface next.

Where this leads

That closes the CHAMP: the layout, the iteration, and the improvement over the HAMT, each tied to the registry the F# bus port keeps. The chapter goes on from here to branded identifiers and the single-writer actor that serialises edits to that registry — the parts that turn a CHAMP into the bus's data layer.

← C4.06.2 · Iteration ↑ C4.06 · CHAMP maps C4 · Algorithms & Data Structures →

Status — echo_fs is an in-memory model. The EchoMQ protocol — the Lua transitions executing on a Valkey wire — is not implemented (there is no Lua and no Valkey client in the code); that is the coming-soon transport (EchoMQ.Connector). This block shows how the model uses the structure, not a running bus.

References

Sources

FSharp.Core API reference — the Map module and its structural equality.
Microsoft — F# documentation — equality and comparison on discriminated unions and records.
Microsoft — .NET documentation — the cost model and memory layout the comparison rests on.
The F# Software Foundation — F# on the .NET runtime.

Related in this course

Elixir — E4.06 · CHAMP maps — the parity sibling, where the HAMT→CHAMP improvement is taught in its own course.
C4 — Algorithms & Data Structures — the chapter, and C4.05 the HAMT this measures against.
F# In Depth — the course home.
C4.06.2 — Iteration — the canonical walk this builds on.