# Persistent Data Structures
Deft's lists, maps, sets, and tagged maps are persistent in the
Clojure sense: an operation returns a new value, the old value stays
valid and unchanged, and the two versions share most of their memory.
Two structures do the sharing — a 32-way vector trie for lists and
sets, and a CHAMP tree for maps — and one operator, `<<`, steps outside
the pure model to accumulate into a binding in place. This entry covers
the representation, the copy-on-write rules, and exactly what `<<` does
differently. For the user-facing API see
Collections; for allocation and GC
mechanics see Memory Management.
## Value Semantics and Structural Sharing
Every collection value is a pointer to an immutable heap object. A verb
like `append`, `assoc`, or `dissoc` builds a new object that shares
every node the change did not touch:
def xs @{ 1 2 3 } def ys $xs set zs [append $xs 4] # zs is @{ 1 2 3 4 }, shares $xs's trie $xs # => @{ 1 2 3 } — unchanged $ys # => @{ 1 2 3 } — the same value, still valid
Three properties follow from this design plus the non-moving GC
described in Memory Management:
- Old versions stay usable. Anything holding a prior version keeps
reading it; there is no invalidation, no copy-on-read, no locks.
- Memory tracks the delta. A version costs the nodes along its
changed path, not a copy of the collection.
- No write barriers. The collector never moves objects, so a shared
node can be read by whoever holds it — including another runtime's
thread reading a rooted value (values still cross heaps only by
copy; see Execution Model).
Mutable arrays (`[array ...]`) are the deliberate escape hatch: flat,
O(1) `aset`, no sharing. Everything below is about the persistent
collections.
Equality is per-kind: lists and sets compare element-wise, while maps
(and tagged maps) compare by identity — two structurally equal maps
built separately are not `==`, whereas the same value read twice is.
## Lists: a 32-Way Vector Trie
`@{ ... }` builds an `ObjVector`. The docs call it a list; the shape is
Clojure's persistent vector:
- count — element count (u32).
- shift — trie depth in bits; 0 for vectors of 32 or fewer, then
5, 10, ... Each trie level consumes 5 index bits, so nodes are
32-slot arrays (`VEC_BITS = 5`).
- root — the trie root, or null when everything fits in the tail.
- tail / tail_len — the last 1–32 elements, stored flat outside
the trie for fast appends.
### Lookup
For `idx`, the tail starts at `(count - 1) & ~31` once count reaches
32; an index at or past that offset is a direct tail read. Otherwise
the index is walked down the trie five bits at a time —
`(idx >> level) & 31` — to a leaf. That is O(log32 n), at most seven
node reads for a 32-bit count.
### Append
`[append $xs v]` is the only vector verb that copies just a path, and
it has two cases:
1. Tail has room (`tail_len < 32`). Allocate a new vector shell and
a new tail array of `tail_len + 1` elements, copying at most 31
values. The trie root is shared verbatim.
2. Tail is full. Copy the old tail into a fresh leaf node, splice
it into the trie by copying only the nodes on the insertion path
(`vecPushTail`), and start a new one-element tail. Sibling subtrees
are shared with the old vector. If the trie is already at capacity
for its depth, a new root level is added (`shift += 5`).
So a single append costs a path copy — O(log32 n) — and repeated
appends amortize to O(1) each, since only one append in 32 pays for
the trie.
### Not Every Verb Shares
Only `append` path-copies. `set-nth`, `insert-nth`, `remove-nth`,
`slice`, `reverse`, `sort`, `flatten`, and the rest materialize a flat
buffer and rebuild the trie from scratch (`makeVector` →
`ObjVector.create`), which is O(n) with no sharing. That is fine for a
one-off rewrite, but a loop of `set-nth` is O(n²) — accumulate with
`<<` or a transducer instead.
### Nodes and GC
Each trie node is one fixed-size object: a `VecTrieNodeHeader` with 32
raw u64 slots, a generation stamp, a per-cycle `valid_gen` guard, and
an intrusive-list link. Leaf slots hold NaN-boxed `Value` words.
All nodes are linked into `heap.vec_trie_nodes`. The sweep frees dead
nodes by walking that one list rather than recursing through every
vector (shared nodes would otherwise risk double frees), while the
mark phase walks each live root and stamps visited nodes with the
cycle's generation. The `valid_gen` stamp, refreshed on every header
at cycle start, lets lookups and copies detect a stale leaf pointer
and return nil instead of dereferencing freed memory — a defense that
turns an upstream use-after-free into a leak rather than a crash.
## Maps: CHAMP
`%{ ... }` builds an `ObjMap` backed by a CHAMP tree (Compressed
Hash-Array Mapped Prefix-tree), the evolution of HAMT. Keys are hashed
to 64 bits and consumed five bits per level, so a lookup descends at
most 13 times.
### Shape
Each node carries two 32-bit bitmaps — `datamap` for inline key/value
pairs and `nodemap` for child pointers — followed by a single packed
content array: data pairs first, then child pointers. That layout is
why CHAMP beats plain HAMT on lookup: the common case (a key sitting
inline) never leaves the node's cache line. Node capacity is rounded up
to the next power of two (minimum 2), which keeps growth within one
allocator size class. Two keys whose hashes agree through the final
shift are stored together in a collision node (`is_collision`), scanned
linearly.
### Lookup and Update
- `get` — test the slot bit in `datamap`, compare the inline key, or
descend via `nodemap`; missing slot → nil. O(log32 n).
- `assoc` — overwrite an inline pair, or (on a hash-prefix collision
with a different key) push both keys down into a child, creating one
if needed. Only nodes on the path are copied; every untouched child
is shared with the old map. A new map shell is always allocated, so
the old map is untouched.
- `dissoc` — remove the pair (`ObjMap.without` internally); a child
that shrinks to a single entry is inlined back into its parent, and a
child with no entries is dropped. If the key is absent, the same
map value is returned.
The data/child transitions keep the shape canonical: for a given key
set the layout is determined by the hashes, so re-`assoc`ing an
existing key only rewrites its value slot, and `dissoc` collapses
children eagerly instead of leaving sparse nodes behind.
### Keys and Hashing
`Value.hash()` routes by kind:
| Key kind | Hash |
|---|---|
| Number, boolean, nil | splitmix64 mix of the NaN-boxed bits |
| String | Wyhash of the bytes, memoized on the string object |
| Keyword | Wyhash, salted so `:ok` and `"ok"` land in different slots |
| Other objects | identity (pointer) |
Keys compare by content (`Value.eql`), so any immutable value can be
a key. At the `get`/`assoc`/`dissoc` boundary a string key is
canonicalized to an uninterned dynamic keyword through a bounded
128-entry memo — see Memory Management for why
those are not added to the permanent intern table.
### Iteration Order
`keys`, `values`, `entries`, and direct `for`/`each` iteration walk the
trie: hash order, stable for a given key set, but not insertion
order. Canonical writers sort explicitly where stable output matters —
`theme/save` sorts keys within each map — so don't rely on trie order
crossing a file boundary.
### Allocation and Transients
Node allocation checks a per-bucket free list, then carves from a
64 KB bump slab, then falls back to the allocator. All nodes are
linked into `heap.champ_nodes`; the sweep recycles dead nodes onto the
bucket free lists instead of returning them to the allocator, which
keeps reuse within the owning heap (see
Memory Management). Map shells come from a
dedicated pool.
`TransientMap` is the mutable builder:
- It starts by allocating an edit token and sharing the persistent
root.
- The first write through a node owned by a different token copies
that path and stamps it with the token — copy-on-write. Later writes
through token-owned nodes mutate in place, and content grows in
place while it stays within the node's bucket.
- `persistent()` allocates a shell, hands over the root, and frees the
token — O(1) freeze, no rebuild.
Map literals are built this way (`ObjMap.create` loops a transient),
as are statement-position `[assoc $m k v]` (fused to `assoc_local`),
the map branch of `<<`, and map accumulators in `reduce`/`into` (the
transient is installed in `g_reduce_transient` and intercepted by
`nativeAssoc`).
## Sets, Tagged Maps, Metadata
Sets reuse the vector layout: `makeSet` builds an `ObjVector` and
flips the shell's kind to `.set`. The set literal dedups as it builds,
and `in?`, `union`, `intersection`, `difference`, and the subset
predicates scan the backing vector linearly. Two implementation
consequences: set equality is positional (same members in a different
order compare unequal), and because the `.set` flag lives on the shell
while the append/transient path builds a plain vector shell, `<<` and
`append` on a set return a list. Use `into ^{}` or `union` when
the result must stay a set.
Tagged maps (`%Tag{ ... }`) are a thin wrapper: an `ObjTaggedMap`
holds an `ObjMap` plus a name buffer up to 48 bytes. Operations unwrap,
change the map, and re-wrap (`rewrapTagged`), so the tag adds no
triework.
Metadata (`with-meta` / `meta`) is a side channel: maps, tagged
maps, vectors, sets, strings, and keywords carry an optional `meta`
pointer. Attaching metadata copies only the shell and shares the
payload, and the payload's equality semantics are unchanged — a
meta-carrying keyword or string still matches plain lookups.
## The `<<` Operator
Everything above describes pure values. `<<` is the exception: it
appends to a binding in place, bypassing the persistent copy when
it can. `[append $xs v]` remains the pure sibling:
def build {|| def out @{} for x in @{ 1 2 3 } { $out << ($x * 2) } # one transient for the loop $out } [build] # => @{ 2 4 6 } [append [build] 8] # pure: a new value, receiver unchanged
### Where the Mutation Lives
The compiler lowers `<<` by receiver position, not by runtime type:
| Receiver | Lowered to | Mutation target |
|---|---|---|
| Function-local `$xs` | `append_local` (captured locals: `append_boxed`) | a per-frame transient on that slot |
| Top-level / global `$xs` | `[append $xs v]` + store back to the namespace | the binding (aliases keep the old value) |
| Literal, field access, call result | a plain `append` call | none — a new value is returned |
For a local, the VM keeps a lazily created `transients` array parallel
to the frame's locals. The first append on a slot wraps the current
value:
- a list gets a `TransientVector` — a flat copy with geometric growth;
- a map gets a `TransientMap` — shares the root, copy-on-write.
Subsequent appends mutate the wrapper, so a loop accumulates without
touching the trie. The wrapper is frozen back into the local when the
local is read, when the function returns, or when a coroutine
suspends (`flushFrameTransients` — which is why `$xs << 1; [await`
...]; $xs << 2` does not lose the first append).`
The common shapes are fused at compile time: `set x ($x << y)` stays
on the append fast path, statement-position `$buf << [str ...]`
becomes a single `append_format_str` opcode, and statement-position
`[assoc $m k v]` becomes `assoc_local`. A chain `$xs << a << b << c`
is folded into sequential appends against the bottom local, with one
freeze for the whole chain.
Aliases are safe. The transient starts from a copy (vector) or
copy-on-writes any node it touches (map), so a persistent value held
elsewhere is never modified — only the binding moves to a new value.
Captured locals are boxed, so appends through a closure are visible to
sibling closures, and the freeze writes the box's value.
### What It Evaluates To
Because `<<` is an operator over a binding, its value depends on the
form. The compiler is explicit about it:
| Form | Evaluates to |
|---|---|
| `$xs << v` as a discarded statement | nothing (no value is left on the stack) |
| `($xs << v)` in expression position, one append | `v` — the appended value |
| `($xs << a << b)` chain in expression position | the mutated collection |
| `set xs ($xs << v)` | `v` (and `$xs` is mutated) |
| `set xs ($xs << a << b)` | the mutated collection |
| `(@{} << v)` — non-local receiver | a new list, `@{ v }` |
Two caveats: the top-level/global store-back covers only the innermost
append, so chains on a global binding should be separate statements;
and because a single append evaluates to the value appended, code that
wants the collection should read the binding or use `[append ...]`.
### Cost
- Same-frame accumulation (`for`/`while`, inlined into the frame):
amortized O(1) per append for the vector transient, then one O(n)
rebuild when the transient is frozen. This is the shape `<<` exists
for.
- Closure accumulation (`each`/`map` bodies): each call is a
separate frame, so the captured accumulator is frozen and re-copied
on every return — effectively O(n²) for n appends. Prefer `for`/
`while` loops, `reduce`, or `transduce` for large accumulations.
- One append to a large list: the transient copies the whole list
up front, where `[append ...]` would path-copy O(log32 n). `<<` pays
off when appending repeatedly, not once.
## Quick Reference
| Question | Answer |
|---|---|
| Are `@{}`/`%{}`/`^{}` mutable? | No — operations return new values; the old value is unchanged |
| Does `[append $xs v]` change `$xs`? | No — use `$xs << v` to update the binding |
| Does `$xs << v` change other references to the old value? | No — the transient copies/copy-on-writes; only the binding moves |
| How is `<<` different from `append`? | It fuses to transient opcodes for locals and mutates the binding; its expression value differs per form (see table) |
| Is `[append $list v]` O(1)? | O(log32 n) — path copy; amortized O(1) over 32 appends |
| Is `$list << v` faster? | While accumulating, yes; the freeze at read/return is O(n) for lists, O(1) for maps |
| Does `assoc` share structure? | Yes — path copy only; untouched nodes are shared |
| Does `set-nth` share structure? | No — full flat rebuild, O(n) |
| Are map keys insertion-ordered? | No — trie/hash order, deterministic but not insertion |
| Does `<<` keep a set a set? | No — it returns a list; use `into ^{}` / `union` |
| Why didn't my `each` accumulation scale? | Each closure call freezes the transient; use `for`/`while` or `transduce` |