The idea: caches copy lines, and copies must agree
Each core has its own L1 cache. When a core reads memory it does not fetch one variable but a whole cache line of 64 bytes, and keeps a copy of it. If two cores hold copies of the same line and one of them writes, the other copy is wrong. Cache coherence is the hardware protocol that stops this: before a core may write a line, every other copy of that line is thrown away (invalidated). The most common protocol is MESI.
Two threads that each update their own counter should not slow each other down. But if both counters are in one line, the hardware cannot tell them apart: every store by one core invalidates the other core's copy, and the line ping-pongs between the caches. That is false sharing: nothing is shared in the program, but the line is.
The four MESI states
Every line in every L1 is in one of four states. The page colours them the same way on the canvas.
| State | Meaning | Load | Store |
|---|---|---|---|
| M modified | the only copy, newer than L3 (dirty) | hit | hit |
| E exclusive | the only copy, same as L3 (clean) | hit | hit, silent E → M |
| S shared | clean, other caches may have it too | hit | BusUpgr first: invalidate the others |
| I invalid | no usable copy (the old bytes may still be there) | miss: BusRd | miss: BusRdX (RFO) |
The rule behind the table: a line may be written only in one cache at a time (M or E), and then no other cache holds it at all. Many caches may read a line at once, in S.
Bus messages and snooping
The caches talk over a shared bus (on a real chip: a ring or mesh, often with a directory in L3). Every cache snoops every message and checks it against its own lines.
- BusRd: "I want to read this line." A cache that has it in E or S keeps it as S. A cache that has it in M must flush it: write it back to L3 and hand it over, then keep it as S.
- BusRdX, also called RFO (read for ownership): "I want to write this line and have no copy." Every other cache drops its copy (→ I), an M owner flushes it first.
- BusUpgr: "I have this line in S and want to write." The data is already there, so only the invalidation is sent.
Demo 1: read → E, write → M: the first load finds no other copy, so the line is E, and the stores after it need no bus message at all. Demo 2: shared copies, BusUpgr, flush: both cores read a (S, S); core 1's store sends BusUpgr and core 0's copy becomes I; core 0's next load sends BusRd and core 1 flushes its dirty line, so both end in S with a = 1 and L3 up to date. 4 bus messages, 1 invalidation, 1 writeback.
False sharing, step by step
Take struct { long a; long b; }. a is at offset 0 and b at offset 8, so both live in line 0x1000. Thread T0 on core 0 runs a++ in a loop, thread T1 on core 1 runs b++.
- Core 0 stores to
a: no copy, so BusRdX. L3 sends the line; core 0 has it in M. - Core 1 stores to
b: no valid copy, so BusRdX. Core 0 snoops it, flushes the line (writeback) and drops it: invalidation. Core 1 has the line in M. - Core 0 stores to
aagain: its copy is I, so BusRdX again, and core 1 flushes and invalidates. And so on.
Every store is a miss that waits for the other core, roughly 50 cycles here (40 to well over 100 on real CPUs, more across sockets) instead of 4 for an L1 hit. Demo 3: false sharing runs 4 rounds: 8 stores, 8 BusRdX, 7 invalidations, 7 writebacks, 0 hits, about 400 cycles. Over a loop of millions of increments, two threads are often slower than one.
The fix: padding
Put each counter on a line of its own. Demo 4: padded runs the same loop with a at 0x1000 and b at 0x1040: one BusRdX per core, then each line stays in M in its own L1, so the other 6 stores are hits. 2 bus messages, 0 invalidations, about 124 cycles.
| Language | How to give a field its own line |
|---|---|
| C / C++ | alignas(64) long a;, or alignas(std::hardware_destructive_interference_size) |
| Java | @jdk.internal.vm.annotation.Contended (with -XX:-RestrictContended outside the JDK), or manual padding fields |
| Go, Rust | a padding array, e.g. _ [56]byte, or crossbeam::CachePadded |
The JDK uses this itself: LongAdder keeps an array of padded cells so threads add to different lines and only sum() reads them all; ConcurrentHashMap counts its size the same way, and Thread pads its random-number fields. The cost of padding is memory: 64 bytes per counter instead of 8. Many Intel chips also fetch the neighbouring line in pairs (the adjacent-line prefetcher), which is why some libraries pad to 128 bytes.
Reads are fine, true sharing is not
Only writes cause the ping-pong. Demo 5: reads only: core 0 reads a and core 1 reads b in the same line; both copies settle in S and every later load is a hit, 0 invalidations. Demo 6: true sharing: with padding, both cores now write a itself. The line ping-pongs exactly as in Demo 3 (4 BusRdX, 3 invalidations), and padding cannot help, because the data really is shared. The fix there is to share less: per-thread counters added up at the end, batching, or an atomic counter used less often (see Compare-and-Swap and Spinlock, whose lock word bounces the same way).
Finding it
False sharing does not show up in the code, only in the hardware counters. On Linux, perf c2c record and perf c2c report list the cache lines with the most HITM events (a load that hit a line Modified in another core's cache) and the code and offsets that touch them. Two hot fields at offsets 0 and 8 of one line, written from different threads, is the signature.
See also How a CPU Cache Finds, Misses and Replaces (tags, sets and lines inside one cache), NUMA (where coherence traffic crosses sockets) and ConcurrentHashMap.
See Java Memory Model for how store buffers and the JIT make writes visible late or out of order, and how volatile fixes it.
What the page leaves out
Real CPUs use variants of MESI: Intel MESIF adds F (forward, the one shared copy that answers), AMD MOESI adds O (owned, dirty but shared, so a flush is not needed). Many cores do not snoop a bus but ask a directory or snoop filter in L3, which knows who holds each line. The page also leaves out L2, evictions and write-back on eviction, store buffers and memory ordering (a store can retire before its RFO completes), the adjacent-line prefetcher, more than two cores and real cycle counts. The 4 and 50 cycles are rough round numbers.