The problem › Same work, different speed
Two loops walk into a matrix
Here are two loops. CS:APP calls them sumarrayrows and sumarraycols, and they are the most famous pair of functions in the book. Both sum every element of the same 4096×4096 float matrix. Both execute exactly 16.7 million additions, touch exactly the same 64 MB of data, and compile to nearly identical instructions. One merely swaps the loop order of the other.
// row-major walk
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
sum += a[i][j];// column-major walk
for (j = 0; j < N; j++)
for (i = 0; i < N; i++)
sum += a[i][j];Predict first
Commit before reading on: how do these two loops compare in wall-clock time on a real machine?
The mechanism › The two habits caches bet on
Spatial and temporal locality
Chapter 0.5 said the cache is a statistical bet. Now name the statistics: the principle of locality, which CS:APP calls "an enduring concept that has enormous impact on the design and performance of hardware and software systems." Temporal locality: a memory location referenced once is likely to be referenced again multiple times in the near future (loop counters, accumulators, hot functions). Spatial locality: if a location is referenced, nearby locations are likely to be referenced soon after (arrays walked in order, struct fields used together). The blunt version: programs with good locality run faster than programs with poor locality. Caches reward both habits: temporal by keeping lines around, spatial by fetching 64 bytes when you asked for 4.
The unit of analysis is the stride. Visiting every element of a contiguous array in order is a stride-1 (sequential) reference pattern; visiting every kth element is stride-k. As stride grows, spatial locality decays, and CS:APP reduces the whole story to one formula: a stride-k pattern (k in words) costs an average of min(1, (wordsize × k) / B) misses per loop iteration.
Apply it to each loop. C stores a[i][j] row-major: row 0's 4096 floats, then row 1's, one long byte run, chapter 0.1's adjacency. The row walk is stride-1: k = 1, 4-byte floats, B = 64 → min(1, 4/64) = 1 miss per 16 accesses. The first touch of each line misses and hauls in 64 bytes; the next 15touches hit. That mhhh…mhhh… rhythm is CS:APP's own hit/miss table, and with a cold cache it's the best you can do.
The column walkis stride-4096 in floats: 16 KB between consecutive accesses. Every access lands on a fresh line; the 15 neighbors that rode along are ignored, 0.5's 94% wasted traffic, now on every access. Could the lines survive until the walk comes back for column j+1? Each column marches through 4096 distinct lines (256 KB of traffic), and the 64 MB matrix dwarfs your 30 MB L3. The working set exceeds capacity, so by the return trip everything has been evicted: textbook capacity misses. The book states the general law: with a stride-N walk of an array larger than the cache, "each and every access of a[i][j] will miss!"Ostrovsky's stride experiment shows the same cliff from the other side: step sizes 1 through 16 all run in the same time (same lines touched), and only past 16 ints (one 64-byte line) does the loop actually speed up.
SourcesCS:APP 3e §6.2 · pp. 640–644CS:APP 3e §6.5 · pp. 669–672
The number › Your turn
Derive the gap, no measurement required
Compute the number › AMAT for each walk, from 0.5's arithmetic
| floats per line | 64 B ÷ 4 B = 16 |
| row-walk misses | min(1, 4·1/64) = 1/16 per access |
| row-walk AMAT | 1 + (1/16 × 90) ≈ 6.6 ns |
| col-walk misses | min(1, 4·4096/64) = every access |
| col-walk AMAT | 1 + 90 = 91 ns |
| ratio | 91 ÷ 6.6 ≈ 14 |
| Result | ≈ 14× from napkin AMAT; CS:APP measured 25× |
An order of magnitude, computed on a napkin before touching a compiler, and the same magnitude class as the book's measured 25×. (The exact factor depends on how much the L2/L3 and the prefetcher soften each miss and on how well the row walk streams; direction and magnitude class never change.) This is the chapter-0.3 lesson wearing new clothes: both loops move the same useful bytes; one of them pays latency on every line.
The same analysis scales up. CS:APP closes chapter 6 by writing matrix multiply six ways: every permutation of the i, j, k loops. All six do identical arithmetic; their inner-loop miss counts range from 0.25 to 2.0 per iteration, and the fastest class runs almost 40× faster than the slowest for large n. Better yet: miss rate predicts the ranking better than the total number of memory accesses does; the class doing more loads but fewer misses wins. Loop interchange, the transformation you just watched, is the whole trick.
interactive · coming soon
TraversalRace: same loop, two orders
Planned interactive: both walks race over a live matrix, byte runs lighting up line by line, with running miss-rate meters and a wall-clock gap you predict before pressing run.
The full story › the memory mountain
CS:APP §6.6 turns this chapter into a landscape. Measure read throughput while sweeping working-set size (temporal locality) and stride (spatial locality) and you get a surface: the memory mountain. On the book's Core i7 Haswell: an L1 ridge reading over 14 GB/s, a main-memory floor around 900 MB/s (more than an order of magnitude top to bottom), with ridges of temporal locality exactly where the working set fits in L1, L2, L3 (32 KB / 256 KB / 8 MB on that machine), and slopes of spatial locality falling as stride grows. Even on the memory floor, spatial locality is worth 8×: the highest point of the main-memory ridge is a factor of 8 above its lowest. On your Intel Core i9-12900K, expect the cliffs at 48 KB, 1.25 MB, and 30 MB. Every program you will ever profile lives somewhere on this mountain; fast code is code that stays on the plateau.
Two honest asterisks. There is a flat ridge at stride-1 where throughput stays ~12 GB/s even for working sets far beyond L2. That's the hardware prefetcherrecognizing sequential patterns and fetching lines before they're asked for, one more reason stride-1 is king; it softens the column walk's cliff until stride or working set defeats it. And once stride reaches the line size (8 words of 8 bytes on that machine), every read misses and throughput flattens at the rate lines can be hauled up, exactly the "one access per cache line" regime the column walk lives in. (Blocking, restructuring loops to reuse a cache-sized chunk before moving on, buys temporal locality on machines without good prefetching; the 0.X capstone runs the mountain on your own machine.)
Locality is the contract between your code and the hierarchy: touch what you just touched (temporal), touch what sits adjacent (spatial), and the cache pretends memory is fast. The rules fit on an index card: repeated references to the same variables are good; stride-1 is good; the smaller the stride, the better. And the same loop, reordered, swings 25× on a real machine. Loop order is not style; it is a performance decision you can now price by hand.