Data Access Patterns That Makes Your CPU Angry
The article explores how different data access patterns impact CPU performance, demonstrating that non-sequential memory access (like random or strided access) can drastically slow down programs compared to sequential access, due to CPU caching behavior and prefetching mechanisms.
Background
- The post explores how seemingly innocent data access patterns (like linked-list traversal or pointer chasing) can be 10-100× slower than linear array access, because modern CPUs rely on prefetching and cache locality to stay fast.
- It walks through concrete C++ benchmarks showing that "random" access patterns defeat the CPU's branch predictor and prefetcher, causing pipeline stalls and cache misses — the hardware equivalent of "angry."
- The key insight: the slowest code isn't always complex algorithms; often it's the simple act of jumping to unpredictable memory addresses, which starves the CPU of data.
- Assumes familiarity with CPU caches (L1/L2/L3), cache lines, and the idea that main memory is ~100× slower than a register — core concepts in systems programming and performance engineering.
- Relevant for engineers writing performance-sensitive code (databases, game engines, kernels); the takeaway is to design data structures for sequential, predictable access patterns rather than pointer-heavy linked structures.