Why can a column-order scan of a huge row-major elevation grid run an order of magnitude slower than a row-order scan?
answer
- count the operations, then count the jumps
- how far apart are vertical neighbours
- what does big-O assume about access cost
- the label is the same, the constant is not
- match traversal order to storage order
basics
~20 sBoth loops touch the same number of cells, but row-major storage puts a row's cells next to each other. A row-order scan walks memory one slot at a time; a column-order scan jumps a full row width per step, so each access lands in a different region.
solid answer
~50 sBig-O counts operations, and both nested loops perform `rows * cols` of them — that is why the label is the same and the runtime is not. Big-O silently assumes every memory access costs the same, and on real hardware it does not. In row-major storage, cells `(r, c)` and `(r, c+1)` are adjacent slots, while `(r, c)` and `(r+1, c)` are `cols` slots apart. Scanning row-order therefore walks memory as one continuous sweep and every fetch brings along values the loop is about to want; scanning column-order steps by a full row width, so each fetch is used once and then discarded. On a 10^4 by 10^4 grid — a hundred million cells, far too large to hold in any fast memory — that difference shows up as an order-of-magnitude gap. The fix is to make the traversal order match the storage order, or to change the storage order to match the dominant traversal.
code
pseudocode · 10 lines// elevation grid stored flat, row-major: cell (r, c) at r*cols + c
sum = 0
for r in 0..rows-1
for c in 0..cols-1
sum = sum + elev[r * cols + c] // next access is 1 slot away
...
sum = 0
for c in 0..cols-1
for r in 0..rows-1
sum = sum + elev[r * cols + c] // next access is cols slots awaygo deeper
Know that a row-major grid stores each row as a contiguous run, so walking along a row moves one slot at a time while walking down a column jumps by the row width. Be able to say which loop order is the contiguous one.
Explain why the two loops share a complexity label and not a runtime: big-O counts operations under a uniform-access-cost model, and memory order lives entirely in the constant factor. Name the stride between vertical neighbours.
Demonstrate the diagnosis and the fix: time both orders at two grid sizes and show the ratio widening, then choose between interchanging the loops, changing the storage order, transposing once, or tiling — and say when the honest answer is to leave it alone.
Own the layout decision for the workload as a whole. Decide whether the grid's canonical order should follow the dominant access pattern, what a second transposed copy costs against a memory ceiling, and how a portable routine avoids depending on a convention that differs between ecosystems.
## Two orders for the same grid A rectangular grid must be flattened onto a one-dimensional memory line, and there are two natural agreements about how. - **Row-major**: the whole of row 0, then the whole of row 1, and so on. The address of cell `(r, c)` is `r * cols + c`. Horizontal neighbours are 1 slot apart; vertical neighbours are `cols` slots apart. - **Column-major**: the whole of column 0, then column 1. The address is `c * rows + r`. Now vertical neighbours are adjacent and horizontal neighbours are `rows` apart. Neither is better in the abstract. What matters is whether the order you *store* in matches the order you *walk* in. ## Why the complexity label hides the difference Both nested loops execute the body `rows * cols` times. Counting operations, they are identical: `O(rows * cols)`, linear in the number of cells. That analysis is correct and it is also the source of the wrong answer, because the standard cost model behind it assumes **uniform access cost** — that reading any slot costs the same as reading any other. Real machines have a memory hierarchy: a fetch pulls in a small contiguous block, and the hardware speculatively pulls further blocks when it detects a sequential walk. A row-order scan spends one fetch and then consumes several useful values from it, over and over. A column-order scan consumes one useful value per fetch and throws the rest of the block away before returning to it much later — by which time it has been evicted by the hundred million other cells the scan touched in between. So big-O is not lying; it is answering a different question. It bounds how the work **grows**, and the two orders grow identically. The constant factor is where memory order lives, and constant factors are exactly what a production latency budget is made of. ## When the gap appears, and how large it gets The gap is not a fixed multiplier, and quoting one as a law is a mistake. It depends on how many values fit in a fetched block (so on the element size), on the grid width, and on the machine. What is reliable is the **shape** of the effect: - On a small grid that fits entirely in fast memory, both orders run at nearly the same speed. The strided scan re-reads values that are still close at hand. - As the grid outgrows the fast tiers, the strided scan starts paying a fresh fetch per cell and the ratio opens up. At `10^4 x 10^4` — a hundred million cells — an order of magnitude is an unsurprising measurement. - If the per-cell work is heavy (a transcendental function, a branchy classification), the memory cost is amortized against real computation and the ratio shrinks. The effect is largest exactly when the body is cheap, like summing elevations. This is also why the honest way to answer the question in an interview is "I would time both orders on the same data at two sizes": the ratio growing with grid size is the signature that confirms the diagnosis rather than a guess. ## The same loop is the fast one in one ecosystem and the slow one in another Storage order is a convention, and mainstream ecosystems did not agree on it. Grids in C-descended languages are row-major, while Fortran- and MATLAB-descended numerical stacks are column-major, and array libraries in other ecosystems let you choose per array. A nested loop copied between those worlds without changing the loop order keeps its complexity and inverts its performance. That is the clearest evidence that the layout, not the loop, is the thing being asked about — and the reason a portable grid routine either queries the layout or is written to be layout-agnostic. ## What to do about it 1. **Interchange the loops.** If the computation is order-independent — a sum, a per-cell transform, a maximum — simply put the fast-varying index in the inner loop. Free, and usually the whole fix. 2. **Change the storage order.** If the workload is genuinely column-dominant (per-column statistics over an elevation grid, say), store column-major and the same reasoning runs the other way. 3. **Transpose once, then scan many times.** Where a column-dominant phase follows a row-dominant one, paying a single transposition amortizes across all subsequent passes. It costs a full extra copy of the grid unless done in place. 4. **Block the traversal.** When both orders are needed at once — combining a row aggregate with a column aggregate in one pass — walk the grid in small rectangular tiles sized so a tile's rows stay resident together. Each tile is scanned row-order internally, so both aggregates advance without long strides. 5. **Do nothing.** If the grid is small, or the pass runs once at startup, or per-cell work dominates, the difference is unmeasurable and the clearer loop order wins. ## The claim to state carefully The precise statement is: *traversal order does not change the asymptotic complexity of a full grid scan; it changes the constant factor, by an amount that grows with the grid size and can reach an order of magnitude.* Saying "column-order scanning is O(n^2)" is wrong. Saying "order is just style because both are O(rows*cols)" is also wrong. Both halves matter.
- The workload genuinely needs per-column statistics over this grid. What are your options?Store the grid column-major so the dominant access becomes the contiguous one; or transpose once up front and amortize that cost across every later pass; or, if both row and column aggregates are needed in a single pass, walk small rectangular tiles so each tile's rows stay resident while both accumulators advance. Choose by counting how many column passes there are per transposition.
- How would you confirm that memory order, not something else, is the cause of the slowdown?Time both loop orders over the same data at two or three grid sizes. If memory order is the cause, the two run at nearly the same speed while the grid is small and the ratio widens as it grows — the signature of a strided walk outgrowing fast memory. A cause independent of layout, such as a bounds check or a branch in the body, would show a roughly constant ratio instead.
- When is column-order traversal of a row-major grid not worth fixing?When the grid is small enough to stay entirely in fast memory, when the pass runs once rather than in a hot path, or when the per-cell work is expensive enough to dominate the access cost. The effect is largest precisely when the loop body is cheap; with heavy per-cell computation the ratio collapses and the clearer loop order should win.
saying these in an interview costs you the question
- Says loop order is style because both are O(rows*cols)
- Claims column-order traversal changes the complexity to quadratic
- Thinks row-major means rows are processed first, not stored first
- Quotes a fixed slowdown factor as if it were a constant of nature
- Assumes the effect is the same on a tiny grid as on a huge one
- Believes swapping to nested row arrays removes the stride penalty