Prefetching and Access Patterns

Fetching data from main memory (RAM) costs a CPU roughly 100-300 cycles — hundreds of times slower than an operation that hits data already sitting in cache. If a CPU only started fetching memory the instant an instruction asked for it, every cache miss would stall the pipeline completely. Instead, CPUs run a hardware prefetcher: a unit that watches recent memory accesses, detects a pattern, and starts fetching addresses it predicts the program will need before any instruction has actually requested them.

The prefetcher is very good at one specific pattern: sequential or fixed-stride access, like walking through an array one element (or every Nth element) at a time. It is essentially useless for pointer chasing — following a linked list or tree where each next address depends on the value stored at the current one, discovered only after the current fetch completes. There, the prefetcher has nothing to predict from, and every step pays the full memory-latency cost with no overlap.

Sequential versus pointer-chasing access

Worked example

Summing 10 million doubles stored in a std::vector (contiguous array) takes roughly 6 milliseconds on typical server hardware — the prefetcher recognizes the stride-8-bytes pattern almost immediately and keeps a steady stream of cache lines arriving just before the summation loop needs them. Summing the same 10 million values stored as a std::list (each value in its own heap-allocated node, linked by pointers scattered wherever the allocator happened to place them) takes roughly 140 milliseconds for the identical arithmetic — more than 20x slower, entirely because each node's address is unpredictable until the previous node's pointer is actually read, so every single access pays close to the full memory-latency cost with no overlap.

What this means in practice

This is the single biggest reason "use std::vector, avoid linked structures" is such persistent advice in performance-sensitive C++: it's not really about the container's API, it's about whether the CPU can predict where you're going next. Order books, price series, and any hot analytical loop benefit enormously from contiguous, sequentially-scanned storage; tree and graph structures pay a pointer-chasing tax that's often invisible in complexity analysis but very visible in wall-clock time.