Cache-Aware Algorithms
Two algorithms with identical asymptotic complexity can differ by an order of magnitude in wall clock, because complexity analysis counts operations and hardware charges for data movement. Blocking, compact layouts and node sizes matched to the transfer granularity are all the same idea: arrange the work so that data pays its travel cost once.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
The cost model complexity analysis uses is not the machine's
Big-O counts operations under an implicit assumption: every memory access costs the same. That assumption made sense when it was formalised and is now wrong by two orders of magnitude between a register and DRAM (see The Memory Hierarchy). What the hardware actually charges for is *transfers* — a cache line moved from L3, a page fetched from storage — and an algorithm's transfer count is not determined by its operation count.
This is why the external-memory or cache-oblivious literature exists: it re-does the analysis counting block transfers instead of operations, and gets different answers. You do not need that machinery to benefit from the idea. The practical version is one question asked of any hot loop: *how many times does each piece of data travel, and could it travel fewer times?*
Note what this does and does not say. It does not say complexity analysis is useless — an O(n²) algorithm will lose to an O(n log n) one at large n no matter how cache-friendly it is, and choosing the right algorithm is still the first and largest lever. It says that *among algorithms of the same complexity class*, and at the sizes real programs actually run at, data movement usually decides the winner.
| Structure or approach | Operation count | What the hardware is charged for | Where the difference comes from |
|---|---|---|---|
| Array scan vs linked-list scan | Both O(n) | Array: one line per several elements. List: often one line per node | Contiguity and prefetchability — see Both Are O(n). One Is Far Slower. |
| Binary search tree vs B+ tree lookup | Both O(log n) | BST: one line per level. B+ tree: one line per *many* keys per level | Node size matched to the transfer unit |
| Naive vs tiled matrix multiply | Both O(n³) multiplies | Naive re-fetches a row or column per pass; tiled fetches a block once | Reuse while resident — see Matrix Tiling: Same Arithmetic, Ten Times Faster |
| Row-major vs column-major traversal | Both O(rows × cols) | One walks lines; the other touches one element per line | Stride versus layout — see Spatial Locality |
| Pointer-linked graph vs index-linked graph | Both O(V + E) | Pointers scatter; indices into an array stay dense | Allocation layout — see Pointer Chasing: The Address You Do Not Have Yet |
Three techniques that are all the same technique
Blocking (tiling) restructures a loop nest so that a chunk of data is brought in once and fully used before being evicted. This is the technique behind tiled matrix multiply, blocked transposes and cache-friendly sorts. It changes no arithmetic; it changes residency.
Sizing nodes to the transfer granularity is why a B+ tree beats a binary search tree for on-disk and increasingly for in-memory indexes. A binary tree pays one expensive access per *comparison*; a B+ tree pays one per *node*, and a node holds many keys. The fan-out is chosen so a node matches the unit the layer below actually transfers — a page for storage, a line or small multiple for memory. The database domain derives this from the storage side in Why B+ Trees: Fanout, Not Big-O and Pages: The Unit of Everything; the hardware reason is identical.
Compact, dense layouts reduce the number of lines a traversal touches at all. Struct-of-arrays for field-selective work (Array of Structs, or Struct of Arrays?), indices instead of pointers, and removing padding (Padding: Why Your Struct Is Bigger Than Its Fields) all shrink the bytes moved per useful byte consumed.
A fourth idea worth knowing by name rather than by implementation: cache-oblivious layouts such as van Emde Boas achieve good behaviour at *every* level of the hierarchy simultaneously, without being tuned to any particular cache size. They matter because they show the goal is not "tune to L2" but "arrange for reuse at whatever scale the machine has".
- Blocking — bring a chunk in once, finish with it, then move on. Same operations, fewer transfers.
- Fan-out sizing — make the node match the transfer unit, so one expensive access yields many useful comparisons.
- Dense layout — fewer bytes per element means fewer lines per traversal.
- Cache-oblivious layout — recursive structure that gets reuse at every level without knowing any cache size.
- The check that unifies them — count how many times each datum crosses a hierarchy boundary, and ask whether it needs to.
When this is worth doing, and when it is not
Cache-aware restructuring is not free. Tiling adds loop nests and a tile-size parameter that is machine-dependent. Struct-of-arrays fragments a conceptually cohesive object across arrays. Index-based graphs lose type safety that pointers gave you. All of these make code harder to read and harder to change, which is a real and recurring cost paid by every future maintainer.
The honest rule is the same one that governs all optimisation: do it where the measurement says it matters, which in practice is a small number of hot loops over large data. Applying it everywhere produces an unreadable codebase and a rounding-error speedup — the failure mode Data-Oriented Design, Without the Dogma warns about at length.
The good news is that the *analysis* is cheap even when the fix is not. Asking "how many times does this data move?" costs nothing, catches the worst offenders early, and often reveals that the answer is not a clever layout but a plainly better algorithm or simply doing the work in a different order.
Key points
- Complexity analysis counts operations and assumes uniform memory cost; hardware charges for transfers, so the two rank algorithms differently.
- Among algorithms of the same complexity class, data movement usually decides which wins at real sizes.
- Blocking, fan-out sizing and dense layouts are three expressions of one idea: make each datum pay its travel cost once.
- A B+ tree beats a binary tree for the same reason a tiled multiply beats a naive one — the unit of work is matched to the unit of transfer.
- The restructuring costs readability and adds machine-dependent parameters, so it belongs in measured hot paths, not everywhere.
Progressive depth
Overview
Two algorithms with the same big-O can have very different runtimes, because complexity counts operations while hardware charges for moving data. Arranging work so each piece of data is used fully while it is nearby is the single highest-leverage optimisation for large-data loops.
Practical
Three recurring techniques: block the loop so a chunk is reused while resident; size structure nodes to match the transfer unit, which is why B+ trees are wide; and make elements dense so more useful data arrives per line. Apply them in measured hot loops only — everywhere else they cost readability and buy nothing.
Advanced
The external-memory model re-does complexity analysis counting block transfers rather than operations, and produces genuinely different rankings. Cache-oblivious structures such as van Emde Boas layouts achieve near-optimal transfer counts at every level of the hierarchy simultaneously, without being parameterised by any cache size — which matters because a tuned constant is a portability hazard.
Internals
Transfer count is not the whole story: the hardware can overlap independent misses (Misses That Overlap Are Nearly Free), so an access pattern with many outstanding independent misses tolerates them far better than a dependent chain does. This is why a blocked traversal with predictable strides beats a pointer-linked one by more than the raw miss counts suggest — the prefetcher works on one and not the other, and the misses that remain are overlapped rather than serialised.
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.
- 1Algorithm → access sequence: the loop order and data structure together determine which addresses are touched, and in what order.
- 2Access sequence → line requests: the hardware translates that into cache-line requests; addresses within a line cost one transfer between them.
- 3Line requests → hierarchy traffic: each request that misses walks outward, and the working set decides at which level it stops (Working Set: Why Performance Falls Off a Cliff).
- 4Hierarchy traffic → stall cycles: misses that the CPU cannot overlap become stalls, which is where the wall-clock difference actually appears.
- 5Stall cycles → runtime: two algorithms with equal instruction counts diverge here, and no amount of instruction-level tuning closes the gap.
- • "It is O(n log n), so it is fast enough" — complexity bounds the growth rate, not the constant, and the constant is where the hierarchy lives.
- • "The tiled version does less work" — it does exactly the same arithmetic; it moves less data.
- • "Cache-friendly code is always worth writing" — outside hot loops it buys nothing and costs clarity permanently.
- • "We tuned the tile size, so it is optimal" — optimal on the machine you tuned it on, and possibly nowhere else.
Consequences, controls and cost
- • A structure that is theoretically optimal can lose badly to a "worse" one that fits the hierarchy — the standard example being linked structures against arrays.
- • Performance falls off a cliff at the input size where the working set stops fitting a level, rather than degrading smoothly.
- • Tuning constants such as tile size are machine-specific, so a value tuned on one machine can be wrong on the next.
- • Index and tree designs across databases converge on similar fan-outs, because they are all solving the same transfer-count problem.
- • Choose the right algorithm first — cache-friendliness never rescues an asymptotically worse choice at large n.
- • Restructure loops to reuse data while it is resident (blocking) before attempting anything more exotic.
- • Match structure granularity to transfer granularity: wide nodes, dense arrays, indices instead of pointers.
- • Shrink the element: remove padding and split rarely-used fields out, so more useful data arrives per line.
- • Measure the transfer count, not just the runtime, so you know whether you fixed the cause or got lucky.
- • Compare cache-miss counts per level before and after; a restructuring that helped should show fewer last-level misses for the same instruction count.
- • Plot runtime against input size and look for the knee where the working set exceeds a cache level — the knee moves when the layout changes.
- • Check instructions retired alongside runtime: if instructions are flat and runtime fell, you removed transfers rather than work.
- • Run on more than one machine before trusting a tuned constant.
- • Blocked and tiled code is substantially harder to read and to modify than the loop nest it replaces.
- • Tile sizes and fan-outs are machine-dependent parameters that silently become wrong as hardware changes.
- • Dense layouts such as struct-of-arrays fragment objects and can complicate ownership, serialisation and debugging.
- • The analysis effort is only repaid in genuinely hot code over genuinely large data.
Scope
§224 — what these claims are specific to.
- GENERALThe principle — hardware charges for transfers, not operations — holds on every machine with a memory hierarchy, which is all of them.
- SIMPLIFIEDThe cost scale is relative and illustrative. Real ratios vary by a factor of several between machines, and the L3-to-DRAM gap in particular depends on memory configuration and contention.
- PLATFORM-SPECIFICOptimal tile sizes and tree fan-outs depend on the specific cache sizes, line size and page size of the target machine; a value tuned for one is often wrong for another.
Misconceptions
Apply it
Where the rest of this lives
Whether a "dense array of objects" is actually dense in memory depends on the runtime: a language that boxes elements gives you an array of pointers, and the cache-aware layout you thought you wrote does not exist.