CPU Cache Optimization
CPU Cache Optimization — writing code that exploits the CPU's memory hierarchy (L1→L2→L3→DRAM) to minimize expensive cache misses, potentially achieving 10-100x performance improvement.
Memory Hierarchy Latency
| Level | Size | Latency | Bandwidth |
|---|---|---|---|
| L1 Cache | 32-64 KB | ~1 ns (4 cycles) | ~1 TB/s |
| L2 Cache | 256 KB-1 MB | ~3 ns (12 cycles) | ~500 GB/s |
| L3 Cache | 8-64 MB | ~10 ns (40 cycles) | ~200 GB/s |
| DRAM | 16-256 GB | ~70 ns (280 cycles) | ~50 GB/s |
Key Optimization Strategies
1. Spatial Locality: Access data sequentially (cache lines are 64 bytes)
- Row-major array: Iterate rows then columns (C/C++ default)
- Column-major: Iterate columns then rows (Fortran default)
- Wrong order → cache miss every element instead of every 16th element (64B / 4B float)
2. Temporal Locality: Reuse data while it's still in cache
- Loop tiling/blocking: Process small blocks that fit in L1/L2 before moving on
- Hot/cold splitting: Separate frequently-accessed fields from rarely-accessed ones
3. Avoid False Sharing: Different threads writing to same cache line → invalidation ping-pong
- Pad per-thread data to cache line boundaries (64 bytes)
4. Prefetching: CPU hardware prefetcher detects sequential/strided patterns. Use `__builtin_prefetch()` for irregular patterns
Cache optimization is the #1 performance technique for CPU-bound code — an algorithm that's cache-friendly can outperform an otherwise "faster" algorithm with poor locality.