jonnifyfsharp

Dive C4.06.1

The CHAMP layout

Two bitmaps, two packed arrays, no empty slots — and a count of bits is all it takes to find a key.

A CHAMP 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. A slot's position in its array is the population count of the set bits below it — popcount(map & (bit - 1)). This dive models a node in valid F# and shows the index math; every // val it: echo was produced by dotnet fsi.

Build a node Module hub
C4.06.1 · part 1

Two compartments, two bitmaps

The shape is a discriminated union. A Leaf holds a single hashed key/value; a Node holds the two bitmaps and the two packed arrays. The bitmaps and the arrays stay in step: the number of set bits in datamap is exactly the length of the data array, and likewise for nodemap and nodes. There is no slot in either array that does not have a set bit behind it.

// a CHAMP node: two bitmaps, two packed arrays — no empty slots
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>[]

let empty<'K,'V> : Champ<'K,'V> = Node(0, 0, [||], [||])
// val empty<'K,'V> : Champ<'K,'V>
datamap
a 32-bit bitmap; bit i set means slot i holds an inline key/value entry.
nodemap
a second 32-bit bitmap; bit i set means slot i holds a child sub-node.
data
the packed entries, in slot order — one per set datamap bit, no gaps.
nodes
the packed sub-nodes, in slot order — one per set nodemap bit, no gaps.

A slot is either an entry, a sub-node, or empty — never two at once, so a given bit is set in at most one of the two bitmaps. That invariant is what keeps the layout compressed and canonical.

C4.06.1 · part 2

popcount is the index

Because the arrays are packed, a slot number does not address an array cell directly. The index is the number of set bits below that slot: mask off the higher bits with bit - 1, then count what is left. The CLR exposes this as a single instruction through System.Numerics.BitOperations.PopCount, so the lookup costs a mask and a popcount, not a scan.

let popcount (x: int) = System.Numerics.BitOperations.PopCount(uint32 x)
let dataIndex (datamap: int) (bit: int) = popcount (datamap &&& (bit - 1))
// val popcount: x: int -> int
// val dataIndex: datamap: int -> bit: int -> int

// datamap = 0b100100 (slots 2 and 5 hold entries); the entry at slot 5:
dataIndex 0b100100 0b100000   // val it: int = 1   (one entry sits before slot 5)
The same function indexes the nodes array against nodemap. One masked popcount per level is the whole cost of finding where a key lives in a node.

Build a node, slot by slot

Set a slot's datamap bit and watch the packed data array grow. The readout names the bit you set, computes dataIndex for it, and shows where it lands in the array. A slot that is already set is left alone — the array never gains a gap. Eight of the thirty-two slots are shown.

A CHAMP node's datamap and packed data array

datamap (8 of 32 slots) slot 0 slot 2 slot 5 data array (packed, in slot order) data[0] data[1] datamap = 0b00100100 · 2 entries packed · pick a slot to set a bit
datamap = 0b00100100 · popcount = 2 · the packed data array holds 2 entries, in slot order with no gaps.

The bitmap is the directory; the array is the storage. A masked popcount turns a slot number into an array index, and because the array is packed in slot order it has the same shape every time the same keys are present — the canonical form the next dives lean on.

C4.06.1 · EchoMQ in F#

The registry a queue needs

A queue needs a registry: every job's row, reachable by its identity. That registry is a branded-key→row persistent map — exactly what a CHAMP is. The F# bus port, echo_fs (the skeleton of the Elixir echo/apps/echo_mq bus), declares it.

EchoMQ in F# · Store.Rows

In echo_fs/EchoMQ/Store.fs, a queue's state holds its rows as a persistent Map keyed by the branded id — the source comment says it plainly: “Rows are a Map keyed by branded id”.

// echo_fs/EchoMQ/Store.fs
type QueueState =
    { Rows: Map<string, Job>     // the branded-key → row registry
      Pending: Set<string>       // ids awaiting a claim, in mint order
      // ... Schedule, Active, Dead, Paused, Completed, Failed }

// idempotent admission writes the row and adds the id to pending
let enqueue (id: string) (payload: string) (st: QueueState) =
    if st.Rows.ContainsKey id then st, Admission.Duplicate
    else { st with Rows = st.Rows.Add(id, Job.create id payload) }, Admission.Enqueued

That Rows: Map<string, Job> is an F# balanced tree today. It stands in for the production branded CHAMP: the enqueue/claim/ complete surface is what callers touch, and the durable backing sits behind it.

Living status. The production Elixir bus is backed by a branded CHAMP; echo_fs does not implement a CHAMP yet — its Store.Rows is a Map standing in for it. The compact CHAMP and the Valkey transport (EchoMQ.Connector) land next, behind the same surface.

The CHAMP node

A datamap/nodemap pair and two packed arrays, indexed by popcount.

The bus registry

The branded-key→row map a queue keeps — a Map today, the compact CHAMP behind the same surface next.

Where this leads

The layout is the foundation. The next dive walks it: because entries are contiguous and separate from child pointers, iteration is a straight sweep in canonical order. The third weighs the whole CHAMP against the HAMT it compresses.

↑ C4.06 · CHAMP maps C4.06.2 · Iteration → C4.06.3 · HAMT vs CHAMP

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

Related in this course