Expand description
A persistent ordered map — the language’s Map[K, V].
§Why this exists
docs/19-phase-1-report.md §19.4 item 3: the fold was
O(events × rows) because map_insert cloned the whole accumulator. Arc<BTreeMap> makes
cloning the handle cheap and updating expensive, which is exactly backwards for a language
whose central construct is state = fold(f, init, events).
The Phase 1 report proposed uniqueness analysis — let the fold mutate in place when the previous
state is dead. That is worth having eventually, but it is the wrong first answer: it makes an
asymptotic guarantee depend on an optimisation firing. A persistent map gives O(log n) updates
unconditionally, with or without the analysis, on every backend. Uniqueness analysis then turns
O(log n) into O(1) amortised for the common case, which is a real but secondary win.
§Why it is written here rather than depended on
im and rpds are both MPL-2.0, which deny.toml does not allow. More to the point, a
persistent map is not a third-party concern for a functional language — it is Map[K, V], a
type in the surface language, and its performance characteristics are part of the semantics.
docs/01-vision-and-premise.md §1.5’s “we do not write a storage engine” is about substrates,
not about the standard library’s own data structures.
§Why this structure
Three requirements fix the answer, and it is worth writing down which:
- Persistent.
state = fold(f, init, events)keeps old states reachable — snapshots hold them,replay_torebuilds them, the differential harness diffs against them. So updating cannot mean mutating. - Ordered by key. Iteration order reaches the rendered page and the state digest, and §4.8’s replay harness compares both bit for bit.
- Keys are arbitrary
Values — not integers, so no Patricia trie; ordered by comparison, so no hash table.
(2) and (3) together mean a comparison-based ordered dictionary, whose worst case is
Ω(log n) per operation on information-theoretic grounds. O(log n) is therefore optimal and
the only question left is which balanced search tree. Three are plausible:
| scheme | height | len | used by |
|---|---|---|---|
| AVL | ≤1.44 lg n | O(n) | OCaml Map |
| red-black | ≤2 lg n | O(n) | Scala, Java TreeMap |
| weight-balanced | ≤2.4 lg n | O(1) | Haskell Data.Map, SML/NJ |
Weight-balanced wins here for a language-specific reason: map_len is a prim, so a program
may call it inside a view that already runs once per event. Every node carries its subtree size,
so len is a field read rather than a traversal. The same sizes give O(log n) rank/select if
indexing is ever added, and admit the join-based union/intersection/difference of Blelloch,
Ferizovic and Sun (2016) at the optimal O(m log(n/m + 1)) if those become prims.
A HAMT (Bagwell 2001; CHAMP, Steindorfer and Vinju 2015) would be a constant factor faster — depth ≤7 rather than ~2.4 lg n — but iterates in hash order, which violates (2); recovering key order would cost a sort on every render, and the digest would then depend on a hash function staying stable across compiler versions. It buys no asymptotic improvement, so it loses.
§Cost
| operation | time | fresh nodes |
|---|---|---|
get, contains_key | O(log n) | 0 |
insert, remove | O(log n) | O(log n) |
len, is_empty, clone | O(1) | 0 |
iter, keys, values | O(n) | 0 |
So a fold of E events over a map reaching n entries costs O(E log n) time, against the
O(E · n) — quadratic when every event adds a row — that copying cost. Live space is O(n)
nodes plus O(log n) per retained version: the path a superseded version rebuilt is freed by
its Arc the moment the old state is dropped.
The price of sharing is per-entry overhead: a node is key + value + usize + two Option<Arc>
plus the Arc header, roughly 3–5× a BTreeMap entry, which packs ~11 entries to a cache line
group. That is the trade — and it is repaid immediately, because the old code allocated a whole
copy of the map on every event.
The remaining constant-factor win is uniqueness: when the previous state is dead, the path could
be updated in place (Arc::get_mut — Clojure’s transients) for O(1) allocation. That is a
real improvement and it is not implemented here, because an asymptotic guarantee should not
depend on an optimisation firing.