The cache is not automatic — you have to earn it
By now you know the machinery. The memory wall means a miss to main memory can cost a hundred-plus cycles, the cache hides that latency by keeping recently used data close, and whether you hit or miss is decided by the principle of locality. Here is the part that surprises beginners: none of that is something the cache decides for you. The hardware will faithfully cache whatever you touch — but which bytes you touch, and in what order, is entirely up to your code. Two programs that compute the exact same answer can differ by 5x or 10x in run time purely because one respects locality and the other tramples it.
Recall the two flavours of locality from guide two. Temporal locality says if you used a byte, you will probably use it again soon — so reusing data while it is still hot in the cache is free. Spatial locality says if you used a byte, you will probably use its neighbours soon — and this one has teeth, because the cache never moves a single byte. It always pulls in a whole cache line, typically 64 bytes, on every miss. Touch one byte and you have already paid to bring its 63 neighbours along; cache-friendly code is, more than anything, code that uses those neighbours before they get evicted.
The classic example: row-major versus column-major traversal
The cleanest demonstration is summing a large 2D array. In C, a matrix is stored row-major: the whole first row sits contiguously in memory, then the whole second row, and so on. So element [i][j] and [i][j+1] are right next to each other, while [i][j] and [i+1][j] are a full row apart. Now compare two loops that touch every element and produce the identical sum — they differ only in which index runs on the inside.
// A: row-major order — cache-FRIENDLY
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
sum += A[i][j]; // walks memory straight: ...A[i][j], A[i][j+1]...
// B: column-major order — cache-HOSTILE
for (j = 0; j < N; j++)
for (i = 0; i < N; i++)
sum += A[i][j]; // jumps N elements every step
// 64-byte line holds 8 doubles. Per line of 8 elements:
// A: 1 miss + 7 hits -> miss rate ~1/8 = 12.5%
// B: 1 miss per access -> miss rate ~100%, and each touched
// line is evicted long before you return to it.Loop A streams straight along memory: each miss drags in a line of 8 doubles, and the next 7 reads are hits — about one miss per eight accesses. Loop B leaps a whole row on every step, so each access lands on a different line; it pays a miss almost every single time, and worse, by the time the loop comes back to that line's neighbours it has touched N other lines and the line is long gone. The result is identical to the last bit, but loop B can easily run several times slower on a big array. This is the whole lesson of cache-friendly code in one picture: match your traversal order to your memory layout.
Loop tiling: shrinking the working set to fit
Sometimes good traversal order is not enough, because the data you must reuse is simply too big to stay in the cache between uses. The textbook case is matrix multiply, C = A x B. To compute one row of C you stream across all of B; by the time you start the next row, B has been completely flushed out and you reload all of it from memory again — and again, once per row. The working set (the set of lines you revisit within a short window) is larger than the cache, so temporal locality exists in principle but the hardware cannot exploit it.
The cure is loop tiling, also called blocking. Instead of sweeping across the entire matrices, you chop the work into small square tiles — say 32 by 32 — sized so that the tiles of A, B, and C you are currently using all fit together in the cache at once. You do all the arithmetic that touches those tiles before moving on, so every line you load is reused many times while it is hot, then never needed again. You have not changed a single multiply or add; the answer is bit-for-bit identical. You have only reshaped the loop nest so the working set shrinks to fit the cache, converting a flood of misses into a stream of hits.
A field guide to friendly (and hostile) habits
Most cache-friendliness boils down to a handful of habits, each of which is just locality wearing different clothes. Walk arrays in storage order so you exploit spatial locality and let the hardware prefetcher — which spots a steady stride and fetches lines ahead of you — do its job. Prefer compact, contiguous layouts: an array of plain numbers beats a linked list of nodes scattered across the heap, because chasing pointers turns every step into a fresh, unpredictable miss. And when you process a big dataset several ways, do as much as you can per element while it is hot, rather than making many separate passes that each re-stream the whole thing from memory.
Two habits matter especially once you reach multiple cores. First, watch your data structure layout: storing related fields together (so one cache line carries everything a piece of work needs) beats scattering them, and sometimes a "struct of arrays" beats an "array of structs" precisely because the inner loop then touches contiguous fields. Second, beware false sharing — when two cores update different variables that happen to live on the same cache line, the cache coherence protocol forces the line to bounce back and forth between them as if they were fighting over shared data, even though logically they are not. Padding hot per-core variables onto separate lines fixes it. (False sharing is the multicore rung's headline; here just notice that it, too, is a locality story.)
Measure, do not guess — and stay honest about the trade
A warning before you optimise everything in sight. Cache effects are invisible in the source code — both loops in our example look equally innocent — so intuition is unreliable and you must measure. A profiler can report cache miss rates directly, and a simple wall-clock timing on a realistically large input will already reveal a row-major-versus-column-major gap. Crucially, cache tuning only pays off where the program is actually memory-bound and the data is too big for the cache; on small arrays everything fits and the layout barely matters. This is just make the common case fast applied honestly: spend your effort on the hot loop over the big array, not the cold setup code.
And keep the iron law in view. Cache-friendly code wins by lowering the effective cost of memory accesses — it shrinks the stall part of CPI, which the iron law (run time = instruction count x CPI x cycle time) tells us is one of only three levers on speed. It does not magically execute fewer instructions, and it cannot speed up code that was never waiting on memory in the first place. Its power is real but bounded: it converts misses into hits, nothing more. When the next rungs add more cores, GPUs, and accelerators, locality does not retire — it gets more important, because feeding many hungry compute units without choking on memory is the central problem of all of them.
- Walk memory in storage order (row-major in C) so each loaded line is fully used and the prefetcher can run ahead.
- When the working set is too big, tile (block) the loops so the actively reused data fits in cache — same arithmetic, far fewer misses.
- Prefer compact contiguous layouts over pointer-chasing structures, and pad hot per-core variables to dodge false sharing.
- Measure with a profiler on realistically large data, and only optimise the memory-bound hot loops where it actually pays.