Cache coherency and MESI

Each core has private caches. If two cores both hold a copy of a line and one writes it, the other copy is stale. Hardware cache coherency ensures every core sees a single, consistent value for each location: at any moment a line may be cached read-only by many cores, or writable by exactly one.

The protocol behind that on most processors is a variant of MESI, named after the four states a line can be in, in each core's cache.

Intel adds a Forward state and AMD an Owned state to reduce memory traffic, but MESI is enough for reasoning about code.

When a core wants to write a line that it holds in Shared state, or does not hold at all, it must gain ownership: it sends a request that invalidates every other copy and waits for the acknowledgements. Only then can the write complete. The next time another core touches the line, it misses, fetches the line from the writer's cache, and the cycle continues.

A line written by several cores in turn therefore travels between them on every write. Each transfer costs roughly what an L3 hit or more costs, tens of nanoseconds on one socket and well over a hundred across sockets, and the transfers serialise: only one core can own the line at a time.

That answers the question. Each fetch_add needs the counter's line in Modified state on the incrementing core. With eight cores incrementing, the line moves continuously, every increment waits for a transfer, and they happen one at a time. One thread incrementing a line that stays in its own L1 is far faster than eight threads queueing for one line.

The fixes are the general ones for contended shared data:

• Per-thread counters, each on its own cache line, summed when read. Writes become local; only the occasional reader pulls lines across.
• Batching: accumulate locally and publish occasionally.
• Ownership: one thread owns the value and others send it messages.

Many cores can hold a line in Shared state at once and read it from their own caches without any traffic. That is why read-mostly data, such as configuration or reference data, scales perfectly, and why a seqlock or a versioned snapshot works well: readers share the line; only the single writer forces invalidations, and only when something changes.

The asymmetry gives a rule for designing hot data: separate what is written from what is read, and separate what different threads write.

A thread waiting for a flag set by another core should spin on a plain load, not on an atomic exchange or compare-and-swap. A load keeps the line in Shared state in the waiter's cache and costs nothing until the writer changes it. A read-modify-write in the loop requests ownership every iteration and drags the line away from the thread trying to set it. That is why the spinlock in Module 4 tests with a load before trying the exchange.

On a two-socket machine, coherence traffic between sockets goes over the interconnect, which is several times slower than within a socket. Two threads that share a hot line on different sockets pay that on every transfer. Pinning cooperating threads to cores on the same socket, ideally sharing the same L3, is part of the system setup covered in Module 6.