Dive C4.06.2

Cache-friendly iteration

Contiguous entries walk in one straight sweep, in the same order every time — that is the payoff for the split.

Because a CHAMP keeps its entries in a single packed array, separate from child pointers, a walk reads them linearly, then descends into sub-nodes. There are no empty slots to test and no child pointers interleaved with the data, so the entry sweep stays tight in cache. The order is canonical: a function of the hash fragments alone, not of insertion history. F#'s built-in Map already gives the same canonical walk — sorted key order — and Map.fold / Map.toList are the idiomatic ways to take it. Every // val it: echo below came from dotnet fsi.

Walk a node Module hub

C4.06.2 · part 1

Entries are contiguous

A HAMT node holds one array sized to one bitmap, with entries and child pointers mixed together. Iterating it means testing each slot and branching on what it holds. A CHAMP node splits the two, so iterating a node is two straight sweeps: the data array first, then the nodes array. The data sweep touches only entries, laid out one after another, which is the layout a CPU cache rewards.

// a node's entries are contiguous — sweep them, then descend into children
let rec walk (acc: 'S) (step: 'S -> 'K -> 'V -> 'S) (node: Champ<'K,'V>) : 'S =
    match node with
    | Leaf(_, k, v) -> step acc k v
    | Node(_, _, data, nodes) ->
        let acc = data  |> Array.fold (fun a (k, v) -> step a k v) acc   // entries, in slot order
        nodes |> Array.fold (fun a child -> walk a step child) acc   // then descend
// val walk: acc:'S -> step:('S -> 'K -> 'V -> 'S) -> node:Champ<'K,'V> -> 'S

The entry sweep is a single pass with no bitmap test per cell, because a packed array has no empty cells. That is the whole reason the two kinds are kept apart.

C4.06.2 · part 2

The order is canonical

The slot of an entry is fixed by its hash fragment, so the array order is fixed too. Two maps holding the same entries iterate the same way, whatever order the inserts arrived in. F#'s Map is a balanced tree rather than a CHAMP, but it carries the same property — iteration is in sorted key order — and that is what makes Map.fold and Map.toList deterministic walks.

let rows : Map<string,int> =
    Map.empty |> Map.add "JOB0aaa" 1 |> Map.add "JOB0bbb" 2
// val rows: Map<string,int> = map [("JOB0aaa", 1); ("JOB0bbb", 2)]

rows |> Map.toList
// val it: (string * int) list = [("JOB0aaa", 1); ("JOB0bbb", 2)]

// one linear pass in key order
rows |> Map.fold (fun acc _ v -> acc + v) 0   // val it: int = 3

HAMT iteration

Entries and child pointers share one array, so a walk tests each slot and branches — interleaved reads.

CHAMP iteration

A contiguous entry sweep in canonical order, then descend — far fewer cache misses on every walk.

Walk the packed entries

Step through a CHAMP node's iteration. Each step lights the next entry in the packed data array and folds it into the running total, exactly as Array.fold would; after the entries, the walk descends. The readout names the entry visited, the accumulator, and where the walk is. Run it and the order is the same every time.

A linear sweep over the packed data array

Array.fold over node.data · not started · the walk visits entries in slot order, accumulating a total, then descends into sub-nodes.

Same entries, same walk, every time. A canonical order is not a nicety here — it is what lets a snapshot be compared against the next one without re-sorting, the property the persistent registry depends on.

C4.06.2 · EchoMQ in F#

Browsing the registry

An operator inspecting a queue browses its rows. The F# bus port exposes that as a scan over the pending ids, served in order with no auxiliary index — the canonical-walk property put to work.

EchoMQ in F# · Store.browse

In echo_fs/EchoMQ/Store.fs, the browse is a single scan of the ordered pending set. The source comment names the property: “Newest-first browse over the pending ids themselves (no second index)”.

// echo_fs/EchoMQ/Store.fs — "Newest-first browse over the pending ids themselves (no second index)."
let browse (n: int) (st: QueueState) : string list =
    st.Pending |> Set.toList |> List.rev |> List.truncate n

The ids are time-ordered and Base62 sorts as the integers do, so the id order is the mint order — the scan needs no second index. The rows themselves walk in key order from Rows: Map<string, Job>; a Map.fold over them is one canonical pass, the same sweep this dive showed.

Living status. Today the registry is an F# Map (a balanced tree) and the browse scans a Set; the production Elixir bus is backed by a branded CHAMP, whose contiguous nodes give the same canonical walk with better cache locality. echo_fs does not implement a CHAMP yet — the surface is kept ready, and the Valkey transport (EchoMQ.Connector) lands next.

Where this leads

Contiguous, canonical iteration is one of the two prizes the split buys. The last dive takes the whole comparison: the same lookup depth as the HAMT, a smaller node, and a canonical shape that makes equality and the bus's snapshot diffs cheap.

← C4.06.1 · The CHAMP layout ↑ C4.06 · CHAMP maps 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

FSharp.Core API reference — Map.fold, Map.toList, and Array.fold, the canonical walks.
Microsoft — F# documentation — recursion and pattern matching over a discriminated union.
Microsoft — .NET documentation — arrays and the CLR memory/cache model.
The F# Software Foundation — F# on the .NET runtime.

Related in this course

Elixir — E4.06 · CHAMP maps — the parity sibling, where cache-friendly iteration is taught in its own course.
C4 — Algorithms & Data Structures — the chapter, and C4.05 the HAMT this contrasts.
C4.06 — CHAMP maps — the module hub.
C4.06.1 — The CHAMP layout — the packed arrays this dive walks.