jonnifyfsharp

Module C4.05

Hash array mapped tries

Spread a hash table over a tree, branch thirty-two ways at a time, and the depth all but vanishes.

C4.04 sent a key through a hash to a slot in one flat table. A HAMT — a hash array mapped trie — spreads that idea over a tree. It consumes the key's hash a few bits at a time, branching up to 32 ways at each level, so a node is a small bitmap plus one packed array, and the depth is about log₃₂ n — roughly four levels for millions of keys. This module re-derives the structure in F#, at parity with the Elixir course's E4.05. One thing has to be said plainly first, and the whole module holds to it: F#'s built-in Map is an immutable balanced search tree, not a HAMT. The HAMT is taught here as a technique — the persistent-map design Elixir's Map and Clojure use — and F#'s choice of a balanced tree is named as the real trade it is. Every F# snippet across the three dives was verified in dotnet fsi.

The three dives Back to C4 · Algorithms

One node: a bitmap and a packed array

The HAMT's whole compactness comes from one trick at the node. A node has room for 32 slots, but it does not store 32 cells. It stores a 32-bit bitmap — a bit set for each occupied slot — and a single packed array sized to the number of set bits, so an empty slot costs nothing. To find a slot's place in that array, count the set bits below it: the popcount of the lower bits is the array index. One CPU instruction per level.

Insert a key on the interactive below. The bitmap flips a bit on, the packed array grows by exactly one cell at the popcount index, and the readout shows the arithmetic. Every value is computed by a pure function over a fixed eight-slot bitmap — the static diagram and table stand on their own without scripting.

A set bit maps to a packed slot by popcount (8 of 32 slots shown)

bitmap 8 of 32 slots 0123 4567 array index(slot) = popcount(bits below slot)
bitmap 0b00100100 · 2 slots set. Each set bit owns one packed cell; its array index is the popcount of the bits below it. Slot 2 → array[0], slot 5 → array[1].
Without JavaScript: the initial node, slots 2 and 5 set
bitmap0b00100100 (2 bits set)
slot 2popcount(below) = 0 → array[0]
slot 5popcount(below) = 1 → array[1]

A bitmap plus a packed array turns a 32-wide node into a compact one, and a few hash bits per level keep the tree shallow. The three dives take the trie shape, the descent by hash, and the way an edit shares structure in turn — and name, throughout, what F#'s standard library does instead.

F#'s Map is a balanced tree, not a HAMT

The point most worth fixing before the dives: F#'s Map is the standard library's immutable persistent map, and it is implemented as a balanced binary search tree (an AVL tree), not as a HAMT. So this module teaches the HAMT as a design you would build by hand or pull from a library — never as a description of Map. The two are kin: both give O(log n) lookup and both share structure on update, which is what makes either a good persistent map. They differ on two axes, and the difference is a genuine engineering trade.

HAMT · the technique

Keys are placed by hash; nodes branch 32 ways, so depth is near-constant (~log₃₂ n). The order of iteration is hash order. The design Elixir's Map and Clojure use.

F#'s Map · the choice made

Keys are kept in sorted order in a balanced tree; depth is O(log n) binary. Iteration is in key order, and range queries come for free. The trade F#'s standard library took.

The discipline this module holds to: it never claims F#'s Map is a HAMT, and never claims the echo_fs port ships a HAMT — echo_fs uses the stdlib Map (a balanced tree). The HAMT is the technique; the balanced tree is what F# chose; both are persistent maps.

The three dives

Read them in order. The first builds a plain prefix trie keyed by a key's digits — the trie shape, before any hashing. The second turns it into a HAMT: a node is a bitmap plus a packed array, indexed by slices of the key hash, with the index found by popcount. The third reads how an update shares structure, and verifies on F#'s own Map that the old version survives untouched. Each dive carries an EchoMQ in F# block tied to the bus's job registry.

live module hub built dive ready soon specified
C4.05.1built

Prefix tries

A trie keyed by the digits of a key; shared prefixes share the path. The shape a HAMT generalises.

  • the triestore keys by their pieces, before any hashing
C4.05.2built

The HAMT

A bitmap + a packed array per node, indexed by slices of the key hash; index-by-popcount; depth ~log₃₂ n.

  • the nodethe high-fan-out persistent map a registry calls for
C4.05.3built

Structural sharing

Why each update keeps the old map intact and shares structure — the property a balanced tree and a HAMT both give.

  • sharingverified on F#'s own Map: the old version survives

EchoMQ in F#

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.

The F# EchoMQ port (echo_fs) keeps each queue's job rows in a persistent map. That registry is the structure this module is about — the part of the bus a HAMT, or its compressed successor, would back. The honest framing holds: today the registry is a plain F# Map; the production Elixir bus backs the equivalent registry with the echo_data HAMT/CHAMP family; and because the port keeps the same surface, a HAMT/CHAMP swaps in behind it later with no caller change.

EchoMQ in F#

The job registry as a persistent map

The queue state holds its rows in a Map keyed by branded id. Quoted verbatim from echo_fs/EchoMQ/Store.fs:

/// One queue's state.
type QueueState =
    { Rows: Map<string, Job>
      Pending: Set<string>
      // id -> due-at (ms), id -> lease deadline (ms), ... }

A registry read is a map lookup; an admission is a non-destructive map write. The surface is get/add over Rows — the same surface whether the map is a balanced tree (today) or a HAMT/CHAMP (the Elixir bus's backing):

let get id (st: QueueState) = Map.tryFind id st.Rows   // a lookup
let add (row: Job) (st: QueueState) =                   // a non-destructive write
    { st with Rows = st.Rows.Add(row.Id, row) }
// val get : string -> QueueState -> Job option

The F# EchoMQ keeps its job registry in EchoMQ.Store.Rows today — an immutable F# Map (a balanced tree), in the in-memory core (echo_fs/EchoMQ/Store.fs — built and tested). The HAMT/CHAMP backing and the Valkey transport EchoMQ.Connector land next; the get/add surface holds across the swap.

A registry calls for a persistent map: cheap lookups, non-destructive writes, a prior snapshot kept for free. The HAMT is one way to build that map; F#'s Map is another. The dives take both.

References

Sources

Related in this course