skip to content

Rebuilding an immutable cart, why batch many edits into a temporary mutable buffer and freeze it once at the end?

level: middleimportance: should knowfreq 50%

answer

  1. unobserved values need not exist
  2. private buffer, one public value
  3. count edits between observations
  4. one allocation instead of n
  5. confinement is the licence to write

basics

~20 s

Because the intermediate carts nobody can see do not have to exist. Edits go into a private buffer in place, and one immutable value is produced at the end — one allocation instead of one per edit.

solid answer

~40 s

The reason update by copy is expensive in a loop is that it builds a publishable value after every single edit, when only the last one is ever published. Batching collects the edits into a temporary buffer that no other code can reach, applies them in place, and converts the result into an immutable value once. Cost drops from Θ(n·m) and `n` allocations to roughly Θ(n + m) and one. The licence for mutating is **confinement**: while the buffer is unreachable from anywhere else, nobody can observe a partly-edited state, so the intermediates are not values anyone could depend on. For a single edit this machinery buys nothing and should be skipped.

code

pseudocode · 6 lines
pseudocode
function applyEdits(cart, edits)
    buffer = mutableCopyOf(cart.lines)   // one copy, m slots
    for each edit in edits               // n edits, written in place
        buffer[edit.index] = edit.line
    return freeze(buffer)                // one published value, totals once
// buffer is unreachable after the call returns

go deeper

for a junior

Recall the trick: collect the edits into one temporary working copy, change it in place, and turn it into an immutable value once at the end instead of after every single edit.

for a middle

Explain why it is legitimate — the intermediates were visible to nobody, so they never had to exist — and quote the saving: one allocation instead of n, and Θ(n + m) work instead of Θ(n·m).

for a senior

Show the rule you apply: count the edits between two points where anyone can observe the value. One edit, copy directly; many edits behind a boundary, batch into a confined buffer and freeze once.

for a principal

Set the boundary for the team: where a mutable buffer may exist at all, who may hold one, and what keeps the pattern in the few measured hot paths instead of spreading into ordinary code.

## The rule that licenses the mutation Immutability is a promise made to **observers**: whoever holds a value will keep reading the same thing. A value that no one but the code building it can reach has no observers, so nothing is promised about it, and nothing is broken by writing into it. That is the whole argument for batching. A loop that copies per edit produces `n` values, `n − 1` of which are seen by nobody. They exist only because the code kept asking for a publishable value at a point where no one was going to read it. Build the buffer instead, write into it freely while it stays private, and publish exactly one immutable value — the one that was going to be observed anyway. The decision rule falls straight out of that: **count the edits between two points where anyone can observe the value.** One edit between observations, copy directly. Many edits behind a boundary, batch and freeze. ## The shape 1. Create a mutable buffer from the current cart's lines — one copy, `m` slots. 2. Apply every edit into the buffer in place, each one touching only what it changes. 3. Convert the buffer into an immutable cart once, computing the derived totals at that moment. 4. Let the buffer go out of scope so no path to it survives the function that created it. Step 4 is not decoration. The buffer's confinement is what made step 2 legal, and the confinement has to hold for its whole lifetime — including after the freeze, if the freeze hands over the buffer's storage rather than copying it out. ## What it saves | | copy per edit | buffer, then one freeze | |---|---|---| | immutable values produced | n | 1 | | allocations for containers | n | 1 buffer + 1 value | | work for n edits over m lines | Θ(n·m) | Θ(n + m) | | appending n lines | ≈ n²/2 slot writes | Θ(n) amortised | | derived totals recomputed | n times | once | | observable intermediates | none published either way | none | The last two rows carry the practical point. In a cart the expensive part is often not the container copy at all but the totals recomputed after every edit; batching collapses `n` recomputations into one, and the final value is **identical** to the one the copying loop would have produced. Batching changes the cost of getting there, never the answer. ## The conditions it depends on - **Confinement.** The buffer must not be reachable by anything except the code doing the edits — not returned, not stored in a field, not handed to a callback, not captured by something that outlives the build. - **A source that is safe to copy from.** Building the buffer from the cart's own storage rather than from a copy of it would mutate the published cart, which is the mistake this technique is supposed to prevent. - **A freeze discipline.** Either the freeze copies the buffer's contents into storage the value alone owns, or it takes the storage over and the buffer handle is retired; a freeze that shares storage while leaving the handle usable is not a freeze. - **Whole-value publication.** The value becomes visible only after the last edit, so readers see the cart before and the cart after, never a cart midway through the batch. ## When not to reach for it - **A single field change.** A copy-with-one-field-changed is already one allocation; a buffer adds another plus an extra indirection and buys nothing back. - **A handful of edits on a narrow container.** The arithmetic only turns interesting when `n·m` is large enough to see. - **Anywhere the intermediates genuinely are observed.** If something is meant to react to each edit, the intermediates are real values with real readers and must be produced. - **Code where confinement is hard to guarantee.** The technique trades a cost problem for a correctness obligation; in a tangled call graph where the buffer would have to be passed around, the plain copy is the safer default. ## How to talk about it The answer an interviewer is listening for is not "use a buffer, it's faster". It is the reasoning that makes the buffer legitimate: the value is immutable to everyone who can see it, and during the batch nobody can see it. Candidates who present the buffer as "cheating on immutability" have the model backwards — the guarantee is about what observers can witness, and confinement is how you keep that guarantee while still writing in place.

  • Does batching change what callers can observe about the cart?
    No, provided the buffer is never published. Callers see the cart before the batch and the cart after it, never a state in between — which is exactly what the copy-per-edit loop showed them too, since its intermediates were also unpublished. Only the cost of reaching the final value changes.
  • When is the buffer the wrong choice?
    For one edit, or a few edits on a narrow container: it adds an allocation and an indirection, and it introduces a mutable handle that must not escape. It is also wrong wherever the intermediate values genuinely have readers, because then they are real values rather than waste.
  • Where should the buffer be created from?
    From a copy of the cart's lines, never from the published cart's own storage. Writing into storage the existing cart is reading would mutate a value callers already hold, which is precisely the failure the whole design exists to prevent.

saying these in an interview costs you the question

  • Says a mutable buffer means the result is not really immutable.
  • Passes the buffer to other code while edits are still in flight.
  • Reaches for a buffer to change a single field.
  • Thinks batching produces a different final value, not just a cheaper route.
  • Treats the freeze as free regardless of how storage is handed over.