skip to content

A loop applies 1,000 line edits to an immutable cart by copying the whole cart each time — what does that cost?

level: middleimportance: must knowfreq 58%

answer

  1. you pay per container, not per field
  2. cost follows the cart's line count
  3. n edits times m lines
  4. appending one at a time is quadratic
  5. allocation rate, not peak footprint

basics

~20 s

Each edit builds a whole new cart container, so one edit costs work proportional to the number of lines, and 1,000 edits cost roughly 1,000 times that plus 1,000 allocations — a throughput cost, not a memory-footprint one.

solid answer

~40 s

The unit of cost is the container, not the field you changed. For a cart of `m` lines, one copy allocates a new container and writes `m` line slots, so it is Θ(m) per edit and Θ(n·m) for `n` edits. If the loop appends rather than replaces, `m` grows with every step and the total becomes about n²/2 slot writes. The 1,000 intermediate carts are unreachable as soon as the loop rebinds, provided nothing else retained them, so peak memory stays roughly flat — what you are paying is allocation and copying bandwidth. Whether that matters depends entirely on how wide the cart is and what else each iteration does.

code

pseudocode · 7 lines
pseudocode
cart = cartWithLines(existingLines)      // m lines

for each edit in edits                   // n = 1,000 edits
    cart = copyWithLineReplaced(cart, edit.index, edit.line)
    // each call: 1 new container, m line slots written

// 1,000 containers built; 999 unreachable by the end

go deeper

for a junior

Remember that copying a container is not the price of changing one field: the new container has to be filled in, so the cost follows how many items the container holds, not how many you altered.

for a middle

Put numbers on it. For a cart of m lines and n edits, state the Θ(m) per edit and the Θ(n·m) total, and say that appending one line at a time through whole copies is quadratic in the append count.

for a senior

Separate footprint from throughput. Intermediates nobody retains do not raise peak memory; they cost allocation and copying bandwidth, and that is what you measure before calling the design a problem.

for a principal

Decide where the team draws the line: update by copy as the default everywhere, with batched rebuilds reserved for the few paths a measurement has named, rather than left to each author's instinct.

## The unit of cost is the container, not the field When you change one field of one line inside an immutable cart, the thing you are obliged to rebuild is not the field — it is every value that contained it. The line is rebuilt, then the cart that held the line, and the new cart's line collection has to be filled in. That last step is where the money goes: a container of `m` lines is produced by writing `m` slots, whatever fraction of them changed. So the mental model that produces a wrong answer is "I changed one number, so I paid for one number". The right one is **"I produced a new container, so I paid for a container"**. ## Putting n and m on it Let `m` be the number of lines in the cart and `n` the number of edits the loop applies. 1. **One edit, cart width fixed.** One new container, `m` reference slots written, one new line object: **Θ(m)**. 2. **n edits, cart width fixed.** The loop repeats that, so **Θ(n·m)** slot writes and **n** container allocations. With n = 1,000 and a 50-line cart that is around 50,000 reference writes and 1,000 containers for 1,000 changed numbers. 3. **n appends, cart growing.** The k-th append copies the k−1 lines already present, so the total is 1 + 2 + … + n ≈ **n²/2** slot writes. Appending one item at a time through whole-container copies is the quadratic case, and it is the one that shows up as a mystery in profiles. Note what is **not** in that arithmetic: the line objects themselves are not duplicated. The copy re-points at them, so the cost is the container's width and not the cart's total reachable size. | | copy per edit | one container built once | |---|---|---| | containers allocated | n | 1 | | reference slots written | n·m (or ≈n²/2 while appending) | m (or n while appending) | | values anyone can observe | the first and the last; the rest are private | the first and the last | | peak live memory | roughly one cart, if nothing retains the rest | roughly one cart | ## Footprint versus throughput The most common wrong answer is that the intermediates "pile up and blow the memory budget". They do not, in the ordinary case: each iteration rebinds the name to the new cart, the previous cart becomes unreachable at that moment, and only a couple are live at a time. Peak footprint is therefore about the size of one cart. What the loop really spends is: - **allocation rate** — n containers requested in quick succession, all of which the runtime must eventually account for; - **copying bandwidth** — n·m slot writes that do no logical work, since most slots get the value they already had; - **cache behaviour** — each new container is fresh memory, so the working set churns rather than staying hot. The exception that makes the footprint claim true is when something **retains** the intermediates — a log of every version, a history buffer, a listener that keeps what it is handed. Then n carts really are live, and the size claim becomes correct for that reason and not because copying implies it. ## When the cost is real and when it is noise - **Noise:** one or two edits per request, a narrow cart, or an iteration that already does parsing, validation or I/O that dwarfs a few dozen slot writes. - **Real:** a tight in-memory loop over a wide container, a hot path that rebuilds the whole cart per event, or an append-one-at-a-time build where the quadratic term is the whole profile. - **The diagnostic:** compare the per-edit copy against the useful work per edit. If the copy is the majority, the loop is spending its time reproducing values it already had. - **The measurement:** the symptom is high allocation rate and time spent in bulk copying with the logic itself barely registering — not a growing heap. It is also worth knowing that this cost model belongs to a **flat, whole-container copy**. Container designs that avoid touching every slot on an update change the arithmetic entirely, and that is a subject of its own; the point here is to be honest about what the plain copy costs before reaching for anything cleverer.

  • Does the loop's peak memory grow with the number of edits?
    Not by itself. Each iteration rebinds to the new cart, so the previous one becomes unreachable and at most a couple are live at once. What grows is the allocation rate and the total slot writes. Peak memory only tracks the edit count if something deliberately retains the intermediate versions.
  • What changes if the loop appends lines instead of replacing one?
    It becomes quadratic in the number of appends. The container copied on the k-th append already holds k−1 lines, so the total is 1 + 2 + … + n ≈ n²/2 slot writes, against Θ(n) for filling one container. This is the single most common way copy-per-edit turns into a profile mystery.
  • How do you decide whether this cost is worth attacking?
    Compare the copy against the useful work each iteration already does. If the edit involves parsing, validation or I/O, the copy is noise; if it is a tight in-memory transform over a wide container, the copy is the profile. Measure allocation rate and bulk-copy time before changing the design.

saying these in an interview costs you the question

  • Says copying the cart costs about the same as changing one field.
  • Claims the loop's intermediate carts accumulate and exhaust memory.
  • Assumes the copy duplicates every line object, quoting a far worse cost.
  • Believes untouched lines cost nothing, ignoring the slot written for each.
  • Optimises a copy that happens once per request as if it were the loop.