Big-O Is Not Enough: CPU Caches, Memory Locality & Real-World Latency
Why asymptotic notation ignores hardware realities: CPU cache line misses, branch prediction, allocation churn, and hidden architectural constants.
Big-O Is Not Enough: CPU Caches, Memory Locality & Real-World Latency
1. The Asymptotic Illusion
In computer science curricula, algorithmic efficiency is taught via Big-O notation ($O(1)$, $O(log n)$, $O(n)$, $O(n^2)$). However, in high-performance production systems, theoretical time complexity often misleads developers because Big-O explicitly ignores constant factors ($c$) and hardware architecture realities.
Execution Time = (Number of Operations * Big-O) * (Cost per Operation)
If Operation A is $O(n)$ with sequential memory reads (1 ns each), and Operation B is $O(log n)$ with random pointer indirections causing CPU cache misses (100 ns each), Operation A can be 10x faster for $n < 100,000$.
2. The Hardware Hierarchy: Latency Numbers Every Engineer Should Know
+-----------------------+---------------+
| Memory Hierarchy Level| Access Latency|
+-----------------------+---------------+
| CPU L1 Cache Reference| ~ 0.5 - 1 ns |
| CPU L2 Cache Reference| ~ 3 - 4 ns |
| CPU L3 Cache Reference| ~ 10 - 20 ns |
| Main Memory (DRAM) | ~ 60 - 100 ns |
| SSD Random Read | ~ 16,000 ns |
| Network Roundtrip DC | ~ 500,000 ns |
+-----------------------+---------------+
Reading data from main RAM is 100x slower than reading from L1 cache.
[ CPU Core ] <---> [ L1 Cache ] <---> [ L2 Cache ] <---> [ L3 Cache ] <---> [ DRAM ]
(Fastest, small) (Slow, large)
3. Contiguous Arrays vs Linked Lists / Pointer Graphs
- Flat Typed Arrays: Elements are stored contiguously in memory. When the CPU loads element 0, the hardware prefetcher loads the entire 64-byte Cache Line, making subsequent elements already resident in L1 cache (Spatial Locality).
- Linked Lists / Node Trees: Every node is allocated at a random address on the heap. Traversing the list triggers a CPU Cache Miss on almost every dereference, stalling the CPU execution pipeline.
4. Practical Engineering Takeaways
- Profile before picking complex trees over contiguous arrays.
- Beware of excessive garbage collection allocations in hot loops.
- Design data layouts for sequential cache-friendly access.
