Mutability vs Persistent Data Structures

When to mutate state in place versus reach for immutable, structurally-shared persistent data structures — and why the default should flip depending on your concurrency and history needs.

What they actually are

Mutability means you change a value in place: the array you had is the array you now have, just different. Persistent data structures give you a new version on every "change" while keeping the old one intact and valid forever. The trick that makes this not insane is structural sharing — a Hash Array Mapped Trie or RRB-tree copies only the path from root to the changed node, log32(n) nodes, and points everything else at the old structure. So "copy the whole map" is a lie people tell to dismiss immutability; you copy a thumbnail of it. The two aren't symmetric options. Mutability is the machine's native behavior — registers, RAM, and CPUs mutate. Persistence is a discipline layered on top to buy guarantees. That asymmetry is the whole debate: you trade some cycles and bytes for the ability to reason about your program.

Where mutability still wins

Don't let an immutability evangelist near your inner loop. Mutating a preallocated buffer in a tight numeric kernel, a game frame, or an embedded controller is faster, allocates nothing, and keeps cache lines hot — persistent structures chase pointers across heap-scattered trie nodes and lean on the allocator and GC you were trying to avoid. If your data has exactly one owner, never escapes the function, and lives a few microseconds, versioning it is pure ceremony tax. Languages know this: Clojure ships transients, Scala has mutable builders, Rust hands you &mut precisely so you can mutate locally inside an otherwise-safe boundary. The honest framing is scope. Mutation is fine when it's invisible — when no other thread, no future caller, and no past version can observe it. The moment that data is shared or its history matters, in-place mutation stops being an optimization and becomes a liability.

Where persistent structures earn it

Every nasty bug you've spent a weekend on lives in shared mutable state: two threads racing a hashmap, a callback mutating an array a caller still held, a "defensive copy" someone forgot. Persistent structures delete that category. If a value can't change under you, there's nothing to race and nothing to defensively copy — you can hand the same reference to ten threads and sleep. They also hand you features for free that mutation makes you build by hand: undo/redo is just keeping old roots, time-travel debugging is replaying versions, and cheap reference-equality change detection is why React/Redux and Re-frame insist on it. "Did this subtree change?" becomes a pointer compare instead of a deep walk. That's not academic purity; it's the difference between an O(1) === and crawling your whole state tree on every render. The safety isn't free, but the bugs it prevents are the expensive ones.

The verdict

Default to persistent, drop to mutable on evidence. Pick immutability as your architectural baseline — state trees, shared caches, event logs, anything multiple readers touch — because it removes the bugs that actually cost you days, not microseconds. Then, where a profiler (not a vibe) shows a hot path bottlenecked on allocation or copying, carve out a single-owner region and mutate freely behind that wall. This is exactly what mature languages encode: Clojure's transients, Rust's &mut inside safe APIs, Scala's builders. The losing strategy is the inverse — mutating everything by default and bolting on locks, defensive copies, and snapshot hacks as bugs surface. That's how you get a codebase nobody can reason about. Immutability scales with team size and concurrency; mutation scales with raw single-threaded throughput. Most software is bottlenecked on the former. So I pick persistent data structures, and I let you mutate in the corners where you've proven you must.

Quick Comparison

Factor	Mutability	Persistent Data Structures
Concurrency safety	Needs locks, defensive copies, careful ownership	Share freely across threads; no races possible
Raw single-thread speed	Native, zero-alloc, cache-friendly in-place updates	Pointer-chasing tries, GC/allocator pressure
Memory footprint	Minimal — one copy, updated in place	Structural sharing is cheap but old versions linger
Undo / time-travel / change detection	Build it all yourself, error-prone	Free — old roots and O(1) reference equality
Reasoning about code at scale	Aliasing and hidden mutation make it hard	Values never change under you; local reasoning holds

The Verdict

Use Mutability if: You're in a hot numeric loop, a memory-constrained device, or a single-threaded section where in-place updates are measurably faster and the data has no shared readers.

Use Persistent Data Structures if: You have concurrency, undo/redo, time-travel debugging, change detection, or any shared state — which is most real application code — and you want a class of bugs to simply not exist.

Consider: You rarely pick one globally. Use persistent structures at the architecture boundaries (state trees, shared caches, event logs) and drop to local mutation inside isolated, single-owner hot paths.

Mutability vs Persistent Data Structures: FAQ

Is Mutability or Persistent Data Structures better?

Persistent Data Structures is the Nice Pick. Persistent data structures make the expensive bugs — shared-mutable-state races, accidental aliasing, lost undo history — structurally impossible, and structural sharing means you pay far less for that safety than naive copying implies. Mutability wins tight loops and memory ceilings; everywhere else, immutability is the correct default.

When should you use Mutability?

You're in a hot numeric loop, a memory-constrained device, or a single-threaded section where in-place updates are measurably faster and the data has no shared readers.

When should you use Persistent Data Structures?

You have concurrency, undo/redo, time-travel debugging, change detection, or any shared state — which is most real application code — and you want a class of bugs to simply not exist.

What's the main difference between Mutability and Persistent Data Structures?

When to mutate state in place versus reach for immutable, structurally-shared persistent data structures — and why the default should flip depending on your concurrency and history needs.

How do Mutability and Persistent Data Structures compare on concurrency safety?

Mutability: Needs locks, defensive copies, careful ownership. Persistent Data Structures: Share freely across threads; no races possible. Persistent Data Structures wins here.

Are there alternatives to consider beyond Mutability and Persistent Data Structures?

You rarely pick one globally. Use persistent structures at the architecture boundaries (state trees, shared caches, event logs) and drop to local mutation inside isolated, single-owner hot paths.

The Bottom Line

Persistent Data Structures wins

Persistent data structures make the expensive bugs — shared-mutable-state races, accidental aliasing, lost undo history — structurally impossible, and structural sharing means you pay far less for that safety than naive copying implies. Mutability wins tight loops and memory ceilings; everywhere else, immutability is the correct default.

Related Comparisons