Cache Line Transfer, False Sharing, and the Cost of Contention

An atomic increment costs a few cycles when one thread performs it and, on the same hardware, can cost two orders of magnitude more when eight threads perform it on the same address. Nothing about the instruction changed. What changed is where the cache line holding it lives, and how far it has to travel before the increment can proceed.

The gap between those two cases is the single most important performance fact about concurrency primitives, and it is not visible in the instruction set. A lock xadd on an address held exclusively by the executing core is a register operation with an extra internal step. The same instruction on an address held by another core must first obtain ownership, which means a coherence transaction that takes the line away from the other core, waits for it to acknowledge, and delivers it. The latency of that transaction is a property of the interconnect, not of the instruction, and it is measured in tens to low hundreds of cycles rather than in single digits.

What a coherence transaction does

On a typical multicore with a snooping protocol, each cache line is in one of a small number of states: modified and owned exclusively by one core, shared read-only by several, or invalid. A write to a line requires the writer to hold it exclusively, so a core that wants to modify a line it does not own must first invalidate every other copy.

The sequence for a contended increment is therefore: the core issues a request for exclusive ownership, the request is broadcast to the other cores, each invalidates its copy and acknowledges, the line is transferred with its current value, and only then can the arithmetic proceed. The total is a round trip to the interconnect plus the arbitration needed to serialize the responses. Because only one core can hold the line exclusively at a time, a stream of increments from several cores degenerates into a queue of line transfers, and the throughput is bounded by the transfer latency rather than by the arithmetic.

The same mechanism underlies every read-modify-write instruction, including a locked compare-exchange, and it underlies a plain load that misses: a load for a line held exclusively by another core also requires a transfer, though without the invalidation round trip. A load of a line that no core holds is a memory access, with a latency set by the DRAM hierarchy rather than by the interconnect.

Cache line size is 64 bytes on x86-64 and on the common Arm implementations, and 128 bytes on some POWER designs. It is also the granularity of transfer and of invalidation. That single number explains most of the surprising behaviour in this area: two variables that are logically independent but that fit within 64 bytes of each other are, from the coherence protocol’s point of view, one object.

False sharing is contention without a shared variable

Two threads each increment their own counter. The counters are adjacent in a struct, so they share a cache line. Every increment by either thread invalidates the other’s copy, and the line ping-pongs between the cores exactly as if the threads were fighting over the same variable. The program has no data race and no correctness problem. It has a performance problem that is invisible in the source and disappears if the fields are separated.

The diagnosis is not obvious from timing alone, because the effect looks like ordinary contention. It is visible in profiling that counts coherence events: a line that produces a large number of invalidations while being accessed by several cores with no true sharing is the signature. Some processors expose hardware counters for this; all of them make it visible through the ratio of cycles to instructions in code that does almost nothing.

/* counters that share a line */
struct stats { _Atomic long a; _Atomic long b; };   /* adjacent, same 64 bytes */

/* padded so each counter owns its line */
struct padded { _Atomic long v; char pad[64 - sizeof(long)]; };

The padding is deliberately sized to the line, and the alignment matters as much as the size: an array of padded counters only avoids sharing if each element starts on a line boundary, which requires an alignment attribute or an allocator that returns line-aligned blocks. Sizing without aligning produces elements that straddle a boundary and share with a neighbour anyway.

Padding is pure waste when the counters are not contended. A structure with sixteen counters padded to 64 bytes occupies a kilobyte, which is a whole L1 capacity fraction on some designs and a real cost in cache footprint. The decision is between space and coherence traffic, and the correct answer depends on whether the fields are written by different threads concurrently, which is a property of the access pattern and not of the type.

Sharding as an alternative to padding

When the contention is real rather than false, padding does not help: the threads are incrementing the same variable, so there is nothing to separate. The alternative is to give each thread its own copy and combine at read time.

#define SHARDS 8
static _Atomic long counts[SHARDS];

static void bump(int tid)
{
    atomic_fetch_add_explicit(&counts[tid], 1, memory_order_relaxed);
}

static long total(void)
{
    long sum = 0;
    for (int i = 0; i < SHARDS; i++)
        sum += atomic_load_explicit(&counts[i], memory_order_relaxed);
    return sum;
}

Each shard is written by one thread, so the increments are uncontended and cost register arithmetic. The reads are relaxed because a counter that reports a slightly stale total is usually acceptable; the alternative, a sequentially consistent read, would impose a global order that no consumer of an approximate statistic needs.

The trade is exactness for throughput. The total is not a snapshot of a single instant: shards are read one after another while other threads increment, so the sum includes some increments that happened after others were read. That is a linearizability failure, and it matters for a statistic that drives an allocation decision and does not matter for a counter of requests served. The same sharding appears in Progress Guarantees and the Lock-Free Hierarchy as the standard mitigation for a contended single word.

Sharding also changes the read cost. A read now touches every shard, so it costs one cache line per shard rather than one line, and if the shards are padded that is a kilobyte of traffic per read. The pattern is only worth it when writes vastly outnumber reads.

Backoff and the shape of the queue

When several threads loop on a compare-exchange against one word, each failure is a line transfer, and the losers immediately retry, producing a burst of transfers that keeps the line moving. The threads are not making progress; they are taking turns being the one that loses.

Adding a delay after each failure reduces the traffic, because a thread that waits has a chance of finding the line already settled. The delay must be short enough to keep latency low and long enough to avoid the transfer. Exponential backoff with a cap is the standard shape, and the cap is what makes it practical: unbounded doubling produces delays that dwarf the operation being performed.

A better structure than backoff is to stop having all threads compete for the same word. A ticket lock replaces the compare-exchange race with a pair of counters, one for the next ticket and one for the serving number, and each waiter spins on the serving counter rather than attempting a modification. The waiting threads then read a shared line without invalidating it, which turns the queue into a broadcast rather than a fight, as described in Spinlock Design from Test-and-Set to Ticket Locks. The same principle, that readers do not need to transfer the line, underlies the read-copy-update family.

The measurement that does not exist

There is no portable way to state the cost of a contended atomic operation, because it depends on the number of cores, the topology, the interconnect, and the access pattern. The honest formulation is a bound: an uncontended atomic on a line the core already owns is a handful of cycles; a contended one is bounded below by the coherence latency, which is on the order of the L3 access latency and therefore in the range of several tens of cycles on a single socket and substantially more across sockets.

The practical consequence for design is that contention scales worse than linearly. Adding a core to a workload that hammers a single atomic word can reduce total throughput, because the extra core adds transfer traffic without adding capacity. A structure whose scalability depends on a single hot word has a ceiling that no amount of tuning removes; the only fix is to remove the shared word from the hot path.

Non-uniform memory access makes this sharper. On a machine with multiple sockets, a line owned by a core on another socket must cross the interconnect between them, and the latency is several times the intra-socket figure. A sharded counter whose shards are allocated on the wrong node converts a cheap local increment into a remote transfer, which is why thread-local allocation and first-touch placement matter as much as the padding.