skip to content

Why is a persistent map's logarithmic update usually acceptable against a mutable structure's constant-time in-place write?

level: middleimportance: should knowfreq 46%

answer

  1. the base is large, not two
  2. depth, not entry count
  3. bits of hash per level
  4. about four levels for a million
  5. bitmap keeps nodes narrow

basics

~20 s

Depth, not size, sets the cost. A wide branching factor keeps a map of millions only about four levels deep, so an update rewrites a handful of small nodes - a bounded constant in practice, for which you get every earlier version still valid.

solid answer

~40 s

The logarithm is a logarithm of depth with a large base. In a wide-branching trie - the hash array mapped trie is the workhorse shape - each level consumes a few bits of the key, so with 32-way branching a million entries sit about four levels down and a billion about six. An update rewrites only the nodes on that one root-to-slot route, and each node is small because it stores just its occupied slots. So the asymptotic gap against a single in-place store is real but the constant is a few allocations and a few pointer writes, and the depth is effectively capped. It stops being acceptable in a hot loop that rewrites single slots millions of times and keeps no old version - there the mutable write is the right tool.

code

pseudocode · 11 lines
pseudocode
// branching factor b = 32: each level consumes 5 bits of the key's hash

function updateEntry(root, key, value):
    path = nodesFromRootToSlot(root, key)     // about log_b(n) nodes
    newNode = leafHolding(key, value)
    for each node in path, from deepest to shallowest:
        newNode = copyOf(node) with one child replaced by newNode
    return newNode                            // this is the new root

// n = 1,000,000 and b = 32  ->  path length about 4
// the other 999,999 entries are reached from both roots, untouched

go deeper

for a junior

Recall that an update does not rebuild the map: it touches only the nodes between the root and the changed slot, so a big map does not mean a big update.

for a middle

Explain where the logarithm's base comes from - bits of hash consumed per level - and compute the depth: about four levels for a million entries at 32-way branching, capped by the hash width.

for a senior

Bring the measurement, not the asymptotics: dependent pointer loads and allocation pressure are what a profile shows, and the honest comparison includes what a mutable structure would have to pay in locks or defensive copies to give readers the same stable view.

for a principal

Own the boundary decision: where in the system the versioned representation ends and a mutable hot path begins, and what evidence would move that line. A blanket rule either way is what makes the trade-off unarguable later.

## The two costs being compared One side is a mutable structure: computing a slot address and storing a word into it. One memory write, contiguous memory, cache-friendly, no allocation. The other side is a persistent structure, where an update must produce a new version while the old version stays entirely valid - so it cannot write into anything the old version can still see. Stated as complexity that sounds catastrophic: constant against logarithmic. Stated as what actually happens per update it usually is not, and the reason is where the logarithm's base comes from. ## Where the logarithm comes from A persistent map is typically a tree keyed by a path through the key's hash. Each level consumes a fixed number of bits of the hash to pick a child. The number of levels between the root and the slot is therefore the depth of the tree, which is the logarithm of the entry count **in the branching factor** - not in two. With 32-way branching (five bits of hash consumed per level): | entries | levels on the path | |---|---| | about a thousand | about 2 | | about a million | about 4 | | about a billion | about 6 | There is a second cap that matters: the path can never be longer than the hash width divided by the bits consumed per level. With a 32-bit hash and five bits a level that is about seven, whatever the entry count. So a structure that is logarithmic on paper behaves like a bounded constant in every size a program actually holds in memory. ## Why a wide node is not expensive to copy The obvious objection is that a 32-wide node is 32 slots to copy per level, which would trade depth for width and gain nothing. Real implementations avoid it by storing an occupancy bitmap plus an array holding **only the occupied children** - the shape the hash array mapped trie is named for. A node with three children is three slots wide, not thirty-two, and the bitmap tells you which logical slot each entry corresponds to. Sparse levels stay small; only genuinely dense levels get wide. So one update is roughly: walk about four levels, allocate about four small nodes, copy a handful of pointers into each, return the new root. That is the honest constant behind the logarithm. ## What the comparison actually costs you 1. **Allocation instead of a store.** Each update produces new nodes rather than writing over old ones. That is real work, and it pushes on memory management in a way an in-place write does not. 2. **Pointer chasing instead of contiguity.** A flat mutable array is a single indexed access; a trie is several dependent loads, each of which can miss cache. This, not the node count, is usually what you measure. 3. **The old version is retained while anything holds it.** The update is cheap; keeping the history is what costs memory. ## Not every persistent structure is logarithmic The shape decides the cost, and the wide trie is one shape among several: - **A chain of cells** (each holding a value and a reference to the rest) supports adding to the front in **constant** time, sharing the entire remainder untouched - cheaper than the trie for that one operation. But changing the element at position k costs work proportional to k, because everything before it must be rebuilt. - **A balanced tree keyed by order** gives logarithmic updates in base two - deeper than the wide trie, but it keeps the entries in sorted order, which the hash-keyed trie does not. - **A wide-branching indexed sequence** gives both indexed access and updates in the same bounded-depth range as the map. So the right answer to "what does a persistent update cost?" always begins with *which structure*, and the well-known near-constant behaviour is a property of the wide-branching family specifically. ## When the gap genuinely matters The comparison stops being a rounding error when the update rate is the program's inner loop and no version is ever kept - a numeric kernel rewriting single slots millions of times, a hot counter, a buffer being filled byte by byte. There the mutable structure is simply the correct tool, and forcing persistence on it buys a guarantee nobody is using. It is also why systems that want both build the new value through a temporary mutable phase and hand out an immutable version at the end. The mirror of that case is where the persistent update is free in the only currency that matters: a reader that would otherwise need a lock or a defensive copy to get a stable view. Against the cost of copying the whole document for every concurrent reader, four small node allocations are not a trade-off at all.

  • Is every persistent update logarithmic?
    No - the shape decides it. Adding to the front of a chain of cells is constant and shares the whole remainder, while changing the element at position k in that same chain costs work proportional to k. The near-constant behaviour people quote belongs to the wide-branching tries, and an order-keyed balanced tree is logarithmic in base two, so deeper.
  • Why not raise the branching factor to 1,024 and make the tree even shallower?
    Because width and depth trade against each other. Fewer levels mean fewer nodes to rewrite, but each node is bigger to copy and less cache-friendly, and the bitmap trick only keeps sparse levels small. Around 32 the depth is already effectively capped by the hash width, so extra width buys almost no depth and costs real copying.
  • In a measured profile, what usually dominates the update - the copying or something else?
    Usually the memory behaviour rather than the node count: several dependent pointer loads down the path, each able to miss cache, plus pressure from allocating the new nodes. A flat mutable slot write is one contiguous access. Counting nodes underestimates the gap; counting cache misses explains the measurement.

saying these in an interview costs you the question

  • Says an update copies the whole map
  • Assumes the logarithm is base two here
  • Thinks a 32-wide node always copies 32 slots
  • Claims persistent updates are constant time for any structure
  • Ignores allocation and cache effects, counting only node copies