False sharing problem: Visual walkthrough — Hardware deep dive

Nothing here is assumed. If you have never seen a "cache line", a "core", or the symbol $⌊ \cdot ⌋$ , you will meet each one before it is used.

Step 1 — Memory is a long ruler of bytes

WHAT. A computer's memory is one enormous row of little numbered boxes. Each box holds one byte (8 bits, enough for one small number or one letter). The number on the box is its address. We write addresses in hexadecimal (base 16) with a 0x in front — so 0x1000, 0x1001, 0x1002, … are three boxes sitting side by side.

WHY. Everything about false sharing comes from which boxes sit next to which. So before anything else we must picture memory as a straight ruler with a position for every byte. No triangles, no protocols yet — just the ruler.

PICTURE. Below, the ruler runs left to right. Two variables counter[0] and counter[1] are 4-byte integers. Notice they are right next to each other — counter[1] begins exactly where counter[0] ends.

Step 2 — The hardware never moves one byte; it moves a whole line

WHAT. The CPU never fetches a single byte from memory into its fast local storage (the cache). It always grabs a fixed-size chunk called a cache line. On almost every modern machine that chunk is $L = 64$ bytes.

WHY. Fetching 64 bytes at once is cheaper per byte than 64 separate trips (memory likes bulk moves, and nearby data is usually needed together). This is a good bet — but it is exactly the bet that backfires in false sharing. The unit of transfer being bigger than one variable is the seed of the whole problem.

PICTURE. We now group the ruler into blocks of 64 bytes. Both our counters fall inside the same shaded block. That single shaded block is the cache line the hardware treats as one indivisible unit.

See Cache line size and alignment for where the 64 comes from.

Step 3 — Which line is an address in? Meet the floor function

WHAT. To decide whether two variables live in the same cache line we compute a line number for each address. Divide the address by $L$ and throw away the fractional part. Throwing away the fractional part is what the symbol $⌊ x ⌋$ (the floor) means: round down to the nearest whole number.

WHY. We need a yes/no test — "same line or not?" — and the only thing that matters is which 64-byte block you land in, not where inside it. Dividing by 64 and flooring collapses every address in one block to the same integer. That integer is the block's identity.

PICTURE. The number line of addresses is split into unit-64 bins. Every address in a bin maps down to the same line number. Watch both counters collapse onto line number 64.

Worked check. counter[0] at 0x1000 = 4096. counter[1] at 0x1004 = 4100. $⌊ \frac{4096}{64} ⌋ = ⌊ 64.0 ⌋ = 64, ⌊ \frac{4100}{64} ⌋ = ⌊ 64.06 ⌋ = 64.$ Same line number ⇒ they collide.

Step 4 — Only one core may own a dirty line (the MESI rule)

WHAT. When several cores keep copies of the same cache line, a protocol keeps them honest. The common one is MESI, named for the four states a line can be in per core: Modified, Exclusive, Shared, Invalid. The one rule we need: a line may be in the Modified state in at most one core at a time.

WHY. If two cores could both hold a modified copy, their edits would disagree and memory would be corrupt. To write, a core must first make itself the sole owner — which means telling every other core "throw your copy away" (set it to Invalid). That announcement is the expensive part.

PICTURE. Two cores, one shared line. Core 0 wants to write, so it broadcasts an invalidate to Core 1; Core 1's copy goes dark (Invalid). Now Core 0 alone holds the Modified line.

Full state machine lives in Cache coherence protocols.

Step 5 — The ping-pong: two owners fighting forever

WHAT. Put Steps 3 and 4 together. Core 0 writes counter[0]; Core 1 writes counter[1]; they are the same line. So each write forces the other core to give up ownership. Ownership bounces back and forth like a ping-pong ball, even though the two cores touch different bytes and share no logical data.

WHY. The hardware cannot see that byte 4096 and byte 4100 are unrelated. It only sees "someone wrote to line 64". Correctness (Step 4) forces a full invalidation on every write. Different variables, same line ⇒ full coherence cost on every single iteration.

PICTURE. A timeline. Each core's write flips the line's owner and sends an invalidate arrow the other way. The pattern never settles.

This is why "I added more cores and it got slower" happens — see Multicore scaling.

Step 6 — The fix: push each variable into its own line (padding)

WHAT. We cannot change $L$ ; the hardware fixes it at 64 bytes. So instead we make each core's variable fill a whole line by itself by adding dead filler bytes — padding — after it. Then the floor test in Step 3 fails for the two variables, and no line is ever shared.

WHY. Recall the collision came purely from $⌊ A_{0} /64 ⌋ = ⌊ A_{1} /64 ⌋$ . If we force the addresses to be at least 64 apart and line-aligned, the two floor values differ, so there is nothing to fight over. We pay in wasted memory (the padding) to buy back cycles.

PICTURE. Same two counters, but now each sits at the start of its own 64-byte block with 60 bytes of grey padding behind it. The line numbers are now 64 and 65 — different bins, no invalidations.

Numeric check. Padded counters at 0x1000 (=4096) and 0x1040 (=4160): $⌊ \frac{4096}{64} ⌋ = 64, ⌊ \frac{4160}{64} ⌋ = 65 \Rightarrow different lines. Fixed.$

In C++17 the compiler tells you the right pad size via std::hardware_destructive_interference_size with alignas. See Memory allocators for how allocators can under- or over-align you.

Step 7 — The degenerate cases (so nothing surprises you)

WHAT & WHY. A good derivation must cover the boundaries, not just the pretty middle. Four edge cases:

Both variables in the same byte range but only read (never written). No writes ⇒ no invalidations ⇒ MESI leaves the line Shared in both caches forever. No false sharing. False sharing is a write problem.
One writer, many readers. The single writer keeps re-taking ownership, forcing readers to refetch. This does cost — it is "true-ish" sharing of one line — but it is not the symmetric ping-pong of Step 5.
Variables land in different lines by luck ( $⌊ A_{0} /64 ⌋ \neq = ⌊ A_{1} /64 ⌋$ already). No fix needed. Padding would only waste memory.
A single variable straddles a line boundary (its bytes span two lines). Then it collides with both neighbouring lines' owners. Alignment (alignas) prevents this by starting it cleanly.

PICTURE. The four cases side by side: two grey (read-only), one asymmetric (one writer), one already-separated, and one straddling. Only the symmetric two-writer, same-line case is the true false-sharing villain.

Atomics don't rescue you here: Atomic operations guarantee correctness but a padded and atomic layout is what you need — and Lock-free data structures rely on exactly this padding to scale.

The one-picture summary

Every idea in one frame: the ruler → the 64-byte line → the floor test → the ownership rule → the ping-pong → the padded fix.

Recall Feynman retelling — say it back in plain words

Memory is a long row of numbered boxes. The CPU is lazy and never grabs one box; it grabs a 64-box tray at a time — that tray is a cache line. To know if two variables ride the same tray, divide each address by 64 and round down; equal answers mean same tray. Now the safety rule: only one core may be scribbling on a tray at once, so before scribbling a core yells "everyone else, tear up your copy!" — that yell is slow. If two cores keep their own variables on the same tray and both keep scribbling, they take turns yelling and tearing up each other's copies forever, even though they touch different boxes. That's false sharing — and it can make code 50–100× slower. The cure: give each core's variable its own whole tray by stuffing 60 junk bytes behind it (padding), so their divide-by-64 answers differ and nobody ever has to yell. Just remember: the villain only shows up when cores write; read-only trays never fight.

Recall Test yourself

Do two ints at addresses 4096 and 4100 share a 64-byte line? ::: Yes — floor(4096/64)=64 and floor(4100/64)=64, same line number. What single operation is required for false sharing to occur? ::: A concurrent write — reads alone leave the line Shared with no invalidations. Why can't the hardware just "see" the variables are independent? ::: Coherence works at line granularity; it only knows a 64-byte block was written, not which byte. How much filler does a 4-byte int need to own a 64-byte line? ::: 60 bytes of padding (4 + 60 = 64). After padding, what makes the two counters safe? ::: Their addresses now differ by ≥64 and are line-aligned, so their floor-divided line numbers differ (64 vs 65).