Dependent Loads and the Cost of Pointer Chasing

A pointer-chasing loop reads one word, computes an address from it, and reads again. On paper that is two instructions. In hardware it is a full memory latency taken serially, because the second load cannot begin until the first has completed. No amount of instruction-level parallelism helps: the processor can issue the dependent load ahead of time only if it knows the address, and it does not. This is the single largest structural cost in linked lists, trees, hash tables with chaining, and any node graph, and it is invisible in instruction counts.

The cost is not the number of misses. A program with many misses and good independence can hide most of them; a program with fewer misses and perfect dependence can hide none. Distinguishing the two is the first step in reasoning about memory-bound code, and the distinction is not property of the algorithm but of the data structure’s shape.

Latency hiding and the miss budget

The mechanism that hides memory latency is overlap. A modern out-of-order core can have dozens of loads outstanding at once, limited by the number of line fill buffers, the miss status holding registers, and the size of the reorder buffer. When a load misses, the core keeps issuing other work until either the missing line arrives or it runs out of independent work to start.

The useful quantity is Little’s law applied to memory: the achieved bandwidth equals the number of outstanding requests divided by the latency of each. If the memory system sustains, say, sixteen outstanding misses and each costs 200 cycles, then the throughput is on the order of one line per 12.5 cycles. To saturate that, the program must have sixteen misses in flight, which requires sixteen independent loads. A loop with one dependent load per miss has one in flight, and its throughput is one line per 200 cycles, a factor of sixteen below what the hardware can do.

That factor is the reason a linked list traversal can run at a small fraction of the arithmetic intensity of the equivalent array walk, even though both move the same number of logical bytes. It also explains why doubling the cache hit rate of a pointer-chasing structure can leave its runtime unchanged: the misses that remain are all serialised.

What the prefetcher can and cannot do

Hardware prefetchers recognise strides and repeated patterns in the sequence of addresses requested. A loop over a contiguous array produces a clean ascending sequence, and the prefetcher issues requests for lines several iterations ahead, converting misses into hits. A loop over a linked list produces an address sequence that depends on data the prefetcher has not seen, so there is no pattern to recognise. The prefetcher does nothing.

Two partial exceptions exist. Some prefetchers follow pointers within a single 4 KiB page, on the theory that a chain node’s next field often points to another node in the same page; this is a real mechanism in some designs and is not portable. And software prefetch instructions can be issued manually, but only when the address is known in advance, which for a dependent chain means speculating the next pointer before the current one has returned. Speculation succeeds when the structure has predictable shape, such as a tree traversal where several candidate children can be prefetched together, and fails when it does not.

The general result is that a dependent chain has a hard lower bound of one memory latency per node. If the nodes are in DRAM, that bound is a few hundred cycles per node, and no micro-optimisation of the node’s contents changes it. The only fixes that work attack the dependence itself.

Making the chain shallower

The most direct fix is to reduce the number of dependent steps. In a linked list, that means storing more than one element per node, so that a single dependent load yields several useful values. A node holding four elements makes the chain four times shorter for the same data, at the cost of wasting space when the list length is not a multiple of four and complicating insertion.

For trees, the equivalent is to widen the nodes. A binary search tree has a chain length of approximately log2(n) and each step is a dependent load. A B-tree node holding 64 keys reduces the depth by a factor of six for the same element count, since log64(n) is a sixth of log2(n). This is the reason B-trees, not binary trees, dominate on-disk and in-memory index structures: the win is not fewer comparisons but fewer dependent memory accesses. The arithmetic is unambiguous: a 16-element fanout within a 64-byte line gives four dependent loads for a million entries instead of twenty.

The cost of widening is that each step now transfers a larger node. For a 512-byte node the transfer is eight cache lines, which is wasteful if only one key compares near the target. Real designs split the difference by choosing the node size that fits a small number of lines and by storing keys and child pointers in separate arrays within the node, so that the key comparisons touch only the key part. That is the layout trade described in Bytes Fetched per Field applied inside a single node.

Breaking the dependence with batching and lookahead

Where the structure cannot be widened, the dependence can sometimes be removed by restructuring the loop so that several independent chains are walked in parallel. A hash table traversal that processes a batch of keys becomes: compute all the bucket addresses, load all of them, then resolve collisions in parallel. The first load in each chain is independent, so the batch yields as many outstanding misses as its size.

/* Resolve four independent chains at once. The four head loads are
 * independent, so the hardware issues them together; the loop below then
 * advances all four in lock-step, keeping at most four dependent loads
 * outstanding instead of one. */
struct node { struct node *next; int key; };

void walk_four(struct node **heads, int *out, size_t n)
{
    for (size_t i = 0; i + 3 < n; i += 4) {
        struct node *a = heads[i], *b = heads[i + 1];
        struct node *c = heads[i + 2], *d = heads[i + 3];
        int sum = 0;
        while (a || b || c || d) {
            if (a) { sum += a->key; a = a->next; }
            if (b) { sum += b->key; b = b->next; }
            if (c) { sum += c->key; c = c->next; }
            if (d) { sum += d->key; d = d->next; }
        }
        out[i / 4] = sum;
    }
}

The loop above keeps four chains in flight, and the compiler or core can overlap their loads because the four addresses are independent of each other. Throughput improves up to the point where the number of outstanding misses reaches the hardware limit; beyond that the limit binds and adding more chains gains nothing. The useful batch size is therefore set by the miss capacity of the core, which is on the order of ten to twenty outstanding requests for current designs, not by an arbitrary constant.

Batching has a cost: the output is scattered, the per-chain control flow is more complex, and the code that consumes the results must accept a batch. Where the walk is one stage of a larger multi-stage computation, the batch boundary often proves the harder problem to fit.

Pointer chasing as a deliberate test

Because a random dependent-load chain has no prefetching, no reuse, and perfect serialisation, it makes a good instrument. The permutation-chase loop described in Working Set Size and the Miss-Rate Cliff measures the latency of each cache level directly, since cycles per step equals the level’s access latency. The same shape with a known footprint is a calibration for any latency model.

The measurement also exposes the difference between the levels more clearly than any bandwidth test. The gap between an L1 hit and a DRAM access that in principle is a factor of twenty or more shows up in the chase loop as exactly that factor, whereas in a bandwidth-bound loop the gap narrows because the hierarchy’s bandwidth ratios are less extreme than its latency ratios.

Where the dependence is worth paying

Not every dependent chain is a performance defect. A chain of four or five nodes that all sit in L1 costs a few tens of cycles in total, which is cheaper than the indirection needed to remove it. The break-even point is a function of how much useful work each node contributes to the total run: a parser walking a document tree that visits each node once for a handful of operations is dominated by the parse, not by the walk.

The cases that matter are those where the chain is both long and repeated. A symbol table lookup on every token, a router’s forwarding table lookup per packet, a filesystem’s directory walk per path component: here the chain is traversed millions of times and its serialisation is multiplied. Those are the places where flattening, widening, or batching produces a step change, and the arithmetic above says how much is available before any code is written.