Data Access Patterns That Makes Your CPU Really Angry
Non-contiguous data access patterns like linked list traversal cause severe CPU cache misses and performance slowdown, as the CPU's prefetcher is optimized for sequential memory access in arrays.
Background
- The CPU is not a simple "fetch-execute" machine — it aggressively predicts branches, caches data, and pipelines instructions to keep all its execution units busy. When those predictions fail or data isn't in cache, the CPU stalls, wasting dozens of cycles doing nothing while it waits.
- "Denormalized" floating-point numbers are tiny values (e.g., 1e-310) that the CPU can represent but must handle with special slow microcode, often 10–100× slower than normal floats. Whether a value is denormal depends on its bits, not its algorithm.
- "Pointer chasing" means following linked-list-style references (e.g., a → b → c) where each address is only known after the previous load finishes. This defeats prefetching and creates a chain of unavoidable cache misses.
- The article builds a program that deliberately combines all three worst-case behaviors — branch mispredictions, denormals, and pointer chasing — to measure the slowest possible addition in x86 assembly, showing how hardware quirks can turn a trivial operation into a disaster.