cache-friendly code (blocking and tiling)
Two cooks follow the identical recipe and produce the identical dish, but one finishes in an hour and the other in five. The difference is organization: the fast cook gathers and uses ingredients in batches close at hand, while the slow cook fetches a single item from the pantry for each step and walks back and forth all day. Cache-friendly code is the fast cook's discipline: writing programs whose memory access pattern respects locality, so the data the CPU needs is almost always already in the cache. The result is identical correctness with potentially many times the speed.
The two core techniques are loop ordering and blocking (also called tiling). Loop ordering means traversing data the way it is laid out in memory so you sweep through consecutive addresses and reap spatial locality — in a row-major language, loop over a 2D array row-by-row, not column-by-column, so each cache line you pull in is fully used before you move on. Blocking means breaking a computation over a large dataset into small sub-blocks (tiles) each sized to fit in the cache, and finishing all the work on one tile while it is resident before moving to the next. This converts capacity misses into hits: instead of streaming a huge matrix past the cache repeatedly (re-loading the same data on every pass), you load a tile once and reuse it many times, exploiting temporal locality the original loop order squandered.
The classic example is matrix multiplication. A naive triple loop on large matrices touches one operand in a cache-hostile order and re-reads it from memory over and over; a blocked version that multiplies cache-sized sub-blocks can run several times faster on the exact same hardware with the exact same result. This is the practical payoff of the whole chapter: caches are automatic, but their benefit must be EARNED. The honest framing is that the cache changes only speed, never the answer — so cache-friendly programming is invisible to correctness and easy to neglect, yet it is one of the highest-leverage optimizations a programmer can apply, often beating algorithmic micro-tweaks. The caveat is that the best tile size and loop order depend on cache sizes and the machine, so the tuning is real, sometimes fiddly work — but the principle, respect locality, is universal.
For a large matrix multiply C = A x B, the naive i-j-k loop re-streams B from memory for every row of A. Tiling into, say, 64x64 sub-blocks loads each tile of B once and reuses it across many rows — the same arithmetic, the same C, but often 3x-10x faster purely from better cache reuse.
Same result, very different speed: respect locality (loop order, tiling) and earn the cache's benefit.
Cache-friendly code changes ONLY speed, never the answer, which is why it is so easy to neglect — and why neglecting it leaves enormous performance on the table. The best tile size and loop order depend on the machine's cache sizes, so the principle is universal but the exact tuning is hardware-specific.