Spatial Locality
If you touch an address, you will probably touch its neighbours soon. Hardware bets on this at every level — line size, prefetchers, DRAM row buffers — so code that walks memory in order gets most of its data effectively for free, and code that scatters pays full price for every element.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
Two ways to visit the same bytes
Spatial locality is the tendency of programs to access addresses near ones they have recently accessed. Hardware exploits it in at least three places: lines bring neighbours along (Memory Moves in Lines, Not Variables), prefetchers detect strides and fetch ahead (Prefetching: The Hardware Guesses What You Will Read Next), and DRAM row buffers make consecutive accesses within a row much cheaper than jumping between rows (How DRAM Is Organised).
That stacking is why the effect is so large. A sequential walk wins at every level simultaneously; a scattered walk loses at every level simultaneously. The gap is not the sum of three small effects but their product, which is why measured differences of five or ten times on identical arithmetic are unremarkable rather than surprising.
The matrix example is the canonical demonstration precisely because both versions are obviously "the same work". Row-major traversal of a row-major array is contiguous; column-major traversal of the same array strides by a whole row each step. Whether that stride costs you depends on the row length relative to your cache — which is why the effect appears as the matrix grows.
| Row-major traversal | Column-major traversal | |
|---|---|---|
| Address step per iteration | One element forward | One full row forward |
| Lines fetched per element | About 1 / (line ÷ element size) | About 1 |
| Bytes of each line used | All of them, eventually | Only the element you asked for |
| Prefetcher behaviour | Detects the stride and runs ahead | May detect a large stride; often cannot help |
| DRAM row buffer | Consecutive hits within a row | Row change per access, in the worst case |
| Scaling with N | Stays efficient | Degrades as a row exceeds cache capacity |
Layout order is a property of your data structure, not a universal law
It is easy to over-learn this lesson as "iterate rows before columns". The actual rule is *iterate in the order your data is stored*, and storage order is a property of the language, library or format you are using — not of mathematics. C and C++ arrays are row-major; Fortran and Julia are column-major; NumPy defaults to row-major but supports both and will happily hand you a transposed view whose logical rows are not contiguous at all.
So the diagnostic question is never "am I looping rows first" but "does my innermost loop step through adjacent addresses". For a transposed view or a strided slice, the answer can be no even though the code looks textbook-correct. This is a place where checking the actual strides beats reasoning from the shape of the loop.
The same reasoning generalises past arrays. Walking a contiguous vector of objects has good spatial locality; walking a container of pointers to heap-allocated objects usually does not, because the objects are wherever the allocator put them (Pointer Chasing: The Address You Do Not Have Yet). The structure that looks equivalent in a complexity table can differ completely in adjacency.
1import numpy as np2 3a = np.zeros((4096, 4096), dtype=np.float32)4print(a.strides) # (16384, 4) -> last axis is contiguous5 6b = a.T # a transposed *view*, no copy7print(b.strides) # (4, 16384) -> last axis strides a whole row8 9# Identical-looking loops over `a` and `b` have completely10# different memory behaviour. Check strides, not loop order.What to do when the access order is not yours to choose
Sometimes the traversal is fixed by the problem — a graph algorithm follows edges, a hash lookup jumps to a bucket, a database follows a pointer to a child node. In those cases the productive move is not to reorder the visits but to change the layout so the visits land closer together.
That is what a great many "cache-friendly data structure" designs actually are: they trade some structural elegance for adjacency. Storing a tree in a flat array in traversal order, packing children contiguously, using indices instead of pointers, or grouping records that are read together are all layout changes made to manufacture spatial locality that the access pattern would not otherwise have. Cache-Aware Algorithms treats this systematically.
And sometimes the honest answer is that the workload has no exploitable adjacency, in which case you are latency-bound and the lever is overlapping misses rather than avoiding them (When You Cannot Ask the Next Question Yet, Misses That Overlap Are Nearly Free). Knowing which of these three situations you are in is worth more than any individual trick.
| What you control | The move | Cost |
|---|---|---|
| Access order is free to change | Traverse in layout order — usually a one-line edit | Essentially none; the cheapest fix in the domain |
| Order is fixed, layout is yours | Change the layout to put co-accessed data together | A migration, and a structure tuned to one access pattern |
| Adjacency exists, set is too large | Block the computation so each tile is reused while resident (Matrix Tiling: Same Arithmetic, Ten Times Faster) | A machine-specific tuning parameter |
| Neither order nor layout is yours | Overlap independent misses instead of avoiding them | Complexity, and it only helps latency-bound code |
Key points
- Spatial locality is exploited at three levels at once — line granularity, prefetchers and DRAM row buffers — so the effects multiply.
- The rule is "step through adjacent addresses", not "loop rows first"; storage order depends on the language, library and whether the view is transposed.
- Access order is usually the cheapest thing to change and often produces the largest single improvement in a memory-bound loop.
- When the order is fixed by the algorithm, manufacture locality by changing the layout instead.
- Some workloads genuinely have no adjacency to exploit; recognising that saves you from optimising toward something unreachable.
Loop Order & Locality
Change an input and watch which number moves — and which one refuses to.
Identical arithmetic, identical element count, identical complexity. Only the order changed. Column-major traversal of row-major storage touches a new line on essentially every access; tiling restores the reuse by keeping a block resident while it is used.
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1Loop → address stream: the innermost loop generates a sequence of addresses whose stride the hardware can observe.
- 2Stride → prefetcher: a detectable constant stride lets the prefetcher issue requests ahead of demand, hiding latency (Prefetching: The Hardware Guesses What You Will Read Next).
- 3Line fetch → neighbours: each fetched line carries adjacent elements, so subsequent iterations hit rather than miss.
- 4DRAM row → row buffer: consecutive addresses often fall in an already-activated DRAM row, avoiding an activation cost.
- 5Scattered stream → all three fail: no reuse within lines, no detectable stride, and frequent row changes.
- • Learning "rows before columns" as a rule and applying it to a column-major library, making things worse with confidence.
- • Assuming a loop over a NumPy view is contiguous because it iterates the last axis, without checking
strides. - • Believing an extra transpose pass must be slower because it is "more work", when it converts many line fetches into few.
- • Concluding a workload has poor locality when the real problem is capacity — the distinction is in Three Kinds of Miss, Three Different Fixes.
Consequences, controls and cost
- • Identical arithmetic can differ several-fold in runtime purely through traversal order.
- • The penalty grows with data size, appearing as a benchmark that "was fine in testing" and is not in production.
- • Transposing a matrix before a column-wise pass can be faster overall than the pass itself, despite the extra copy.
- • Structures using indirection show worse locality than their complexity analysis suggests ([[array-vs-linked-list]]).
- • Make the innermost loop step through adjacent addresses — check strides rather than trusting loop nesting order.
- • Transpose or reorder data once when the access pattern requires the other order repeatedly.
- • Store co-accessed fields and records together, converting an access pattern you cannot change into one that is contiguous.
- • Block or tile so each fetched region is fully exploited before moving on ([[matrix-tiling]]).
- • Prefer indices into flat arrays over pointer graphs where the structure permits ([[data-oriented-design]]).
- • Print or inspect the strides of the array or view you are iterating; a large innermost stride is the mechanism in plain sight.
- • Compare the same computation over an array and its transpose — the ratio is your local penalty for the strided pattern.
- • Sweep the inner dimension size and look for the point where the time per element steps up; that is a cache capacity boundary.
- • Watch cache-miss counters while changing only the loop order, holding the arithmetic constant.
- • Transposing or reordering data costs a pass over memory and extra space, which only pays if the reordered access happens enough times.
- • Layout changes for locality can conflict with layouts chosen for a different access pattern elsewhere in the program.
- • Blocking introduces a tuning parameter tied to cache size, which is machine-specific and needs re-measuring across targets.
Scope
§224 — what these claims are specific to.
- GENERALExploitation of adjacency is universal to cached architectures; the magnitude depends on line size, prefetcher aggressiveness and DRAM organisation, all of which vary by part
- PLATFORM-SPECIFICWhich traversal is contiguous depends on the language and library convention — row-major in C/C++/NumPy default, column-major in Fortran/MATLAB/Julia