Misses That Overlap Are Nearly Free
A cache miss costs a great deal if the core has nothing else to do, and almost nothing if it does. Modern cores keep several misses outstanding at once, so ten independent misses can cost barely more than one — while ten dependent misses cost ten times as much. This is why miss counts alone never predict runtime.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
The core does not stop at the first miss
When a load misses, the core does not halt. Out-of-order execution lets it continue past the missing instruction, issuing any subsequent work whose operands are available — including further loads, which may themselves miss. The memory subsystem tracks each outstanding fill in a dedicated structure, and several can be in flight simultaneously. The result is that their latencies overlap rather than accumulate.
That overlap is bounded by two things. The first is the size of the structure tracking outstanding fills — once it is full, the core cannot issue another miss no matter how much independent work is available. The second is the reorder buffer: the core can only look so far ahead for independent work, and if the next independent load is beyond that horizon it might as well not exist. Both limits are firmly microarchitecture-specific.
The practical consequence is that "cost per miss" is not a constant. It ranges from nearly the full memory latency, when misses are serialized, down to a small fraction of it, when many overlap. Any performance model that multiplies a miss count by a fixed penalty will be badly wrong in one direction or the other.
Dependency is what destroys it
The condition for overlap is independence: the core must be able to compute the second address without waiting for the first load to return. Array traversal satisfies this trivially — every address is base plus index, computable immediately, so the core can run far ahead and issue many loads. Pointer chasing violates it absolutely: node->next cannot be known until node has arrived, so each miss must fully complete before the next can even be issued.
This is the real reason a linked list traversal is so much slower than an array traversal at the same asymptotic complexity, and it is a sharper explanation than "the array has better locality". Locality matters, but even a linked list whose nodes happen to be laid out contiguously suffers, because the *dependency* remains: the hardware prefetcher has nothing to predict from and the core has nothing independent to overlap. Pointer Chasing: The Address You Do Not Have Yet and Both Are O(n). One Is Far Slower. develop this from the data-structure side.
Because the constraint is dependency rather than data volume, the fixes are structural. Traversing several independent lists at once interleaves their chains and restores overlap. Storing indices into a contiguous array instead of pointers lets the core compute addresses ahead of the loads. Splitting one long chain into several shorter parallel ones converts a latency problem into a bandwidth one, which is a much better problem to have.
1# The next address is inside the value being loaded.2while (node) {3 sum += node->value;4 node = node->next; # cannot issue until this load returns5}6# 8 misses cost roughly 8 x miss latency1# Four independent traversals; the core can have2# four loads outstanding at once.3while (a || b || c || d) {4 if (a) { sum += a->value; a = a->next; }5 if (b) { sum += b->value; b = b->next; }6 if (c) { sum += c->value; c = c->next; }7 if (d) { sum += d->value; d = d->next; }8}9# 8 misses cost roughly 2 x miss latencyIdentical work, identical miss count, roughly a quarter of the stall time. Nothing about locality changed — what changed is how many independent misses the core could keep in flight at once.
What this means for prefetching and for measurement
Hardware prefetching is, in effect, a machine for manufacturing memory-level parallelism. It detects a regular access pattern and issues loads ahead of demand, so the data is already arriving when the core asks. That works precisely because the addresses are predictable without waiting for previous results — the same independence condition. It is also why prefetching does nothing for pointer chasing: there is no pattern to extrapolate, since the next address is data the prefetcher does not yet have. Prefetching: The Hardware Guesses What You Will Read Next covers the mechanism.
For measurement, the immediate implication is that a miss count is not a cost and must never be reported as one. Two functions with identical LLC miss counts can differ several-fold in runtime, and the counter that distinguishes them is stall cycles attributable to memory, not the miss count itself. This is the specific trap behind so many "we reduced cache misses by 30% and nothing got faster" reports.
The reverse also happens and is less well known: a change that *increases* miss count while increasing overlap can be a net win. Converting a dependent traversal into several independent streams may touch more memory and miss more often, and still finish sooner because the misses now happen concurrently. Optimising the miss counter is not the goal; optimising cycles is.
| Property | High MLP loop | Low MLP loop |
|---|---|---|
| Address computation | Independent of loaded values | Depends on the previous load's result |
| Misses in flight | Several, up to the hardware limit | One |
| Hardware prefetch | Effective — pattern is extrapolable | Useless — no pattern to predict |
| Cost per miss | A fraction of full latency | Approximately full latency |
| Typical shape | Array scan, matrix traversal, streaming | Linked list, tree descent, hash chain walk |
| The fix | Already near best case | Break the chain: interleave, use indices, restructure |
Key points
- Cores keep multiple cache misses outstanding, so independent misses overlap and cost far less than their sum.
- The limit is set by the structure tracking outstanding fills and by how far ahead the reorder buffer can look — both microarchitecture-specific.
- Dependent addresses destroy overlap entirely: pointer chasing sustains a memory-level parallelism of one.
- Hardware prefetching works by manufacturing this overlap, which is why it helps regular patterns and does nothing for chained loads.
- A miss count is not a cost; two loops with equal miss counts can differ several-fold in runtime.
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1Load → miss: a load misses the last-level cache and an outstanding-fill entry is allocated for it.
- 2Core → continue: out-of-order execution proceeds past the missing load to any instruction whose operands are ready.
- 3Independent load → second miss: another miss issues while the first is still in flight, and its latency overlaps.
- 4Structure full → stall: once all outstanding-fill entries are occupied, no further miss can issue regardless of available work.
- 5Dependent load → serialization: if the next address requires the previous result, no overlap is possible and each latency is paid in full.
- • Multiplying miss count by a fixed penalty to estimate cost, which is wrong by several times in both directions.
- • Concluding an optimisation failed because misses fell and runtime did not, without checking whether those misses were overlapping.
- • Assuming prefetching will rescue a pointer-heavy traversal.
- • Rejecting a restructuring because it increased total misses, when it increased overlap by more.
Consequences, controls and cost
- • Linked structures perform far worse than their miss counts suggest, while array scans perform far better.
- • Reducing cache misses can fail to improve runtime if the removed misses were already overlapping.
- • Restructuring to increase independent accesses can improve runtime while increasing total misses.
- • Prefetch-friendly access patterns get a compounding benefit: fewer misses and better overlap of the ones that remain.
- • Break dependency chains: interleave several independent traversals so the core has misses to overlap.
- • Replace pointers with indices into contiguous storage so addresses are computable before the data arrives.
- • Prefer layouts the hardware prefetcher can extrapolate — sequential or fixed-stride — over unpredictable indirection.
- • When a chain is irreducible, accept it and optimise elsewhere; some traversals are genuinely latency-bound and nothing local will fix them.
- • Stall cycles attributable to memory, alongside the miss count — the pair is the diagnosis, neither alone is.
- • Average outstanding fill occupancy where the chip exposes it, which is the most direct read on achieved MLP.
- • A controlled experiment: interleave two independent instances of the traversal and see whether throughput nearly doubles.
- • Achieved bandwidth — a latency-bound chained traversal uses very little of it, which is itself the tell.
- • Interleaving independent chains complicates the code substantially and increases register and cache pressure.
- • Index-based structures lose the type safety and convenience of pointers and can complicate ownership.
- • Restructuring for overlap can increase total memory traffic, which is a poor trade on a bandwidth-saturated system.
Scope
§224 — what these claims are specific to.
- MICROARCH-SPECIFICThe number of outstanding misses a core can sustain, and the reorder buffer depth that determines how far ahead it can find independent work, are design parameters that differ substantially between cores and generations.
- SIMPLIFIEDThe cost scale shows how overlap changes aggregate cost under idealised assumptions; real overlap is partial and depends on the surrounding instruction mix.