Workspace

Caches, locality and false sharing

3 day streakD

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.

DepthLesson 5 of 618 min

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.

Figure 5.1

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
Line in cache (holds 2)HitMiss
64 values span 8 cache lines, and this tiny cache holds 2 lines. A sequential scan misses once per line. A shuffled linked list visits the same values in random order and misses on most steps. Both are O(n).

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.

Figure 5.2

Two counters, one cache line

Same line: ping-pong

Core 0 · thread Awrites hits
Core 1 · thread Bwrites misses

Every write forces the other core to fetch the 64-byte line again, roughly 100 ns each time.

Padded: each line has one owner

Core 0 · thread Awrites hits
Core 1 · thread Bwrites misses

Each counter sits alone in its line, so both cores keep their copy and write at L1 speed.

Thread A writes 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.
false_sharing.cC
// 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

Columnar analytics

DuckDB and ClickHouse scan contiguous column arrays, using every byte of every line, which is a large part of why they are fast.

Hash tables

Open-addressing tables such as Swiss tables keep probes within a cache line. Chained tables follow pointers and miss more.

Per-core counters

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.

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap