skip to content

A running total over a long scan defers each addition instead of performing it. Why does memory grow with the element count?

level: middleimportance: must knowfreq 50%

answer

  1. nothing is added during the scan
  2. each step builds on the previous one
  3. the accumulator is not a number
  4. reachable, so nothing is collected
  5. footprint tracks the input length

basics

~20 s

Each deferred addition allocates a thunk that references the previous one, so the accumulator grows into a chain as long as the input instead of staying a single number. Nothing collapses until the final force walks the whole chain.

solid answer

~40 s

Nothing is added during the scan. At each element the code builds a new deferred computation whose body is force the previous accumulator, then add this element - and that new thunk holds a reference to the previous thunk, which holds the one before it, back to the seed. After n elements the accumulator is a chain of n unrun additions, every link reachable and therefore live, while the source reads as though it held one running total. The final demand then runs all n additions in a single deeply nested pass, so the whole cost lands at the end. It is called a space leak because the footprint grows with the input for a result that is one value.

code

pseudocode · 7 lines
pseudocode
total = defer(function() return 0)

for each x in items
    previous = total
    total = defer(function() return force(previous) + x)   // no addition happens here

result = force(total)   // now n additions run, nested n deep

go deeper

for a junior

Recall that deferring an addition does not perform it. What the loop carries is a description of work, so deferring n times means carrying n descriptions.

for a middle

Explain the chain: each deferred addition references the previous one, so nothing can be reclaimed, and the final demand resolves all of them in one nested pass.

for a senior

Name the symptom the way it shows up in a service - memory climbing in proportion to input for a job whose output is one number - and give the fix: force the accumulator at each step.

for a principal

The judgment is where strictness lives by default. Deferring everywhere is quick to write and unpredictable to run, so deciding which accumulation points are always forced is a standard you set once for the team.

## What the accumulator actually holds Write the scan out and the defect becomes visible. At each element the code does not add; it builds a new deferred computation whose body is *force the previous accumulator, then add this element*. That new cell must keep a reference to the previous cell, because it cannot run without it. The previous cell keeps a reference to the one before, and so on back to the seed. So after n elements the variable holding the running total is not a number. It is a chain of n unrun additions with the seed at the far end. This is what makes the defect survive code review: the source says *total becomes total plus this element* and reads like arithmetic, while the heap holds a structure the length of the input. ## Why nothing can be reclaimed The usual mental model of a leak is memory that is no longer reachable, or a registration nobody removed. Neither applies here, and that is why it is a leak *in disguise*: - Every link in the chain is reachable from the accumulator the program is still using. - Every link will genuinely be needed, because the final total depends on all of them. - A collector is therefore behaving correctly by keeping all of them; there is nothing for it to reclaim. The memory is retained by a value the program legitimately holds. The defect is not in the collector or in the runtime; it is that a value which ought to be constant-size was allowed to become proportional to the input. ## What the final force does Forcing the outermost cell demands the one beneath it, which demands the one beneath that, all the way to the seed, and the additions then complete on the way back out. For n elements that is n additions - the work was never going to be less than that - but the evaluation also nests n deep, and a long enough chain exhausts the evaluation stack before the additions finish. Two costs land at once: the peak memory just before the demand, and the depth of the pass that resolves it. | | Deferred accumulator | Accumulator forced each step | |---|---|---| | Memory during the scan | grows with elements seen | one value | | When the n additions run | all at the final demand | as the scan proceeds | | Nesting when the total is demanded | as deep as the input | none | | If the total is never demanded | the chain was still built | the additions were already paid | ## Making the accumulator strict The fix is local and does not cost you laziness anywhere else: 1. Force the accumulator at each step, so what the loop carries is a value rather than a description of work. 2. Leave the source lazy. The elements may still arrive on demand and the producer may still be unbounded; only the accumulated value is made strict. 3. Confirm by shape, not by feel: memory that tracks input length for a one-value result is the signature, and it should flatten once the accumulator is forced. This is the one place where deferral is almost never the right default, and the reason is structural: an accumulator is demanded by definition at the end of the traversal, so there is no skipped work to win - unless the total genuinely may never be demanded at all, in which case the honest fix is not to build it. ## The general shape of the defect - It appears wherever a **value summarising a traversal** is built lazily: a total, a count, a maximum, a merged record. - The symptom is memory proportional to the input for an output that is small and fixed. - It is invisible in the source, because a deferred addition and a performed addition are written almost identically. - Deferring the *elements* is usually fine and often the point; deferring the *accumulation of the elements* is what builds the chain. - The cure is strictness at one named place, not abandoning laziness across the pipeline.

  • What is the fix that keeps the scan lazy but the total small?
    Force the accumulator at every step. The elements can still arrive lazily and the producer can still be unbounded; only the accumulated value is made strict, so it stays one number and each addition happens while its operands are at hand. Memory becomes constant instead of proportional to the input.
  • Why can the final force fail on a long enough input even with memory to spare?
    Because the chain is resolved from the outside in: forcing the last cell demands the previous one, which demands the one before it, so evaluation nests as deep as the chain is long. The additions are linear in n, but so is the nesting, and a deep enough nest exhausts the evaluation stack before the total is produced.
  • Does the same leak appear if the total is never demanded?
    The chain is still built and still occupies memory for as long as it is reachable, so the footprint is identical; what you save is only the additions. If the total is genuinely never needed, the real fix is not to accumulate at all - the cost comes from keeping a growing description of work alive, not from running it.

It is a stack of IOUs: each note says whatever the note underneath comes to, plus this amount. You are holding a pile as tall as the ledger rather than a balance, and nothing is settled until someone finally asks for the total.

saying these in an interview costs you the question

  • Thinks the deferred additions collapse on their own as the scan proceeds.
  • Says the accumulator holds the latest running total during the scan.
  • Calls it a leak because the memory is unreachable, which it is not.
  • Assumes laziness always lowers memory use because less work happens.
  • Believes the final force is cheap once the chain has been built.