Memory is a hierarchy
A CPU core reads from fast small caches before slow main memory. A cache miss can cost a hundred times a hit. How you lay out data decides how often you hit.
Locality
Two kinds of locality drive cache behavior.
- Spatial locality means data used together sits close in memory, so one cache line load serves several accesses.
- Temporal locality means data reused soon stays warm in cache.
Layout choices
- Contiguous arrays beat linked structures because they prefetch and stream well.
- Struct of arrays packs the field you scan tightly, so a scan touches only useful bytes.
- Hot and cold splitting keeps rarely used fields out of the hot line.
Access patterns
- Sequential scans are cache friendly because hardware prefetches ahead.
- Random pointer chasing defeats prefetch and stalls on misses.
Tradeoff
Cache friendly layouts can hurt readability and flexibility, so apply them on measured hot paths, not everywhere.
Key idea
Lay out data for spatial and temporal locality so hot scans stream from cache, applying it where profiling shows real cache misses.