A record loop that fitted in memory fails after being rewritten as one whole-column chain — what changed?
answer
- one record against whole columns
- each operator leaves a full-length result
- count what is live simultaneously
- loop over blocks, not records
- block size trades setup against peak
basics
~20 sThe loop held one record at a time; the chain holds whole columns. Under eager evaluation each operator allocates a full-length result, so several column-sized intermediates are live at once. The repair is a deliberate loop over blocks of rows.
solid answer
~50 sThe rewrite traded time for peak memory, and nobody priced the second half. A per-record loop's working set is one record plus whatever it accumulates. A chain of whole-column operators under **eager evaluation** — where each operator returns a complete result before the next one sees it — allocates a full-length result per operator, and the peak is measured at the moment the widest set of those is still referenced. Four steps over a long column can mean four column-sized buffers live at once on top of the operands. The repair is not to go back to a per-record loop: it is a **deliberate loop over blocks of rows**, running the same chain over tens of thousands of rows at a time and releasing each block's intermediates. Inside a block the work is still one dispatch per operator over packed values, so the per-call cost is negligible and the per-value cost stays compiled.
code
pseudocode · 15 lines# eager chain: three full-length intermediates live at the widest moment
t1 = weight * factor # length n
t2 = t1 + offset # length n, t1 still referenced
out = t2 / divisor # length n, t2 still referenced
# same arithmetic, peak bounded by the block size B
out = allocate(n)
start = 0
while start < n:
end = min(start + B, n) # final block may be short
t = weight[start:end] * factor[start:end] # length at most B
t = t + offset[start:end]
out[start:end] = t / divisor[start:end]
start = end
# one dispatch per operator per block; live intermediates are B-sized, not n-sizedgo deeper
Recall that a whole-column step produces a whole new column, so an expression with several steps can hold several column-sized results in memory at the same moment.
Explain the peak as the operands plus every intermediate still referenced, and show that an eagerly evaluated chain leaves one full-length result per operator behind it.
Diagnose by counting what is live at the widest moment, then restore the bound with a loop over blocks that keeps the compiled inner pass and releases each block's temporaries.
Decide whether the team writes chains and relies on the execution model to fuse them, or writes block loops by hand: the first is shorter and depends on a property of the tool, the second is explicit and spends review attention.
## What each form holds at its peak Peak memory is not the size of the answer. It is the largest amount live at any single instant, and the instant that matters is usually in the middle of the expression, not at the end. | form | live at the peak | |---|---| | per-record loop | one record, plus the accumulator, plus the input | | single whole-column operator | both operands plus one full-length result | | eager chain of k operators | the operands plus every intermediate still referenced | | chain under deferred evaluation | the operands plus what the fused pass needs | | in-place operator form | the operands only; the result overwrites one of them | The third row is the one that surprises people. Under eager evaluation each operator must produce a complete result before the next operator can consume it, and the input to a step is still referenced while its output buffer is being filled — so both are live together. A four-step chain over a column of fifty million values can be holding several fifty-million-value buffers at the moment it fails. ## This is a property of the evaluation model, not of the written form The same written expression costs different peaks on different designs, and saying which one you are on is half the answer: - **Eager materialisation.** Each operator allocates and returns; the intermediates exist; the peak is the widest live set. - **Deferred evaluation** — writing the expression only records what is to be done, and nothing runs until the answer is asked for. The chain can be fused into a single pass, in which case the middles are never built at all. - **Designs that share untouched buffers.** Producing a new object need not copy the columns the step did not touch; only the changed column is newly allocated, so a wide table with one changed column costs one column, not the table. - **In-place operator forms**, which write back into a buffer that already exists and allocate nothing — at the price of being visible through anything else pointing at that buffer. So "a step roughly doubles peak memory" is the right first instinct for the commonest design and wrong as a universal claim. Attach the condition. ## The block loop, and why it is not the record loop again The repair keeps the compiled inner pass and bounds the peak: 1. Choose a block size — tens of thousands of rows. 2. Run the identical chain over one block at a time. 3. Write each block's output into the destination, or fold it into an accumulator. 4. Let the block's intermediates go before the next block starts. Inside a block, one call to each operator covers every row in that block, so the fixed per-call setup is amortised across tens of thousands of values and is effectively free. The per-value work is still the compiled one. That is the difference from a per-record loop, which paid an interpreted step per value: the block loop pays one call per operator per block, which is a different order of cost entirely. ## Choosing the block size The choice is bounded from both ends, and between the bounds it barely matters: - **Large enough** that a call's fixed setup — argument checks, type resolution, allocating a result — amortises. Thousands of rows, not dozens; a block of fifty rows reintroduces exactly the small-column problem the chain was meant to avoid. - **Small enough** that the block's operands and every live intermediate fit inside the memory you are prepared to use. If the chain holds four intermediates, a block costs roughly four times the block's own width. Pick a round number inside that range, measure once, and write it down where the next reader can find it. ## What blocking does not fix Blocking bounds the **intermediates**, not the inputs. If the operand columns are already held in full, they still occupy their whole length no matter how the arithmetic is cut up. When peak memory stays pinned at the limit after the chain has been blocked, that is the signal: the inputs are the footprint, and the arithmetic was never the problem. ## How to diagnose it rather than guess - Count what is live at the widest moment of the expression, on paper, before measuring — number of operators, times the column's width in bytes. - Watch the peak rather than the final size; a profile that only samples at the end will show nothing. - Shorten the chain and see whether the peak moves. If it does, intermediates are the cause; if it does not, look at the operands. - Remember that reassigning a name only releases a buffer when nothing else still refers to it. An intermediate an operand still points at stays live.
- Why is a loop over blocks not just the record loop again?Because the work inside a block is still one dispatch per operator over packed values: tens of thousands of values share one call, so the fixed setup is negligible and the per-value cost stays compiled. The record loop paid an interpreted step for every value, which is a different order of cost.
- How do you choose the block size?From both ends. Large enough that a call's fixed setup amortises — thousands of rows, not dozens — and small enough that the block's operands and every live intermediate fit in the memory you are willing to use. Between those bounds the exact value barely matters, so pick a round number and measure once.
- Does the same written chain always hold that many intermediates?No. Under eager evaluation each operator returns a complete result, so a chain of four leaves four. Designs that record the expression and evaluate it once can fuse the chain into a single pass, and in-place operator forms write back into an existing buffer. The peak follows the evaluation model, not the written form.
saying these in an interview costs you the question
- Goes back to a per-record loop instead of a loop over blocks.
- Assumes every design materialises an intermediate per operator.
- Counts the input size and forgets the chain's intermediates entirely.
- Picks a block of a few dozen rows and reintroduces the per-call cost.
- Measures the final result's size and calls that the peak.
- Assumes reassigning a name frees a buffer another operand still references.