When You Cannot Ask the Next Question Yet
Some loops use almost no memory bandwidth and are still dominated by memory. Each access must complete before the next address is even known, so the hardware's ability to overlap misses is worth nothing, and the loop runs at one DRAM round trip per step.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
One outstanding access at a time
A modern core can track several cache misses simultaneously. When addresses are independent, this is what makes memory fast in aggregate: ten concurrent misses cost roughly what one costs, because their latencies overlap. That capability is Misses That Overlap Are Nearly Free, and it is the reason a sequential array scan achieves high throughput despite every line coming from DRAM.
A dependent chain removes the capability entirely. If the next address is the result of the current load, there is nothing to overlap — the hardware genuinely does not know where to look next. Out-of-order execution cannot help, because out-of-order execution reorders instructions whose operands are ready, and here they are not. Prefetching cannot help either, because prefetchers predict addresses from patterns, and a chain of pointers into a heap has no pattern to detect.
So the loop runs at one full memory round trip per element. Bandwidth utilisation is negligible — a handful of bytes in flight at any moment — while the loop is nonetheless entirely memory-bound.
The mirror image of bandwidth-bound
It is worth putting the two regimes side by side, because their signatures are almost exact opposites and the confusion between them is the most common diagnostic error in memory performance work.
A bandwidth-bound loop shows near-peak memory throughput, high stall time, and scaling that plateaus when cores are added. A latency-bound loop shows near-zero memory throughput, high stall time, and scaling that continues nearly linearly with cores — because each core independently has its single outstanding miss and they do not contend for a saturated bus.
That last point is the practical consolation: latency-bound work parallelises well even though each thread is slow. If you have many independent chains to walk, throwing cores at it genuinely helps, which is not true of the bandwidth-bound case.
| Signal | Latency-bound | Bandwidth-bound |
|---|---|---|
| Achieved memory bandwidth | Very low | Near machine ceiling |
| Outstanding misses per core | About one | Many |
| Effect of adding cores | Scales well with independent work | Plateaus quickly |
| Effect of wider SIMD | None | None |
| Effect of narrower data types | Small — the chain length is unchanged | Large — directly reduces bytes moved |
| Effect of converting to arrays | Large — addresses become predictable | Modest |
What actually helps
The only real fix is to remove the dependency, which almost always means changing the data structure. Converting a linked structure into an array makes every address computable in advance, restoring both prefetching and memory-level parallelism at once — the reasoning developed in Both Are O(n). One Is Far Slower..
Where the structure must stay pointer-based, the next best lever is to walk several independent chains simultaneously. Interleaving four traversals in one loop gives the hardware four independent addresses to work on, so four misses can be outstanding and the effective cost per element drops accordingly. This works well for batch lookups into a hash table or forest of trees, and is a standard technique in database internals.
Increasing node size so that more useful data arrives per miss also helps, which is exactly why B-trees exist: a wide node amortises one expensive access over many keys. That connection is developed in Cache-Aware Algorithms, and shows up concretely in B+ Tree Internals: Pages, Splits, Merges.
1// walk a single list2sum = 03node = head4while (node != null) {5 sum += node.value6 node = node.next // next address unknown until now7}8 9// effective cost: N x full memory latency1// walk four lists at once2a = head1; b = head2; c = head3; d = head43while (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 10// the four "next" loads are independent, so their11// latencies overlap: roughly N x latency / 4 for 4x the workThe total number of memory accesses is unchanged and so is the total bytes moved. What changed is how many accesses can be in flight simultaneously. This is the clearest practical demonstration that memory-level parallelism, not bandwidth, is the scarce resource in pointer-heavy code.
Key points
- A dependent load chain permits exactly one outstanding memory access, so the loop pays full latency per element.
- Out-of-order execution and prefetching both fail here: one has no ready operands, the other has no pattern to predict.
- Latency-bound loops use almost no bandwidth while being entirely memory-bound — the opposite signature to streaming code.
- They do scale with cores when there is independent work, unlike bandwidth-bound loops.
- Fixes are structural: convert to arrays, interleave independent chains, or widen nodes so each expensive access returns more useful data.
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.
- 1Load → miss entry: the dereference misses cache and occupies a single miss-tracking entry.
- 2Miss entry → DRAM: the request goes out; no further dependent load can be issued because its address is the value in flight.
- 3Out-of-order window → stall: the scheduler finds no independent memory work to overlap, so the window fills and retirement stalls.
- 4DRAM → core: the value returns, and only now is the next address computable.
- 5Repeat: the cycle serialises, giving one full round trip per element regardless of available bandwidth.
- • "Bandwidth is low, so memory is fine." Low bandwidth with high memory stalls is the defining signature of this regime.
- • "The CPU is out-of-order, so it will hide the latency." It hides latency only when there is independent work available, and a dependency chain provides none.
- • "Prefetching will fix it." Prefetchers extrapolate from patterns; a chain of heap pointers has none to extrapolate from.
Consequences, controls and cost
- • Linked lists, trees and graph traversals underperform arrays by far more than their asymptotic complexity suggests.
- • Hash-table lookups over large tables behave much worse than their O(1) description implies, because each probe is a dependent random access.
- • Adding memory channels or faster memory produces almost no improvement.
- • Convert pointer-linked structures into contiguous arrays where the access pattern allows — the largest single win available.
- • Interleave several independent traversals so multiple misses are outstanding simultaneously.
- • Widen nodes so each unavoidable miss returns more useful data, the principle behind B-tree node sizing.
- • If the structure and access pattern are both fixed, accept the floor: this is genuinely latency-limited and no code tuning removes it.
- • Check memory stall cycles alongside achieved bandwidth — high stalls with low bandwidth localises the problem to dependency chains.
- • Compare traversal of the same data as a linked structure versus as an array; a large gap with identical element counts confirms it.
- • Interleave two independent traversals experimentally; if throughput nearly doubles, memory-level parallelism was the constraint.
- • Converting to arrays sacrifices cheap insertion and removal, which is often exactly why the linked structure was chosen.
- • Interleaving traversals complicates code considerably and only applies when several independent traversals genuinely exist.
Scope
§224 — what these claims are specific to.
- GENERALDependency-chain serialisation applies to any out-of-order machine with caches. The number of concurrent misses a core supports is MICROARCH-SPECIFIC, which changes the size of the win from interleaving but not its existence.