Pointer Chasing: The Address You Do Not Have Yet
Any traversal where the next address comes out of the current load runs at one memory round trip per step. It is the mechanism behind slow lists, slow trees, slow graphs and hash lookups that underperform their O(1) label.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
The chain, and why nothing overlaps it
The defining shape is p = p->next, or equivalently node = node->child[k], or entry = table[hash].next. In every case the address for step i+1 is a value that arrives from step i. There is no way for the hardware to start step i+1 early, because it does not know where to look.
Every mechanism the CPU has for hiding memory latency depends on knowing an address ahead of time. Out-of-order execution reorders instructions whose operands are ready. Prefetchers extrapolate from observed address patterns. Memory-level parallelism issues several independent misses concurrently. A dependency chain defeats all three simultaneously, which is why the effect is so severe.
The result is a loop whose period is the load-to-use latency of whichever cache level holds the next node. If the structure fits in L1 this is cheap and the traversal is fast. If it lives in DRAM, each step costs a full round trip, and a depth-20 tree walk costs twenty of them.
Where it shows up beyond linked lists
Tree traversal is pointer chasing with a branch: each level's node address comes from the previous level. A balanced binary tree over a large dataset costs roughly log₂(n) dependent memory accesses, and if the tree does not fit in cache most of those are DRAM round trips. This is precisely why B-trees exist with wide nodes rather than binary branching — a node holding many keys turns log₂(n) dependent accesses into log_b(n), and each expensive access returns much more useful data.
Hash table lookup is pointer chasing in disguise. The hash is cheap arithmetic, but the bucket access is a random memory access into a large table, and if collisions are resolved by chaining, each probe is another dependent load. This is why O(1) lookup underdelivers at scale and why open addressing with linear probing often wins in practice: the probes are contiguous, so they share cache lines and the addresses are predictable.
Graph traversal is the worst case. Adjacency lists are pointer chasing with unpredictable fan-out, and the access pattern is genuinely random over a large region. This is why graph workloads are famously memory-latency bound and why specialised graph frameworks work so hard on layout and batching.
| Structure | The dependent load | Dependent accesses per operation |
|---|---|---|
| Linked list traversal | node.next | One per element |
| Binary tree search | node.left / node.right | About log₂(n) |
| B-tree search | child pointer in a wide node | About log_b(n) — far fewer |
| Hash lookup with chaining | bucket head, then entry.next | One plus chain length |
| Hash lookup, open addressing | contiguous probe sequence | Often one line, probes share it |
| Graph adjacency traversal | neighbour list, then neighbour node | One per edge, unpredictable |
The three things that actually help
First and best: remove the indirection. Store the data contiguously so addresses become computable. This is what converting a list to a vector does, what a flat adjacency array (compressed sparse row) does for graphs, and what open addressing does for hash tables.
Second: widen the nodes so that each unavoidable dependent access returns more useful work. This is the B-tree insight, and it applies well beyond databases — any tree over data that does not fit in cache benefits from higher fan-out, because the cost is dominated by the number of dependent accesses rather than by the comparisons within a node.
Third: batch independent chains. If you have many lookups to perform, interleaving them gives the hardware several independent addresses to work on at once, restoring memory-level parallelism even though each individual chain remains serial. Database engines do this deliberately for batched index probes, and it is the technique shown in When You Cannot Ask the Next Question Yet.
- Flatten: contiguous arrays make addresses computable, restoring prefetching and overlap.
- Widen: fewer, larger nodes means fewer dependent round trips per operation.
- Batch: interleave independent traversals so several misses are in flight simultaneously.
- Not helpful: more bandwidth, more cores per chain, wider SIMD, loop unrolling — none address the dependency.
Key points
- Pointer chasing is any traversal where the next address is the result of the current load.
- It defeats out-of-order execution, prefetching and memory-level parallelism simultaneously, because all three need addresses in advance.
- Cost is the number of dependent accesses times the latency of the level holding the data, not the instruction count.
- It underlies slow list, tree, hash-chain and graph traversals, which look cheap in complexity terms.
- Fixes are structural: flatten to arrays, widen nodes to reduce depth, or batch independent traversals.
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 and occupies a single outstanding-miss slot.
- 2Address dependency → issue stall: the next load cannot be issued because its address is the value currently in flight.
- 3Scheduler → no overlap: out-of-order execution finds no independent memory work, so the window fills with dependents.
- 4Prefetcher → no prediction: the address sequence has no stride or pattern to extrapolate from.
- 5Return → next issue: only when the value arrives can the following access begin, giving one round trip per link.
- • "The CPU is out-of-order, it will hide this." It hides latency using independent work, and a dependency chain provides none.
- • "Unrolling will expose parallelism." Unrolling exposes instruction-level parallelism; the addresses are still unknown, so no extra loads can issue.
- • "O(1) hash lookup is constant cost." It is a constant number of probes, each of which may be a full-latency random access.
Consequences, controls and cost
- • Tree and graph algorithms run far below their instruction-count potential on large datasets.
- • Hash tables with chaining degrade sharply once the table exceeds cache, despite constant-time complexity.
- • Adding cores helps only when there are independent traversals to run in parallel, not when one traversal is slow.
- • Flatten the structure into contiguous storage where the access pattern allows — the largest available win.
- • Increase node fan-out so each dependent access does more work, the principle behind B-trees.
- • Batch and interleave independent lookups to restore memory-level parallelism across chains.
- • Allocate nodes from an arena in traversal order so that, where flattening is impossible, locality is at least partially recovered.
- • Compare cycles per element against the memory latency of the level holding the structure; a ratio near one confirms a serialised chain.
- • Check outstanding misses or memory-level parallelism counters — roughly one indicates pure pointer chasing.
- • Interleave two independent traversals experimentally; near-doubling of throughput confirms the chain, not bandwidth, was the limit.
- • Flattening sacrifices cheap insertion and stable references, which is usually why the pointer structure was chosen.
- • Wider nodes waste space when partially filled and cost more comparison work per node visited.
- • Batching complicates control flow substantially and only applies when independent work genuinely exists.
Scope
§224 — what these claims are specific to.
- GENERALApplies to any out-of-order machine with caches. The number of concurrent misses supported is MICROARCH-SPECIFIC, which changes how much batching recovers but not that the chain serialises.