False sharing

Why do two processor cores slow each other down when neither one ever touches the other's variable?

Two threads on two cores, each incrementing its own counter in a loop. No lock, no atomic operation, no variable in common: by every reading of the source they are independent.

Yet the pair runs slower than a single thread doing both loops. Nothing in the program says these threads interact, so the interaction is happening somewhere the program cannot see. Where?

Start with a bookkeeping question that has nothing to do with concurrency. A cache holding a copy of memory must record which memory — an address tag plus state bits. Track single bytes and the tag is larger than the data it describes. So caches track blocks: a cache line, commonly 64 bytes on today's mainstream designs and 128 on some, though the figure is a property of the machine and not a law.

Now add the second core. Both may hold copies of one line, so the machine needs a rule stopping a core from reading a value another has already changed. The rule, in the MESI family of coherence protocols, is ownership: a cached line is Modified, Exclusive, Shared or Invalid, and a core may only write to a line it holds exclusively. Acquiring that means telling every other cache to invalidate its copy.

Put the two facts side by side and the answer falls out. The unit the program cares about is a variable, maybe 8 bytes. The unit the protocol works in is a line, 64. When two variables land in one line the protocol cannot tell them apart — no machinery could, because the state bits describe the line, not its contents.

Trace one round. Core 1 writes counter A, taking the line exclusively, so core 2's copy is invalidated. Core 2 then reads counter B — its own variable, untouched by anyone — and misses, because its copy of the line is gone. It requests the line, taking ownership, which invalidates core 1's copy. Core 1 writes A again and the exchange repeats, every iteration.

The arithmetic that decides whether this happens to you. For a 64-byte line, two addresses share a line exactly when they agree in every bit above the low six — when a >> 6 == b >> 6. Consider the most natural way anyone writes this: an array of per-thread counters, 8 bytes each, thread i at offset 8*i*. Threads 0 through 7 sit at offsets 0 to 56, every one below 64. Eight threads, one line — an array written precisely to keep threads apart has put all eight in the worst possible place. The fix is to pad every entry to the line size and align the array to a line boundary, so thread i sits at offset 64*i*. The cost is exact: 512 bytes instead of 64, an eightfold expansion to hold the same eight numbers.

Worth it? A hit in a core's own first-level cache is a handful of cycles; a line taken from another core's cache costs tens within a die and more across sockets. I will not attach vendor numbers, which vary by generation and topology, but the ladder is set out in this collection's piece on caching and the gap is at least an order of magnitude.

Underneath the latency there is a worse effect, and it is why the pair can lose to a single thread. Only one core may hold the line for writing at any instant, so N writers on one line do not run in parallel and slowly — they run in a queue. False sharing converts parallel work into serial work and charges coherence traffic on top. Adding cores makes it worse, which is the signature separating it from ordinary slowness.

The falsification test. Run the identical program twice, altering only the offset of the counters: 8 bytes apart, then padded and aligned to the line size. Algorithm, instruction count and working set are essentially unchanged; only the addresses moved. The prediction is a large runtime difference in the padded direction, with coherence-miss counters falling in step. There is a positive control too: the account requires at least one writer, since several caches may hold a line in the Shared state at once, so making every access a read must abolish the effect. The refuting observation is padding that changes nothing, or a slowdown surviving separation onto different lines — either would put the cause elsewhere, in a real lock, allocator contention, remote-node placement, or bandwidth saturation.

Three things to hold apart.

First, false sharing is not sharing. True sharing is several threads hitting the same variable: inherent contention, which no padding helps and which wants an algorithmic answer such as per-thread accumulation with one combining step at the end. False sharing is contention manufactured by layout alone, and layout is what you can change.

Second, this is the bill for a bet made elsewhere. The piece on caching argues that moving data in blocks is a sound wager on spatial locality — fetch the neighbours, they will probably be wanted. That is excellent for one core walking an array, and false sharing is exactly its cost when two cores write into one block. Same mechanism, opposite sign; the fixed point of difference is the number of writers.

Third, name the constraint rather than the technology. Two durable facts do the work: coherence must be maintained at a granularity coarser than a byte, and moving ownership between cores costs far more than a local hit. Sixty-four bytes is this decade's number — which is why hardcoding 64 into a padding macro is a portability bug, when the runtime can report the interference size and 128-byte lines exist today.

Two caveats. Padding is not free: it inflates the working set, so a structure padded everywhere can lose more to capacity misses than it gains. And adjacent-line prefetchers mean one line's width is occasionally not enough. Measure the fix.

• How per-core accumulation with a final reduction removes true sharing, and when the combining step becomes the bottleneck.

Every term the collection defines is gathered in the glossary.