Producing a modified copy instead of mutating in place costs something. Compare the strategies real languages use for that cost -- eager copying, copy-on-write with a uniqueness check, and persistent structures with structural sharing -- and say where each one surprises people in production.

seniorshould knowfreq 42%

answer

Eager linear, copy-on-write constant then linear, persistent logarithmic forever
Swift: isKnownUniquelyReferenced; an extra reference makes append copy
C++11 banned copy-on-write std::string over iterators and threading
Branching factor 32: about five node copies per update, worse cache locality
Clojure transients as the local escape hatch; Rust needs no copy because &mut is exclusive

basics

~20 s

Eager copying is linear every time, as with Java's defensive array and collection copies. Copy-on-write is constant until a second reference exists, so Swift arrays turn linear the moment one is captured. Persistent structures such as Clojure's vectors copy only a path of nodes.

solid answer

~50 s

Swift collections are copy-on-write, deciding in place versus copy with isKnownUniquelyReferenced. The surprise: storing the array in a second variable or capturing it in a closure flips an in-place append into a full copy, so an unchanged loop goes from linear to quadratic with no code edit.
C++ shipped a copy-on-write std::string in older libstdc++ and the C++11 standard banned it, because the shared refcount made iterator validity and threading unsound. That is the historical proof that copy-on-write leaks into the observable contract.
Clojure and Scala use trees with branching factor 32, so assoc copies about five nodes rather than the collection; the price is pointer chasing and worse cache locality than a flat array, plus transients as the local escape hatch.
Rust copies nothing: &mut guarantees exclusivity so in-place mutation is already safe. You pay in API rigidity, not cycles.
Java copies eagerly at each boundary, so two layers each copying is two linear passes.

- **Swift** collections are copy-on-write, deciding in place versus copy with `isKnownUniquelyReferenced`. The surprise: storing the array in a second variable or capturing it in a closure flips an in-place append into a full copy, so an unchanged loop goes from linear to quadratic with no code edit. - **C++** shipped a copy-on-write `std::string` in older libstdc++ and the C++11 standard **banned** it, because the shared refcount made iterator validity and threading unsound. That is the historical proof that copy-on-write leaks into the observable contract. - **Clojure and Scala** use trees with branching factor 32, so `assoc` copies about five nodes rather than the collection; the price is pointer chasing and worse cache locality than a flat array, plus transients as the local escape hatch. - **Rust** copies nothing: `&mut` guarantees exclusivity so in-place mutation is already safe. You pay in API rigidity, not cycles. - **Java** copies eagerly at each boundary, so two layers each copying is two linear passes.

code

swift · 8 lines

swift

var a = Array(0..<100_000)
for i in 0..<1000 { a.append(i) }        // in place, storage is unique

var a2 = Array(0..<100_000)
let keeper = a2                          // second reference to the storage
for i in 0..<1000 { a2.append(i) }       // first write copies the buffer
// same loop text; the second version pays a copy because
// isKnownUniquelyReferenced now reports false

go deeper

for a junior

Know that making a modified copy costs time proportional to the data unless the language is doing something cleverer, and that the clever versions exist.

for a middle

Name the three strategies and one language for each, and state the cost of an update under each.

for a senior

Explain the failure modes: the extra reference in Swift copy-on-write, the read-path cost of trees with structural sharing, and layered eager copying in a service. Insist on measurement.

for a principal

Turn it into a selection rule tied to workload: versioning and snapshot needs favour persistence, single-owner hot paths favour in-place with controlled sharing, and boundary policy determines how many eager copies a request pays across the whole stack.

The three strategies

When a value must appear unchanged to its existing holders but a modified version is needed, there are exactly three implementable answers.

Eager copy. Duplicate the whole thing up front. Cost is linear in size on every operation, and predictable. Copy-on-write. Share the representation and duplicate lazily, at the first write, if and only if more than one holder exists. Cost is constant while unshared, linear at the moment sharing is detected. Structural sharing (persistent data structures). Store the collection as a tree and rebuild only the path from the root to the changed element, sharing every untouched subtree with the previous version. Cost is logarithmic per update, forever, with both versions remaining valid.

Copy-on-write, and how it surprises

Swift's Array, Dictionary, String and Set are copy-on-write. Assignment copies a small header with a reference to shared storage; a mutating operation calls isKnownUniquelyReferenced on that storage and mutates in place if the count is one, or copies first if it is not.

The hazard follows directly. Appending in a loop to an array that nothing else references is amortized constant time. Introduce a second reference, by assigning it to another variable, capturing it in an escaping closure, storing it in a property that is also read elsewhere, and the first mutation inside the loop copies the whole buffer, every iteration if the extra reference persists. The source of the loop did not change. This is why Swift performance guidance is full of "beware the extra reference" advice and why isKnownUniquelyReferenced is public API for authors of their own copy-on-write types.

C++ provides the cautionary precedent. Older libstdc++ implemented std::string with copy-on-write and a shared reference count. C++11 effectively outlawed it by tightening the requirements: iterator invalidation rules and the demand that concurrent reads of distinct string objects be safe cannot be met when two apparently independent strings share a mutable buffer and a refcount. The implementation had to change and broke ABI compatibility in the process. The lesson generalises: copy-on-write is only invisible while nobody can observe sharing, and reference validity, threading and performance are all observation channels. Qt's implicitly shared containers make the same trade and document it explicitly rather than hiding it.

Structural sharing, and what it actually costs

Clojure's persistent vector and hash map, Scala's immutable collections and Immutable.js in JavaScript are wide trees, typically with a branching factor of 32. Updating one element copies the nodes along one root-to-leaf path, about log32 n nodes, so for a million elements roughly four to five small node copies. Every previous version stays valid and shares almost everything with the new one.

The cost is not in the update, it is in the read. Access requires walking several levels of pointers, so a random read is several dependent memory loads instead of one indexed load into a contiguous array, and the memory layout is far less cache-friendly. In tight numeric loops this is commonly several times slower than a flat array, which is precisely why Clojure offers transients: a locally mutable version of a persistent structure that you build up and then freeze, sound because the mutable window never escapes.

Rust: no copy at all

Rust removes the problem rather than optimizing it. A &mut T is guaranteed by the compiler to be the only live reference, so in-place mutation cannot be observed by anyone else and no defensive copy is ever needed. Cloning is explicit and visible at the call site. What you pay is not cycles but API rigidity: the ownership must be worked out in the signatures, and shared-mutable shapes have to be expressed with Rc<RefCell<...>> or an arena.

Eager copying, and why it is often fine

Java's List.copyOf, defensive array clones in constructors and accessors, and Go's slices.Clone are all eager. The intuition that this is expensive is frequently wrong for small collections: on a generational collector allocation is close to a pointer bump, a short-lived copy dies in the young generation and is never traced, and a contiguous copy of a few dozen elements is a single fast memory move with perfect locality. Escape analysis can sometimes remove the allocation altogether.

Where it does hurt is systematic: a request crossing five layers, each copying the same collection defensively, performs five linear passes over data that never changed. That is an architectural cost, not a micro-optimization, and the fix is to copy once at the outermost trust boundary and pass a deeply immutable type inward.

Choosing

Small and short-lived: copy eagerly, and prefer the contiguous layout. Large, frequently versioned, or needing old versions to stay valid, undo stacks, editor buffers, snapshot isolation over a shared state: use persistent structures. Hot single-owner mutation with occasional sharing: copy-on-write, provided you can control the number of references and are prepared to measure. Then measure, since every one of these strategies has a performance cliff that is invisible in the source: the extra reference in Swift, the cache miss in Clojure, the fifth defensive copy in a layered Java service.

## The three strategies When a value must appear unchanged to its existing holders but a modified version is needed, there are exactly three implementable answers. **Eager copy.** Duplicate the whole thing up front. Cost is linear in size on every operation, and predictable. **Copy-on-write.** Share the representation and duplicate lazily, at the first write, if and only if more than one holder exists. Cost is constant while unshared, linear at the moment sharing is detected. **Structural sharing (persistent data structures).** Store the collection as a tree and rebuild only the path from the root to the changed element, sharing every untouched subtree with the previous version. Cost is logarithmic per update, forever, with both versions remaining valid. ## Copy-on-write, and how it surprises Swift's `Array`, `Dictionary`, `String` and `Set` are copy-on-write. Assignment copies a small header with a reference to shared storage; a mutating operation calls `isKnownUniquelyReferenced` on that storage and mutates in place if the count is one, or copies first if it is not. The hazard follows directly. Appending in a loop to an array that nothing else references is amortized constant time. Introduce a second reference, by assigning it to another variable, capturing it in an escaping closure, storing it in a property that is also read elsewhere, and the first mutation inside the loop copies the whole buffer, every iteration if the extra reference persists. The source of the loop did not change. This is why Swift performance guidance is full of "beware the extra reference" advice and why `isKnownUniquelyReferenced` is public API for authors of their own copy-on-write types. C++ provides the cautionary precedent. Older libstdc++ implemented `std::string` with copy-on-write and a shared reference count. C++11 effectively outlawed it by tightening the requirements: iterator invalidation rules and the demand that concurrent reads of distinct string objects be safe cannot be met when two apparently independent strings share a mutable buffer and a refcount. The implementation had to change and broke ABI compatibility in the process. The lesson generalises: copy-on-write is only invisible while nobody can observe sharing, and reference validity, threading and performance are all observation channels. Qt's implicitly shared containers make the same trade and document it explicitly rather than hiding it. ## Structural sharing, and what it actually costs Clojure's persistent vector and hash map, Scala's immutable collections and Immutable.js in JavaScript are wide trees, typically with a branching factor of 32. Updating one element copies the nodes along one root-to-leaf path, about `log32 n` nodes, so for a million elements roughly four to five small node copies. Every previous version stays valid and shares almost everything with the new one. The cost is not in the update, it is in the read. Access requires walking several levels of pointers, so a random read is several dependent memory loads instead of one indexed load into a contiguous array, and the memory layout is far less cache-friendly. In tight numeric loops this is commonly several times slower than a flat array, which is precisely why Clojure offers **transients**: a locally mutable version of a persistent structure that you build up and then freeze, sound because the mutable window never escapes. ## Rust: no copy at all Rust removes the problem rather than optimizing it. A `&mut T` is guaranteed by the compiler to be the only live reference, so in-place mutation cannot be observed by anyone else and no defensive copy is ever needed. Cloning is explicit and visible at the call site. What you pay is not cycles but API rigidity: the ownership must be worked out in the signatures, and shared-mutable shapes have to be expressed with `Rc<RefCell<...>>` or an arena. ## Eager copying, and why it is often fine Java's `List.copyOf`, defensive array clones in constructors and accessors, and Go's `slices.Clone` are all eager. The intuition that this is expensive is frequently wrong for small collections: on a generational collector allocation is close to a pointer bump, a short-lived copy dies in the young generation and is never traced, and a contiguous copy of a few dozen elements is a single fast memory move with perfect locality. Escape analysis can sometimes remove the allocation altogether. Where it does hurt is systematic: a request crossing five layers, each copying the same collection defensively, performs five linear passes over data that never changed. That is an architectural cost, not a micro-optimization, and the fix is to copy once at the outermost trust boundary and pass a deeply immutable type inward. ## Choosing Small and short-lived: copy eagerly, and prefer the contiguous layout. Large, frequently versioned, or needing old versions to stay valid, undo stacks, editor buffers, snapshot isolation over a shared state: use persistent structures. Hot single-owner mutation with occasional sharing: copy-on-write, provided you can control the number of references and are prepared to measure. Then measure, since every one of these strategies has a performance cliff that is invisible in the source: the extra reference in Swift, the cache miss in Clojure, the fifth defensive copy in a layered Java service.

Why did C++11 make copy-on-write std::string non-conforming?
Because sharing became observable. The rules on iterator and reference validity, and the requirement that operations on distinct string objects be safe from different threads, cannot both hold when two logically separate strings share one buffer and a mutable reference count. Implementations had to switch to small-string optimization plus eager copying, breaking ABI compatibility in the process.
What are Clojure's transients for, and why are they sound?
They are a locally mutable version of a persistent collection, used to build a result efficiently and then converted back with persistent!. They are sound because the mutable handle is confined to the constructing scope and never escapes, and the runtime enforces this by invalidating the old handle after each operation. It is the same principle as a builder: mutate while nobody else can see it, publish an immutable value.
When is eager copying the right answer despite being linear?
When the collection is small, when the copy is short-lived and dies in the young generation of a generational collector where allocation is cheap and dead objects are never traced, and when contiguous layout matters for read performance. The real cost of eager copying is usually architectural rather than local: several layers each copying the same data, which is fixed by copying once at the outermost boundary.

Eager copy is photocopying the whole book each time you correct a word; copy-on-write is sharing one copy until a second reader appears; structural sharing is rebinding one page and reusing the rest of the spine.

saying these in an interview costs you the question

Assuming copy-on-write is always cheap, without accounting for what an extra reference does to the uniqueness check
Believing persistent structures are free because updates avoid a full copy, ignoring their read-path cost and cache behaviour
Claiming allocation is always expensive, when a short-lived copy on a generational collector often is not
Reaching for a persistent collection in a hot numeric loop where a flat array plus a local mutable build-up is correct
Treating copy-on-write as a purely internal optimization, when reference validity and threading make sharing observable

Producing a modified copy instead of mutating in place costs something. Compare the strategies real languages use for that cost -- eager copying, copy-on-write with a uniqueness check, and persistent structures with structural sharing -- and say where each one surprises people in production.

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

The three strategies

Copy-on-write, and how it surprises

Structural sharing, and what it actually costs

Rust: no copy at all

Eager copying, and why it is often fine

Choosing

▾common follow-ups3 questions

▾analogy~20 s

▾red flags5 flags

§ context

▾related questions4 questions

▾related topics4 topics

The three strategies

Copy-on-write, and how it surprises

Structural sharing, and what it actually costs

Rust: no copy at all

Eager copying, and why it is often fine

Choosing

answer

go deeper

context