The Cache Prefetcher's Stride Detector: How CPUs Learn That You're Walking Through an Array

2026-06-16

Sequential prefetching catches the easy case: address N, then N+64, then N+128. But real code rarely walks bytes one at a time. You iterate a struct array where each element is 192 bytes, or you stride through a column of a row-major matrix with a 4096-byte step. The CPU's stride detector exists to catch these patterns — anything that looks like address += constant per load.

The hardware is a small table — Intel calls it the IP-based stride prefetcher, indexed by the load instruction's PC (the IP). Each entry stores: the last address seen at this IP, the last stride observed, and a confidence counter. When a load fires:

The IP-indexing is the clever part. Two interleaved loops with different strides don't confuse each other — they hit different table entries. The PC is the natural ID for "what pattern is this load following."

Real-world example: walking a linked list defeats the stride detector completely. Each node = node->next dereference produces a non-constant delta — wherever the allocator put the next node. You see this as cache misses that the prefetcher never anticipates, even on a hot linked list traversal. Conversely, a packed array of 192-byte structs hits the detector perfectly: stride locks to 192, and by the time you're three iterations in, the next 8–16 lines are already on their way.

Rule of thumb: the stride detector typically tracks ~16–64 IPs and needs 2–3 consistent strides to lock on. So the first 2–3 iterations of any loop pay full miss latency, then prefetch hides the rest. If your loop only runs 4 times, you barely benefit. This is why microbenchmarks of "hot" tight loops dramatically overstate real-world prefetcher gains — short loops train, finish, and never amortize.

The other failure mode: stride > page size. Most stride prefetchers won't cross a 4KB page boundary speculatively, because that would require a TLB walk for an address that may not even be mapped. So a 4096-byte column stride through a matrix gets one prefetch per page at best — often none. This is why blocked/tiled matrix code beats naive column traversal by an order of magnitude.

Key Takeaway: The stride detector turns predictable loops into free bandwidth, but it needs 2–3 iterations to lock on and won't cross page boundaries — which is exactly why pointer chasing and large-stride column walks remain pathologically slow.

All newsletters