Immutable Sequences and Structural Sharing in Radix-Balanced Vectors

An immutable array cannot be updated in place, because every existing reference must keep observing the old contents. The naive immutable array copies the whole buffer on each write: appending n elements costs Θ(n²), and an update costs Θ(n) space. A radix-balanced vector gets the same interface with Θ(log n) time per update and Θ(log n) space per version, by turning the contiguous array into a shallow tree of fixed-arity nodes and copying only the path from the root to the changed leaf.

From index to path

The structure is a tree in which every internal node holds exactly 32 children, and the element index is decomposed into base-32 digits that select the child at each level. The lowest five bits select the slot within a leaf; the next five select the leaf within its parent; and so on. Because 32 is a power of two, the decomposition is a shift and a mask rather than a division, and the branching factor matches the cache-line budget of a pointer array: 32 pointers of 8 bytes is 256 bytes, four lines, so a node’s children occupy a small, fixed footprint. The same decomposition of a fixed-width key into radix digits underlies the hash array mapped trie, where the digits are taken from a hash of the key instead of from its position in a sequence.

/* Index a persistent vector: 32-way branching, five bits per level. */
static inline void *vec_get(const node *root, size_t i, unsigned shift) {
    const node *n = root;
    while (shift > 0) {
        n = n->child[(i >> shift) & 31];
        shift -= 5;
    }
    return n->child[i & 31];
}

For 32-way branching, a tree of depth d holds up to 32^d elements: 32 at depth 1, 1024 at depth 2, 32768 at depth 3, about a million at depth 4, and about 33 million at depth 5. Since each level costs one dependent load, indexing a 33-million-element vector takes five loads. A flat array takes one. That is the entire cost of the representation: four extra pointer dereferences, each of which must be in cache for the access to be cheap.

The comparison with a balanced binary tree is not incidental. A binary tree over the same number of elements has depth around 25, so indexing costs 25 dependent loads rather than five. The wide node also spends its space on pointers rather than on keys: 32 pointers of 8 bytes fill 256 bytes, four cache lines, and a lookup at that level touches the one line holding the needed pointer. A narrower node would fit a whole level in fewer bytes but would need more levels, and the number of dependent loads is the cost that dominates, so the branching factor is pushed up until the node’s footprint stops fitting in a handful of lines. Thirty-two is the usual compromise: it is the largest power of two whose pointer array still spans only four lines, and its five-bit digit makes the index arithmetic a shift and a mask.

What an update copies

Updating element i copies the root, then the child on the path to i, then that node’s child, and so on to the leaf. At depth d that is d nodes of 32 pointers each: 256 bytes per node, so 1 KiB for a depth-4 vector. The remaining nodes are shared with the previous version by pointer.

The consequence is that versions form a tree of their own, with sharing. A program that keeps a version per step of an algorithm and updates one element per step holds, after k updates, the original vector plus k paths of d nodes each. For a vector of a few million elements the depth is 4 and each path is about 1 KiB, so the total is proportional to k and to the depth, and the depth grows only when the length crosses the next power of 32. Copying the flat array would have cost k times the array’s size. This is the property that makes the structure usable for versioned state, undo logs, and any algorithm that needs to backtrack by restoring a previous value rather than by replaying inverse operations.

The cost appears when the versions are not retained. If only the newest version is needed, the structure has paid for copying a path where an in-place write would have cost one store, plus it has left garbage for the collector. A persistent vector used as a mutable array is strictly worse than an array; the representation only earns its keep when old versions are read after new ones are created.

The tail: keeping appends off the tree

Appending is the common operation, and a pure tree append would copy a path on every call. The standard optimization keeps the last, partially filled leaf outside the tree as a separate reference called the tail. Appending writes into the tail’s next free slot and returns a new vector that shares the tree and points at a copy of the tail with one more element.

A tail holds up to 32 elements, so 32 of every 33 appends copy only the tail — 32 pointers, 256 bytes — and leave the tree untouched. The thirty-third append finds the tail full, pushes it into the tree as a leaf, allocates a fresh empty tail, and copies a path to install the new leaf. The amortized cost per append is therefore a small constant plus one path copy per 32 appends, which is the same geometric argument as a growable array’s doubling with a much smaller constant and no element copies at all.

The tail also changes the index arithmetic. An element at index i is either in the tail, if i is at or beyond the offset where the tail begins, or in the tree at the same index with the tail’s contribution excluded. The check is a comparison against a precomputed offset derived from the length, and the tree lookup then uses a shift derived from the tree’s depth rather than from the total length. Getting this arithmetic wrong produces a vector that is correct for the first 32 elements and wrong afterwards, which is why the boundary is the first thing to test.

Relaxed nodes and the size table

A fixed 32-way tree with complete leaves indexes in constant time per level. It also wastes space at the boundaries: a vector of 33 elements has a root, a full leaf, and a tail, and a vector of 1025 has a partially filled leaf at the end of the tree. More importantly, operations that insert or remove in the middle must preserve the fixed-width invariant, and rebalancing a fixed-arity tree after a removal is awkward.

The relaxed radix-balanced tree stores, in each internal node, a small table of cumulative sizes for its children. A child may then hold fewer than 32 elements without breaking the index computation: the lookup finds the child by comparing the index against the cumulative boundaries rather than by extracting a digit. For a node with c children the table has c entries, and the search is a linear or binary scan over at most 32 numbers, all in one or two cache lines.

The size table costs memory per node — one size field per child, so a full node holds 32 pointers plus 32 sizes rather than 32 pointers alone. With 8-byte pointers and 4-byte size fields that is 384 bytes, six cache lines, against 256 bytes and four lines for the plain node; with single-byte counts, as the RRB paper uses, it is 288 bytes, which straddles a fifth line. The table also costs time per level, since the lookup is a search rather than a shift. In exchange, insertion and removal in the middle become O(log n) with a single path copy, and the tree stays dense because nodes are merged and split only when they cross a fill threshold. The variant is what makes a persistent sequence usable as a general list rather than as an append-only vector.

Concurrency and the absence of invalidation

Because a version is never modified after it is published, a reader holding a reference to a version can traverse it while another thread derives a new version from it. There is no window in which the reader observes a half-written node, and no need for a lock on the read path. The only synchronization required is on the publication of the new root, which is a single reference store.

This property is why persistent sequences appear in concurrent systems as the state held by a compare-and-swap loop: a thread reads the current root, computes a new version, and attempts to install it if the root has not changed. A failed attempt discards the computed version and retries. The work of a failed attempt is wasted, which is the cost of the approach under contention, but no reader is ever blocked.

The garbage collector becomes part of the cost model. Old versions that are no longer reachable are reclaimed; versions retained by a long-lived reference keep their shared subtrees alive. A structure with heavy sharing has a retention pattern that is hard to reason about from the outside: a single retained element can pin a path to the root, and through the root, nothing else — the sharing is downward, so a retained leaf keeps its ancestors, not its siblings’ subtrees. That direction of retention is what makes the space bound per version proportional to the depth rather than to the width.

Where the structure is the wrong answer

Three conditions argue against it.

Mutable use. If no old version is ever read, the path copies are pure overhead against an in-place array. A vector used as a scratch buffer should be a std::vector, a slice, or a Vec, not a persistent one.

Sequential scans of the whole sequence. Iterating a persistent vector walks the tree and pays the node indirection at every 32-element boundary. A flat array’s scan is one stream; the vector’s is a sequence of short streams with pointer chases between them, and the prefetcher has less to work with. The cost is small per element but it is present in every full traversal, which is why the flat layout in Sequential Scans, Hardware Prefetch, and the Page Walk remains the right structure for a scan-dominated workload.

Very small sequences. For a sequence of eight elements, the tree is two levels of indirection around data that would fit in a single line. Implementations often special-case the empty and single-element cases and sometimes inline a small number of elements, but the general structure is designed for sequences whose length exceeds a node’s capacity.

The structure’s real domain is state that is read at many versions: editors, version control, incremental computation, and concurrent stores. In that domain the alternative is copying, and copying a multi-megabyte array per edit is not a trade-off but a failure. The same reasoning that made the growth policy a choice in Growth Policies in Dynamic Arrays applies here at a different granularity: the representation is chosen by which cost the workload can afford to pay repeatedly.