Cache Coherence

Our server has 32 cores taking HTTP requests. Each has a private L1 of about 32 KB and a private L2 of about 1 MB; only the L3 and DRAM are shared.

A load does not fetch a byte. It fetches the whole 64-byte line that byte sits in — drag the address and watch the byte we asked for arrive inside the sixty-three that came with it:

Notice that the byte we name never changes the answer: ask for byte 8 or byte 63 and the same sixty-four arrive. The line, not the byte, is the unit every rule below is written in — and it is why section 05 can charge two threads that share no variable at all.

Press play and watch the one copy in DRAM turn into four, as each core in turn reads x and fills a private line of its own:

Notice that nothing has been written and nothing has gone wrong, and the machine is already holding four versions of one variable — three of them in caches no other core can look into. Coherence is the set of rules that keeps those four in agreement, and the rest of this page is what those rules cost.

Take the rules away and the failure is immediate. Step core 0 through a read and a write while core 1 keeps its own copy, then switch the protocol on and watch the invalidation arrive:

With no protocol, core 1 reads 5 — one write behind, with nothing anywhere to tell it so. With MESI, core 0's write first takes the line away from core 1, so core 1's next read misses and fetches 6. That is the whole contract: a read that returns a value that is no longer true is not something software has to defend against.

Coherence is stated per address, and it says two things: every write to x eventually becomes visible everywhere, and all cores observe writes to x in the same order. Drag core 0's four writes through core 1's and watch that one order reshuffle:

Wherever you leave the boundary, there is exactly one row along the bottom, and every core reads that same row. What coherence forbids is core 1 seeing a3 before b1 while core 2 sees b1 first. The order is not yours to pick; it is only promised to be one order.

That promise covers one address. It says nothing whatever about two. Raise the slider to let the flag store overtake the data store — try two steps early — and read what the consumer prints:

Watch the consumer print 0 while every individual address behaves perfectly: data holds 42, flag holds true, and no core ever read a stale value of either. This is the distinction the page turns on. Coherence is per address and automatic; consistency is the order in which writes to different addresses become visible, and it is what volatile, std::atomic orderings and mfence actually configure. Section 03 is where we buy it.

Every line in every private cache carries two bits of state. The protocol is the rule that says how those bits move when a core reads, writes or evicts — and how they move when another core does.

Walk the slider through the four and read what each one licenses the core to do next — M and E are the two that permit a silent write, I is the one that has nothing:

Notice what M and E share and S does not: a core may write without telling anybody only when no other core has a copy. That is the invariant, and it is worth writing as an assertion — at every instant, a line is held writable by at most one core, and if it is, no other core holds it at all. Single writer, or many readers, never both.

Press play and follow one line through every transition three cores can cause. The message each step puts on the interconnect is drawn on the wire beneath them:

Seven of the nine states were reached by a bus message. The one write that was free is step 3, where the line was already exclusive — E had already proved nobody else had it, so upgrading to M needed no permission from anyone. E exists for exactly that: to make the second access to a private line cost nothing.

A write to a shared line is not free, and the price is the number of copies it has to destroy first. Raise the sharers — try eight — and count the copies that go away:

At eight sharers one write costs seven invalidations and seven acknowledgements before the store may be applied. This is why a read-mostly variable that is written once a second is fine and one that is written a million times a second is a scalability wall: the cost is per write and it grows with the audience.

How those messages are delivered is what separates a laptop from a server. Drag the core count out to 32 and compare a snoop broadcast with a directory:

Watch the directory line stay flat while the broadcast climbs. A snoop asks every core and every core answers — 2(n−1) messages whether they hold the line or not — while a directory knows who is actually sharing and pays 2 + 2s. At two sharers the directory is strictly cheaper from five cores up, which is why no 32-core socket broadcasts.

One thing the four states cannot express is shared and dirty. So the moment a line core 0 has written picks up a second reader, MESI has to flush it. Switch the protocol and step through the write-back, then watch who answers the reader after that:

Watch DRAM under plain MESI: the dirty line goes back to memory and both caches end up holding it clean — and with nobody designated to forward a clean line, core 1's read is served by DRAM as well. Intel's MESIF elects one clean sharer — F, forward — as the responder, so that second read never leaves the caches. AMD's MOESI goes further: an Owner keeps the line dirty and answers from it, and the write-back never happens at all. Same four states underneath, two different answers to who pays for the transfer.

Between a core and its L1 sits a store buffer — 56 entries on Skylake, 72 on Ice Lake. A store retires into it and the core moves on; the line is acquired and the write applied later. Store-to-load forwarding means the writing core always reads its own newest value.

Raise the stores still waiting in the buffer — push it to all 56 — and watch the two readings come apart:

Notice this core reads 100 while every other core still reads 44. Nothing here is incoherent: as far as the cache hierarchy is concerned those stores have not happened yet. They will, in order, about 15.6 ns from now — but the value everyone agrees on lags the value the writer sees.

That lag is observable from the outside. Both cores store, then load; switch from one store at a time to real buffers and scrub to the end:

With the stores draining one at a time, one of them lands before either load runs, so r1 = r2 = 0 is unreachable — three outcomes. Give each core a buffer and both loads can execute while both stores are still in flight: four. That is the single reordering x86's TSO permits, and it is the entire reason mfence exists.

The barrier that takes the fourth outcome away is not one instruction — it is one instruction plus everything the core was allowed to defer. The fence is already in — refill the buffer under it, then take it away:

The instruction itself is about 8.3 ns. Draining a full buffer adds another 15.6, for 23.9 ns — roughly 86 cycles for a barrier that appears in the source as one line. Put one in a loop that runs a million times a second and you have spent 2.4% of a core on ordering nobody asked for by name.

x86 gives you one reordering to think about; other architectures give you four. Switch the architecture and step through the pairs — the ones a program can observe out of order against the ones held in program order for free:

Because x86-64 permits only store→load, four of the five pairs are free, and code that is "correct" there can be wrong on ARM64 — where every pair but IRIW is reorderable and acquire/release is spelled into the instructions themselves, ldar and stlr. Porting a lock-free structure from x86 to ARM64 is not a recompile. It is a re-derivation.

When a core writes a line another core holds, the line has to travel: an invalidation out, an acknowledgement back, and the data itself. Measured with a ping-pong of a single line, that round trip is about 30 ns at best and 70 ns typically, inside one socket.

Walk the slider down the ladder and watch the cross-socket bounce run off the end of everything that stays on this core:

A plain increment in L1 is 0.28 ns — one cycle at 3.6 GHz, which is the clock every nanosecond on this page is quoted at. An uncontended atomic on a line this core already owns is 5.6 ns — twenty cycles, and worth memorising, because that is the price of std::atomic with no contention at all. A typical bounce is 70 ns: 252 times the plain increment.

That number is a ceiling, not a tax. Drag the handle along the bounce curve and read the writes per second one contended line can sustain:

At 70 ns a bounce, one line absorbs 14.3 million writes a second — and that figure does not move when you add cores. Thirty-two threads hammering one counter do not get 32 times the throughput. They get the same 14.3 M, split thirty-two ways.

Which is exactly what the flat line below is. Raise the threads to sixteen and watch one shared counter and one counter per thread come apart:

Notice the shared line does not merely stop scaling — it drops. One thread gets 180 M increments a second, because the line never leaves its cache. Two threads get 14.3 M between them, and sixteen get the same 14.3 M. The per-thread version reaches 2.9 G, and the gap is a factor of 202.

"Make it atomic" does not fix this, and on some architectures it makes it worse. Switch the instruction and raise the contenders:

x86's lock cmpxchg holds the line for the whole read-modify-write, so one attempt always succeeds. ARM's ldxr/stxr gives the line up between the two halves, so a contender can steal it and the store-exclusive fails: with eight threads racing, one wins and seven retry — 560 ns of work for one increment. Atomics do not remove contention; they only keep the result correct while you pay for it.

Coherence works on lines, not on variables. Two counters that no line of source code ever shares will still bounce against each other if they land in the same 64 bytes — and the program stays correct throughout, which is why nobody finds it by reading the code.

Drag the second counter along the allocation and watch the moment it crosses out of the first one's line:

At byte 8 the two counters share line 0, and the pair runs at 14.3 M increments a second — the bounce rate, exactly as if they were one variable. At byte 64 they sit on separate lines and the pair runs at 360 M. Nothing in the source changed between those two states.

Padding is how you buy the second state, and the amount is not a matter of taste. Take the padding up from zero and find the edge — 56 bytes is where it is:

Because the counter is 8 bytes wide, 56 is the first amount of padding that puts the second one on a line of its own. Forty-eight buys nothing at all. This is a cliff, not a slope: there is no partial credit for being nearly on another line — two counters 56 bytes apart perform exactly like two that are 8 apart, because both are still inside line 0 and both bounce.

The gap does not close as the struct grows. Add threads to one unpadded struct and watch the shared line refuse to move:

Sixteen threads on one line still get 14.3 M between them; sixteen threads on sixteen lines get 2.9 G. The padded version costs 1 KB of memory — sixteen lines instead of two — and buys a factor of 202. There is no other change in the program worth that trade.

The most common way to buy this by accident is an array. Set the element size and count how many elements start inside line 0:

At 16 bytes an element, four of them share line 0. A vector<Worker> in which every worker increments only its own field is four threads on one line, with no shared variable anywhere in the source — and it fails silently: the answers are right, and the four of them together return 14.3 M increments a second where four separate lines would return 720 M — a fiftieth of what the hardware can do.

"Silently" is worth being precise about, because it is a claim about tools. Flip the layout and watch the cores kept busy refuse to move while the HITM loads appear and disappear:

The top row is why a CPU-time profile is no help: the threads are runnable, on-core and retiring instructions either way — they are just retiring them behind a line that is somewhere else. The counter that does name it is HITM, a load served from a line another core held modified. perf c2c on Linux counts it and prints the offending cache line with the struct offsets inside it; VTune's memory-access analysis reports the same event. Sizing the element to 64 bytes fixes the bug and wastes memory — section 06 is that trade, done deliberately.

Sharding is the general form, and it is what Java's LongAdder and Linux's per-CPU counters both are. Sixteen threads, one counter each on its own line, and a periodic fold into the number anyone actually reads. Two questions decide whether it works: how many counters, and how often to fold.

Raise the counters and watch the busiest one empty out — at sixteen every thread has a line to itself:

One counter is 14.3 M. Eight counters is 114 M — better, but every shard still has two writers, so every shard still bounces. Only at sixteen, where nobody shares, does the curve reach 2.9 G. The gain is not gradual: it arrives when the last shared shard goes away.

The fold has a ceiling of its own, and it is the same ceiling. Move the interval and compare what the reduce asks of the shared total with what one line can give — every thousand is the first one that fits:

Because the published total is one line, it absorbs 14.3 M operations a second and no more. Folding on every increment asks 2.9 G of it, and the shards were pointless. Folding every thousand asks 2.9 M, which fits — and buys a total that can be 16,000 counts behind. For metrics that is free; for a quota check it is a bug.

One last thing can undo all of it without touching a line of your code. Drag the second thread across the socket boundary:

As soon as the two threads sit on different sockets the bounce goes from 70 ns to 250, and the ceiling falls by 3.6× — with no change in the program to explain it. This is why a benchmark that scales beautifully on one socket collapses on two, and why thread pinning and NUMA-aware allocation belong in the same conversation as padding: the line you carefully gave to one thread is only cheap while that thread stays where you put it.

The bug is invisible in the source, so a review of it has to be about layout rather than about logic. Four shapes cover nearly all of it in practice, and the first two are the ones that reach production.

Step through the four and read which of them put two threads' writes inside one line — the tape is the same 128 bytes throughout:

Two atomic counters side by side, and a ring buffer's head and tail, are both textbook false sharing: different threads, one line. The flag beside the data it guards is safe, because one thread writes both. The padded pair is what the fix looks like, and it is the only one of the four that costs memory.

In C++ that fix is one attribute, and the bug is one attribute missing:

struct Counters {          // ✗ one line
  std::atomic<uint64_t> a; //   bytes 0..7
  std::atomic<uint64_t> b; //   bytes 8..15
};

struct alignas(64) Padded {  // ✓ one each
  std::atomic<uint64_t> v;
};

The compiler keeps that promise about the type: sizeof becomes 64 and the stride is a whole line. Hand-rolled padding promises nothing. Leave the padding at 48 bytes and drag the base address the allocator handed back —16 is enough:

Watch the same struct change its mind. At base 0 the two counters are 56 bytes apart and both land in line 0; at base 16 the boundary falls between them and they do not. Nothing in the source moved — the answer is in the low six bits of an address, so this bug appears on one run and hides on the next, and the test that caught it once will not catch it again.

A full line of separation is the only promise, and the line is a number the source cannot see. Put the padding back to the 56 bytes section 05 bought and change the machine underneath it:

Because Apple Silicon's granule is 128 bytes, the padding that is exactly right on x86-64 puts both counters back in one line, and the same binary is fast on the server and slow on the laptop. Drag the padding out to 120 bytes and they separate again — which is exactly the point: the amount is a property of the machine, not of the source, andalignas(std::hardware_destructive_interference_size) is the only spelling that asks the compiler rather than guessing. Five numbers carry the page: a line is 64 bytes (128 on Apple Silicon — getconf LEVEL1_DCACHE_LINESIZE tells you which), an uncontended atomic is 20 cycles, a same-socket bounce about 70 ns, a cross-socket bounce about 250 ns, and one contended line tops out near 14 million writes a second however many cores you throw at it.

Red flags

• Two or more std::atomic fields adjacent in a struct, written by different threads.
• A producer index and a consumer index in the same ring-buffer struct with no padding between them.
• vector<T> where sizeof(T) < 64 and each element has its own writer.
• A hot counter or version field embedded in a node of a read-heavy structure — every update invalidates the node for every reader.
• A padding constant written as a literal rather than read from the platform — alignas binds the type, not the allocation, and before C++17's aligned operator new a vector<Padded> could ignore even that.