A loop builds a result by combining the accumulated table with one more row each iteration, so why does it slow down as it runs?
answer
- the curve bends, it is not linear
- each step recopies all previous rows
- iteration k copies k-1 rows
- collect cheaply, combine once at the end
- the only cost whose share grows
basics
~20 sWhere each combination materialises a new result, it copies everything accumulated so far, so iteration k copies k-1 rows and total work grows with the square of the row count. Collect the rows and combine once instead.
solid answer
~50 sCombining a table with one more row is not writing into spare space at the end. On the common eager designs it produces a brand new table: every column's buffer is allocated afresh at the new length and everything already accumulated is copied into it. Iteration 1 copies nothing, iteration *k* copies *k-1* rows, so over *n* rows the total is roughly *n* squared over two row-copies. The loop therefore gets slower the longer it runs, which is why it passes on test fixtures and dies in production. The fix is to separate accumulating from combining: push each row into a cheap growable container, then combine the whole collection once at the end, which allocates each column once and copies each row once. Designs that only record the operation and materialise at the end do not pay this at all.
code
pseudocode · 10 lines# quadratic: each step allocates a brand-new result and copies all of it
acc = empty_table()
for row in source:
acc = combine(acc, one_row_table(row)) # copies every row accumulated so far
# linear: accumulate cheaply, pay the allocation once
pieces = empty_growable()
for row in source:
push(pieces, row)
acc = combine_all(pieces) # one allocation per column, one copy passgo deeper
Recognise the shape: building a table by combining it with one more row each time gets slower the longer it runs, and collecting the rows first then combining once at the end fixes it.
Do the arithmetic out loud. Iteration k copies the k-1 rows already accumulated, so the total is proportional to the square of the row count rather than to the row count itself.
Say how you would tell this apart from a constant-factor problem: double the input and see whether the time roughly doubles or roughly quadruples, then decide where the fix is worth spending.
Think about how the pattern gets into a codebase at all. It reads naturally, it passes at fixture sizes, and only production row counts expose it, so the guard has to be a review rule or a size-scaled test.
## The pattern, and why it looks innocent The shape is familiar and reads perfectly well: start with an empty result and, on each iteration, combine what you have so far with one more row. Each pass looks like constant work - one row goes in - so the loop looks linear. On most designs it is not, and the reason is entirely in what *combine* does. ## Combining builds a new result Adding a row to a table of this kind is not writing into spare capacity at the end of something. The combination produces **a new table**: for every column, a fresh buffer is allocated at the new length, every value already accumulated is copied into it, and the one new value is written after them. The previous result is then discarded. Count it out. Iteration 1 copies 0 rows, iteration 2 copies 1, iteration *k* copies *k-1*. Over *n* iterations that is 0 + 1 + 2 + ... + (n-1), which is n(n-1)/2 row-copies - proportional to **the square of the row count**, multiplied again by the number of columns, since every copy touches every column's buffer. What that means in practice: - **The loop gets slower as it runs.** The last thousand rows of a hundred-thousand-row build cost around a hundred times what the first thousand cost. - **It is invisible at test sizes.** At a thousand rows the total is half a million row-copies and finishes instantly. At a million rows it is around five hundred billion and does not finish at all. - **It churns memory as well as time.** There are *n* allocations of steadily increasing size, each one orphaning the previous result the moment it is filled. ## The fix, and why it is cheaper Separate accumulating from combining: 1. Push each row into a cheap growable container, which over-allocates and so amortises its own growth to roughly constant work per push. 2. When the loop ends, combine the entire collection in one step. That final step allocates each column's buffer exactly once, at the final length, and copies each row exactly once. Total work is proportional to *n* rather than to *n* squared, the output is identical value for value, and the code is barely longer. | | combine on each iteration | collect, then combine once | |---|---|---| | allocations | one per row, each larger | one per column | | row-copies | roughly n squared over two | n | | cost of the last row | proportional to n | the same as the first row | | peak memory | old result plus new result | the collection plus the result | ## Where this does not hold This is the cost of a particular evaluation strategy, not a law, and the designs in this family genuinely differ: - **Where each step materialises a new full-length result** - the common eager case, and the one the arithmetic above describes - it is exactly quadratic. - **Under deferred evaluation**, a design where writing the operation only records what is to be done and nothing runs until the answer is actually asked for, repeated combination records *n* small operations and materialises once at the end. No intermediate is built, so there is no quadratic copying. Peak memory when it does materialise is still the whole result. - **Where a column is a genuinely growable buffer** that over-allocates and appends in place, growth amortises and the build is linear, at the price of carrying spare capacity. So the honest sentence is not *appending rows in a loop is quadratic*. It is *where each combination materialises a new result, appending rows in a loop is quadratic - and that is the commonest case, so assume it until you have established otherwise.* ## Why this cost outranks the others A record loop pays several fixed costs per row: resolving at run time what the values are, wrapping each one as a language object, assembling a record that is not stored anywhere. Those are constants. They make the loop slower by some factor, and that factor does not change as the input grows. The recopying accumulation is different in kind, because its share of the total **grows with the input**. At a thousand rows it is a rounding error beside the per-value costs; at a million it is the entire runtime and the others are the rounding error. That is why the first diagnostic question about a slow record loop is not which part of the body is expensive, but whether the time grows like the input or like its square. The answer reorders everything else.
- How do you tell this apart from the per-value costs of the same loop?Scale the input. Per-value costs are a constant per row, so doubling the rows roughly doubles the time. A combination that copies the whole accumulation on each step is quadratic, so doubling the rows roughly quadruples it. One measurement at two sizes separates them, and no amount of reasoning about the loop body will.
- Is every design quadratic here?No. Where each combination materialises a new full-length result, it is. Designs that only record the operation and materialise once at the end never build the intermediates. Designs offering a genuine append into an over-allocated buffer amortise the growth instead. Establish which of the three you are on before quoting a cost, because the three answers differ by orders of magnitude.
- Why is one combination at the end cheaper than n small ones?Because it allocates each column's buffer a single time at the final length and copies each row exactly once. The repeated form allocates n times and copies row one n times, row two n-1 times, and so on down. Same values out, work proportional to n rather than to n squared.
Adding a line to a letter by retyping the whole letter each time. Line five costs four lines of retyping, line five hundred costs four hundred, and the total is not five hundred lines of work but something nearer a hundred and twenty-five thousand. Jotting every line on a scrap and typing the letter once at the end costs five hundred. That is exactly what a combination that materialises a new result on every step does, and what collecting first avoids.
saying these in an interview costs you the question
- Calls it slow without noticing the per-iteration cost is growing.
- Thinks a row append writes into spare space at the end.
- Benchmarks at a thousand rows and declares the pattern fine.
- Blames the per-value costs when the curve is clearly superlinear.
- Assumes every design pays it, including ones that materialise once.