5.2 Cache Coherence and False Sharing

Cache Mapping addresses how a core efficiently reuses recently accessed data. This lesson extends the discussion to multiple cores with private caches, explaining MESI's stable states, ownership transfer, and false sharing.

Multiple copies must behave like a single memory location

Two technicians run threads on Core 0 and Core 1, respectively. Both load the cache line at address X into their private L1 cache. If Core 0 then writes to X, Core 1 must eventually see the updated value, not an infinite loop of reading stale copies.

Cache coherence typically provides two guarantees for each cachable physical location:

• Writes to the same location are eventually observed in a consistent order by all participants;
• A core’s read cannot indefinitely use a stale copy that has already been replaced by another core.

The precise definition of these guarantees varies by architecture, but the core idea is coordinating copies of a single location. This is not the same as a memory consistency model, which defines how reads and writes to different addresses can be reordered and observed across processors. It also differs from C/Java memory models, which introduce concepts like data races, atomic operations, happens-before relationships, and compiler optimizations.

Hardware coherence does not guarantee correctness for C programs with data races. Compilers can cache variables and reorder memory accesses, and undefined behaviors at the language level are not automatically fixed by MESI protocols.

MESI's Four Stable States

Classic MESI assigns each cache line a stable state:

State	Readable by this core	Writable by this core	Can other caches have valid copies	Consistent with next layer
Modified	Yes	Yes	No	No, this copy is newer
Exclusive	Yes	Yes, later becomes M	No	Yes
Shared	Yes	No, must acquire ownership first	Yes	Yes
Invalid	No	No	N/A	This copy is unavailable

This is a foundational table of stable states. Real-world protocols also include transient states, request queues, retries, directory structures, or snooping filters. Variants like MESIF or MOESI introduce forwarder or owned states.

Reading an Invalid Line

The core issues a read request. If no other cache holds a valid copy, it typically receives an Exclusive state. If another cache already holds a shared copy, it receives a Shared state. If another core holds Modified data, the latest value may be directly forwarded by the owner or processed through some intermediate cache, without necessarily first writing back to DRAM.

Writing a Shared Line

The core must acquire exclusive write permission, send invalidation requests to all current sharers, and wait for protocol-required acknowledgments. Afterward, the core transitions to Modified state, and all other copies become Invalid.

Writing an Exclusive Line

Since no other valid copy exists, the core can typically transition silently from Exclusive to Modified without first broadcasting an invalidation request.

The protocol governs the entire cache line. Even if a thread writes different bytes within the line, ownership migrates at the line level, this is precisely the root of false sharing.

Coherence Does Not Automatically Provide Atomicity

The fact that a cache line is coherent does not imply that any read-modify-write operation within that line is atomic. counter++ At least includes reading, computing, and writing back; when threads interleave, updates can still be lost.

In C, developers should use <stdatomic.h> atomic types and operations, or implement synchronization via locks. Whether a specific atomic width is lock-free, object alignment requirements, and cross-line behavior are determined by both implementation and instruction set architecture (ISA).

#include <stdatomic.h>

static atomic_ulong counter = 0;

static void increment(void) {
    atomic_fetch_add_explicit(&counter, 1UL, memory_order_relaxed);
}

memory_order_relaxed guarantees atomic read-modify-write operations on this object, but does not establish any cross-thread ordering with respect to ordinary data. If the counter also serves as a signal that "data is ready," then the appropriate release/acquire or stronger ordering must be chosen based on the protocol.

Atomic instructions also require cache line ownership. When multiple cores frequently update the same atomic counter, the cache line migrates between cores, creating a serial bottleneck. "Lock-free" only describes progress properties, it does not guarantee the absence of contention cost.

False Sharing: Two Technicians Never Touch the Same Variable, Yet the Line Keeps Flipping

Core 0 only updates counter A, and Core 1 only updates counter B; the source code shows no shared writes. Still, if A and B happen to reside in the same cache line, both cores will take turns competing for ownership of that entire line. The issue arises at the hardware level, not because of variable names.

Suppose left and right are two independent atomic counters that happen to fall within the same cache line:

line N: [ left ][ right ][ unused bytes ... ]
          Core 0   Core 1

Every time Core 0 writes to left, it must acquire write permission on the line, invalidating Core 1’s copy. Then Core 1 writes to right, reclaiming ownership. There’s no shared logical variable in the program, yet at the hardware level, both cores are sharing the same cache line. This is called false sharing.

It differs from true sharing. When two threads update the same queue head or a lock, synchronization is inherently required. Padding objects to different cache lines cannot eliminate the semantic sharing between them.

Alignment Is Just One Condition for Fixing a Problem

If the target platform confirms a coherence line of 64 bytes, each hot-write counter can be given its own independently 64-byte aligned object. C11 example:

#include <stdalign.h>
#include <stdatomic.h>
#include <stddef.h>

enum { CACHE_LINE_BYTES = 64 };

typedef struct {
    alignas(CACHE_LINE_BYTES) atomic_ulong value;
} PaddedCounter;

_Static_assert(alignof(PaddedCounter) >= CACHE_LINE_BYTES,
               "counter alignment is too small");
_Static_assert(sizeof(PaddedCounter) % CACHE_LINE_BYTES == 0,
               "array elements may share a line");

static PaddedCounter counters[2];

Increasing the alignment of a type typically also rounds the sizeof up to a multiple of that alignment, and the second assertion explicitly specifies the array stride requirement. Still, keep in mind:

• 64 comes from the deployment target, not from an ISO C-defined cache constant;
• the allocator must support extended alignment, and dynamic allocation must use aligned_alloc while adhering to size-multiple constraints;
• adjacent objects, linker layout, and larger coherence granules may still affect the outcome;
• padding increases memory footprint; overuse can degrade capacity locality.

Applying alignas(64) just once to the entire "two-counter structure" does not separate the two internal fields; it only ensures the structure's starting point is aligned. Each hot-write slot requires its own independent stride.

A Better Approach Is Often to Reduce Shared Writes

Padding works well when threads need to frequently write to their own slots. Counting, aggregation, and batch processing can reduce the number of ownership transfers:

1. Each thread accumulates data in a private variable or private array;
2. Shared results are written only after processing a batch of data;
3. A final reduction phase consolidates the results.

#include <stdatomic.h>
#include <stdbool.h>
#include <stddef.h>

static atomic_ulong total = 0;

static void publish_batch(size_t items,
                          bool (*do_one_item)(size_t index)) {
    unsigned long local = 0;
    for (size_t index = 0; index < items; index++) {
        local += do_one_item(index) ? 1UL : 0UL;
    }
    atomic_fetch_add_explicit(&total, local, memory_order_relaxed);
}

The specific business logic behind do_one_item is omitted here. The key insight is that shared line access is contested only once per batch, not once per individual item. The batch size involves a trade-off between throughput, visibility latency, and overflow scope.

Sharded counters, per-CPU data, thread-local storage, and layered reduction all follow this same principle. If strict global consistency at every moment is required, higher synchronization costs must be accepted, or an alternative consistency semantics must be designed.

Beyond MESI: Directory and Interconnects

A small number of cores can monitor shared requests on the interconnect via snooping; however, as core count increases, the cost of broadcasting becomes prohibitive. Systems commonly use a directory to track which caches may hold copies of a given block, sending messages only to relevant nodes.

Inside the chip, architectures may also include mesh or ring interconnects, multi-cluster caches, snooping filters, and home agents. In multi-slot NUMA systems, remote memory access and cross-socket ownership transfers become significantly more expensive. The "shared memory" a program sees is underpinned by physically disparate distances.

Coherence protocols ensure correct coordination of cache copies, but they do not guarantee uniform access latency. Thread placement, first-touch data behavior, and data partitioning all influence how far a request must travel.

Why Store Buffer Doesn't Break Coherence

Processors often place store operations into a store buffer first, allowing the execution pipeline to proceed without waiting for ownership transfers or completion of lower-level caches. When the same address is later loaded by the same core, the store-to-load forwarding mechanism can directly read the newly written value.

This creates a mismatch between when an operation is considered "completed" and when other cores can observe it. Coherence and the memory model jointly constrain the final observed order of operations. Memory fences establish necessary ordering in specific scenarios, but they do not mean "flushing all caches" or serving as a universal fix for misunderstanding atomic semantics.

Similarly, the timing at which dirty data in a write-back cache is written to DRAM is separate from when another coherent core can observe the updated value. Other cores can obtain the latest data from either the owner core or a shared cache, without needing to wait for DRAM to become the latest copy.

How to Prove That a Performance Issue Is Actually False Sharing

Looking only at "multithreaded performance is slower than single-threaded" is insufficient. A credible diagnosis requires multiple lines of evidence:

• Confirm that threads are actually running on separate cores, rather than due to scheduling or resource allocation issues alone;
• Examine hot-write addresses to verify they fall within the same coherence line;
• Use platform-supported performance events such as HITM, snoop, or cache-to-cache transfers to observe line movement;
• Modify only layout or partitioning strategies, keeping the algorithm and workload unchanged;
• Repeat measurements and report CPU model, topology, compilation options, and thread binding.

Some counters are only available on specific microarchitectures, and event names may vary. Clock-time improvements are a result, not a cause; a reduction in ownership events provides stronger causal evidence.

Using volatile in a benchmark does not substitute for atomic operations and does not prevent data races. If two threads write to the same non-atomic object, the C program has undefined concurrent semantics, and any measured results are not trustworthy.

coherence, consistency, durability three axes

Issue	Primary mechanism
Whether multiple cache replicas remain synchronized	cache coherence
The order in which operations at different addresses become visible	ISA/language memory model, atomics, fences
Whether data persists after power loss	durable storage protocols, flush, barrier, device guarantees

The "final write-back to the next layer" in write-back caching does not equate to durability. DRAM typically loses data upon power loss, and SSD controllers may also use volatile buffers. Database mechanisms such as WAL (Write-Ahead Logging), fsync, and flush operations to persistent memory address the third axis (durability) and cannot be explained using MESI states.

Hands-on Tracking of Ownership

1. Start with both cores holding the S state, and draw the stable state sequence for Core 0 writing, Core 1 reading, and Core 1 writing.

2. Explain why a Modified owner can deliver data to a requester without first updating DRAM.

3. Compare true sharing of a single atomic counter with false sharing between two adjacent counters; can padding fix one of these issues?

4. Design a merging protocol for per-thread counters, and explain whether readers can obtain real-time precise values or only periodic snapshots.

5. Identify why aligning a struct with alignas(64) can still result in internal fields sharing a cache line.

6. Write a release/acquire publication example that demonstrates why a relaxed counter cannot automatically publish changes to a regular data block.

The Address Will Undergo One More Translation

Cache typically maintains consistent copies using physical addresses or physical tags, while programs operate with their own virtual addresses. The next chapter delves into Virtual Memory, tracing the second half of a load operation through virtual pages, TLB, page tables, and page faults.