Caches, locality and false sharing
Memory moves in 64-byte lines. Code that uses every byte of each line runs fast; code that jumps around pays the full trip to DRAM again and again.
The CPU never reads a single byte from DRAM. It reads a cache line, usually 64 bytes, and keeps it in a small, fast cache. Modern cores have three levels: L1 of tens of KB per core at about 1 ns, L2 around 1 MB, and L3 shared across cores with tens of MB. A miss in all three costs about 100 ns.
Two kinds of locality decide your hit rate. Spatial locality: if you touched byte n, you will probably touch n+1 soon, so the rest of the line is already loaded. Temporal locality: if you touched it recently, you will probably touch it again. Hardware prefetchers watch for sequential patterns and fetch the next lines before you ask.
Sum an array versus walk a shuffled list
- Values read
- 0 / 64
- Cache hits
- 0
- Misses to DRAM
- 0
- Last access
- —
- Estimated time
- 0 ns
The same effect shows up at every size. When the working set fits in L1, L2 or L3, time per element stays flat; when it spills to the next level, time steps up. The module lab plots exactly this staircase.
The TLB and branch prediction
Addresses are virtual. Translating one to a physical page goes through the TLB, a small cache of page-table entries. Random access across a large heap misses the TLB as well as the data cache, and each TLB miss walks the page tables. Huge pages of 2 MB reduce this. Separately, CPUs guess which way a branch will go. A wrong guess flushes the pipeline and costs 10 to 20 cycles, so unpredictable branches in hot loops are slow.
False sharing
Caches keep lines coherent across cores. When one core writes to a line, every other core's copy is invalidated. If two threads update different variables that happen to sit in the same line, they keep stealing the line from each other. Neither thread shares data, yet they run as if they did.
Two counters, one cache line
Same line: ping-pong
hitsmissesEvery write forces the other core to fetch the 64-byte line again, roughly 100 ns each time.
Padded: each line has one owner
hitsmissesEach counter sits alone in its line, so both cores keep their copy and write at L1 speed.
hits, thread B writes misses. Because both live in one 64-byte line, every write forces the other core to reload it. Padding each counter onto its own line removes the ping-pong.// Before: both counters share one 64-byte line
struct Stats { _Atomic long hits; _Atomic long misses; };
// After: each counter owns a full line
struct PaddedStats {
_Alignas(64) _Atomic long hits;
_Alignas(64) _Atomic long misses;
};Find it with perf c2c on Linux, which reports cache lines contended across cores.
Where you will meet it
DuckDB and ClickHouse scan contiguous column arrays, using every byte of every line, which is a large part of why they are fast.
Open-addressing tables such as Swiss tables keep probes within a cache line. Chained tables follow pointers and miss more.
Metrics libraries keep a padded counter per thread or core and sum them on read, avoiding false sharing on hot counters.
Check yourself
Answer out loud before you open each one.
Why can two O(n) loops differ by 10x?
One reads memory sequentially and gets cache and prefetch hits. The other chases pointers to random addresses and waits about 100 ns on most steps.
What is false sharing, and how would you find it?
Two threads write different variables on one cache line, so the line bounces between cores. perf c2c or a cache-miss counter on the hot loop reveals it.
Why do huge pages help random access over a big heap?
Each TLB entry covers 2 MB instead of 4 KB, so far fewer translations miss.
Try it
Sum a Float64Array of n values, then walk the same values through a shuffled next index array. Time both for n from 1,000 to 50,000,000 and plot nanoseconds per element. On Linux, confirm the cause with perf stat -e cache-misses.