Cache Coherence: Why Shared Memory Works At All
Two cores cache the same variable. One writes. Nothing in your code tells the other core to look again — yet it must not read stale data. Coherence is the hardware protocol that guarantees it, running underneath every shared-memory program, and it is emphatically not free.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
The problem, concretely
Core 1 reads X, and the line containing X lands in its private L1 with value 1. Core 2 reads X too, and gets its own copy of the same line, also 1. So far so good — two readers, two copies, no conflict.
Now core 1 writes X = 2. Its private L1 now holds 2. Core 2's private L1 still holds 1, and core 2 has been told nothing. If core 2 reads X again and is allowed to use its cached copy, it reads 1 — a value that is simply wrong, and wrong in a way no amount of careful programming above it could detect or prevent.
Coherence is the hardware's answer: before core 1 may modify that line, it must acquire it exclusively, which means every other cached copy is invalidated first. Core 2's next read misses, goes out to fetch the current version, and observes 2. The guarantee is that all cores see a single consistent value for each location — though when they see it, and how writes to *different* locations are ordered, is a separate question entirely, handled by Why Your Loads and Stores Happen Out of Order.
Coherence is per line, not per variable
The unit the protocol operates on is the cache line, not the variable. Hardware tracks ownership of lines because tracking individual bytes would need far too much state. This single implementation detail is responsible for an entire class of performance bugs, because two variables that have nothing to do with each other are treated as one unit if they share a line.
It also explains why the cost is asymmetric between reads and writes. Any number of cores may hold a line simultaneously in a shared, read-only state — reads scale beautifully. But writing requires exclusivity, so only one core may hold it in a modified state at a time. A line that many cores read is nearly free; a line that many cores write is a serialization point that no amount of lock-free cleverness removes, because the serialization is in the hardware, below your data structure.
| Access pattern | What the protocol does | Scaling behaviour |
|---|---|---|
| Many cores read one line | All hold it shared; no messages after the first fetch | Scales well — read sharing is nearly free |
| One core writes a line nobody else has | Already exclusive; no coherence traffic | Free — the ideal case |
| One core writes, others read | Invalidate all readers, then they re-fetch | Costly, proportional to the number of readers |
| Many cores write the same line | Ownership ping-pongs between cores | Serialises; can degrade as cores are added |
| Cores write different variables on one line | Same as above — the hardware cannot tell | Serialises for no logical reason: False Sharing: Independent Data, Shared Line |
What it costs, and why atomics are not magic
A coherence miss — fetching a line another core owns dirty — is more expensive than an ordinary miss to the shared cache, because it requires locating the owner, transferring the line, and updating ownership state. It is often comparable to going to memory.
This is the honest reason atomic operations and lock-free data structures are not free. A fetch_and_add on a shared counter is a single instruction, but it requires exclusive ownership of that line, so every core incrementing that counter serialises on the transfer. Ten cores hammering one atomic counter do not get ten times the throughput; they get roughly one core's worth, plus interconnect traffic. The fix is never a better atomic — it is to stop sharing the line, by giving each core its own counter and summing at the end.
That pattern — replicate, then combine — is the general answer to write sharing, and it is why False Sharing: Independent Data, Shared Line matters so much: it produces exactly this cost with none of the intent.
Key points
- Coherence guarantees every core observes a single consistent value per location, without any cooperation from your code.
- A core must obtain exclusive ownership before writing, which invalidates every other cached copy.
- The protocol tracks whole cache lines, not variables — the root cause of false sharing.
- Read sharing is nearly free and scales; write sharing serialises regardless of how clever the data structure is.
- Atomics still require exclusive ownership, so a contended atomic counter is a hardware serialization point.
Progressive depth
Overview
Every core caches its own copy of memory. When one core writes, the others must not keep reading stale copies. Coherence is the hardware protocol that invalidates the stale copies automatically, which is why shared-memory programming works without you doing anything.
Practical
The unit is the cache line, and writes need exclusive ownership. So: many readers of one line is cheap and scales; many writers of one line serialises. If parallel code stops scaling, look for written data shared between threads before looking at your locks — and remember the hardware shares by line, so two unrelated variables in one line count as shared.
Advanced
Contended atomics inherit this cost exactly: a fetch_and_add needs the line exclusively, so N cores incrementing one counter serialise on ownership transfer and deliver roughly one core's throughput plus traffic. The general fix is replicate-then-combine. Note also that coherence gives you *per-location* consistency only — it says nothing about the order in which writes to *different* locations become visible, which is why barriers exist independently of coherence.
Internals
Implementations differ. Small systems snoop: requests are broadcast and every cache checks. Large systems use a directory that records which cores hold each line, so invalidations are sent point-to-point instead of broadcast — snooping does not scale past a modest core count because broadcast traffic grows with cores. Protocols extend the basic states to reduce traffic: an Owned state lets a dirty line be shared without writing back, and a Forward state nominates one sharer to answer requests so several caches do not all respond. Which variant a given chip uses is rarely documented and should not be assumed.
Cache Coherence
Change an input and watch which number moves — and which one refuses to.
MESI is one protocol family among several — MOESI and directory-based schemes differ. The states below are the common teaching set.
Both cores start Invalid. Try: core 1 reads, core 2 reads, core 1 writes.
Alternate writes between the two cores and watch the line bounce between Modified and Invalid. Every bounce is a message on the interconnect. Nothing in the source code shows it — and if the two cores are writing two different variables that happen to share this line, nothing in the source code even suggests they interact.
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1Core 1 write → cache controller: the store needs the line in an exclusive state, which it does not currently hold.
- 2Cache controller → interconnect: a request for ownership is broadcast, or sent to a directory that tracks holders.
- 3Interconnect → peer caches: every other core holding the line invalidates its copy and acknowledges.
- 4Ownership granted → core 1: the store completes into the now-exclusive line, which is marked modified.
- 5Core 2 next read → miss: its copy is gone, so it re-requests, and the current data is transferred from core 1.
- • "There are no locks, so it scales" — contended atomics serialise in hardware exactly as a lock would.
- • "The variables are independent, so there is no sharing" — the hardware shares by line, not by variable.
- • "Coherence keeps memory consistent, so I do not need barriers" — coherence is per-location; ordering across locations is Why Your Loads and Stores Happen Out of Order.
- • "Adding cores will help this contended counter" — it will make it worse; each core adds ownership transfers.
Consequences, controls and cost
- • Shared counters and shared flags become scalability bottlenecks well before locks or logic do.
- • Throughput can fall as cores are added when those cores write the same lines.
- • Lock-free structures built on contended atomics do not scale, despite having no locks.
- • Two logically unrelated variables can serialise against each other purely by sharing a line.
- • Give each thread its own copy of written state and combine at the end — replicate, then reduce.
- • Keep shared data read-mostly; read sharing scales, write sharing does not.
- • Separate independently-written variables onto different cache lines with padding or alignment.
- • Where sharing is unavoidable, reduce the *frequency* of writes: batch updates locally and publish periodically.
- • Watch coherence-related miss events — typically counters for cache-to-cache transfers or lines fetched in a modified state from a peer.
- • Sweep thread count; throughput that peaks then falls is a strong indicator of write sharing.
- • Compare per-thread private counters against one shared counter on identical work — the gap is coherence cost.
- • Inspect the layout of the hot written fields and check whether they share a line.
- • Per-thread replication removes contention but multiplies memory use and needs a combine step.
- • Batching local updates before publishing reduces traffic but makes the shared value stale between publishes.
- • Padding to separate lines wastes memory, which itself costs cache capacity.
Scope
§224 — what these claims are specific to.
- GENERALHardware coherence is universal on mainstream shared-memory systems. Some accelerators and embedded multiprocessors provide none, requiring explicit software cache management instead.
- MICROARCH-SPECIFICWhether the system snoops or uses a directory, and the cost of an ownership transfer relative to a memory access, differ substantially between desktop and large server parts.
Misconceptions
Apply it
Where the rest of this lives
Concurrency reasons about whether a lock-free algorithm is *correct* under interleaving. This lesson supplies the reason a correct lock-free algorithm can still fail to scale: the atomic operation it relies on needs exclusive line ownership, and that is a hardware serialization point.