Prefetching: The Hardware Guesses What You Will Read Next

The simplest useful heuristic is next-line: on a miss for line L, also fetch L+1. That alone covers a large fraction of real access patterns, because sequential traversal is everywhere. More capable prefetchers detect a constant stride — noticing that accesses are separated by a fixed distance and continuing the arithmetic progression — and track several such streams at once.

The crucial property is that prefetching hides latency without reducing it. The miss still happens and the line still travels from wherever it lives; what changes is that it happens concurrently with useful work instead of blocking it. That is why a sequential loop can approach the machine's bandwidth limit rather than its latency limit, and why the two limits are worth distinguishing (Latency and Bandwidth Are Different Resources).

It follows that prefetching only works when the address is knowable in advance. A stride is computable from history. A pointer is not: you must load the current node before you can know the address of the next one, and no amount of pattern detection can shortcut a dependency. That single asymmetry drives most of the practical advice in this module.

Both loops below visit n elements and do one addition each. Complexity analysis calls them identical and is not wrong about operation counts. The hardware treats them completely differently, because one exposes its future addresses and the other conceals them.

In the array version the addresses form an arithmetic progression that the prefetcher locks onto immediately. Several lines are in flight at once, and the loop runs at roughly the rate memory can stream. In the list version each next must arrive before the following address is even known, so misses are strictly serialised: the machine issues one, waits the full latency, then issues the next. There is no overlap to exploit (Misses That Overlap Are Nearly Free).

This is the concrete answer to the interview question about arrays versus linked lists, and it is worth stating precisely: the array wins not because it has fewer operations but because it has fewer *stalls*, and it has fewer stalls because its addresses are computable in advance. Change the linked list so nodes are allocated contiguously in traversal order and much of the gap closes — which is itself evidence that layout, not the data structure's abstract shape, is doing the work.

Prefetchers are finite and occasionally counter-productive. They track a bounded number of streams, so a loop walking many arrays at once eventually exceeds the tracker and the extra streams get no benefit. They generally will not follow a stream across a page boundary without a valid translation, which is one reason large pages sometimes help streaming workloads (Huge Pages: More Coverage per Entry, and What It Costs).

They can also be actively harmful. A pattern that looks like a stride but is not causes the prefetcher to fetch lines nobody wants, and those lines occupy the cache and evict data that was useful — turning a mild miss problem into a worse one. On a workload already saturating memory bandwidth, speculative prefetches compete with demand loads for the resource that is already the constraint (When the Memory Bus Is the Bottleneck).

Software prefetch instructions exist on many ISAs and look like an obvious lever, but they are hard to use well: issue too early and the line is evicted before use, too late and you have not hidden anything, and the right distance depends on the machine and on how fast the loop consumes data. They also compete with the hardware prefetcher rather than cooperating. Measure before and after, and expect a fair number of attempts to make things worse.