False sharing problem: Foundations — Hardware deep dive

This page assumes nothing. Before you can understand False sharing problem, you need a handful of ideas — memory as a ruler of addresses, what a "cache" is, what a "cache line" is, and the little bit of arithmetic ( $⌊ \cdot ⌋$ , the floor function) the parent note uses. We build each one, anchor it to a picture, then show how they stack up into the topic.

1. Memory is a long numbered street

Before anything, picture computer memory as a single very long street where every byte (one storage slot holding a number from 0 to 255) has a house number. That house number is called an address.

Why hexadecimal and not ordinary base-10? Because memory sizes and boundaries are powers of two, and hex lines up cleanly with them: 0x40 is exactly 64 in decimal, 0x80 is 128, and so on. Look at the figure — each tick is one byte; the number under it is its address.

Recall How do we turn a hex address into an ordinary decimal number?

Each hex digit is a power of 16. For 0x1000: $1 \times 1 6^{3} + 0 + 0 + 0 = 1 \times 4096 = 4096$ . For 0x1004: $1 \times 1 6^{3} + 0 + 0 + 4 = 4096 + 4 = 4100$ . We will reuse exactly these two conversions later.

2. A variable lives at an address and has a size

When you write int counter in code, the machine reserves a stretch of the street for it. Two facts matter:

Where it starts — its address, written $addr (v)$ for a variable $v$ .
How wide it is — its size in bytes, written $sizeof (v)$ .

So an array int counter[2] might put counter[0] at $addr = 0x1000$ (taking bytes 0x1000–0x1003) and counter[1] right after it at $0x1004$ . They are different variables but adjacent on the street. Hold that thought — it is the whole trap.

3. The cache: a fast desk next to each core

A core is one independent worker inside the CPU that runs instructions. Main memory (the long street) is far away and slow to reach. So each core keeps a small, fast personal notebook near it called a cache.

Here is the catch that starts the whole story: the cache does not copy one byte at a time.

4. The cache line: the unit of transfer

When a core wants even a single byte, the cache fetches a whole fixed-size block around it. That block is a cache line. Throughout this page we will also picture a cache line as a fence — a visual nickname for the exact same 64-byte block, nothing more.

Look at the figure: the street is now grouped into fixed 64-byte fences (cache lines). Notice counter[0] (orange) and counter[1] (teal) both fall inside the same fence. The hardware can only move the whole fence — never just one variable. This is the "folder, not the page" from the parent note's roommate analogy.

We would like to write a formula "which cache line does an address belong to?", but it needs one arithmetic tool — the floor function — that we have not defined yet. So we build that tool first (Section 5), then state the formula.

5. The floor function $⌊ x ⌋$ — why the topic needs it

Why this exact tool, and not ordinary division or rounding? Because we are asking a grouping question: "which 64-byte fence is this byte inside?" Dividing an address by 64 and dropping the remainder gives exactly the fence number, no matter where inside the fence the byte sits. Rounding (which can go up) would misplace bytes near a fence edge into the next fence. Floor is the tool that answers "which whole block?" precisely.

Now that floor is defined, we can write the promised formula.

The figure walks the arithmetic: divide the address by 64, land on a decimal, and floor it. Both counters floor down to the same integer — that is why they share a line.

6. Coherence: keeping copies honest

If every core caches its own copy of a line, what happens when one core changes a byte? All the other copies are now stale (out of date). The rule that keeps every core seeing a consistent view is cache coherence, and the parent note names the specific protocol: MESI.

The rule that bites: only one core may hold a line in Modified state at a time. So each write forces the writer to invalidate everyone else — and if two cores keep writing the same line, they take turns kicking each other's copy out. That back-and-forth is the "ping-pong" the parent note describes. You do not need the protocol's full detail here; Cache coherence protocols covers it. Just remember: a write demands exclusive ownership of a whole line.

7. Cost, measured in cycles

The parent note quotes numbers in cycles. One cycle is one tick of the CPU clock — the smallest unit of time the processor counts in.

That ~50–100× gap is why false sharing is a problem worth a whole topic: the work is identical, but the hidden coherence traffic multiplies its cost.

Putting the pieces together

The map below is read bottom-up and mirrors the figures: the street of addresses (figure s01) plus the fence carving (figure s02) give you variables sharing a line; the floor arithmetic (figure s03) is what proves they share it; coherence's one-writer rule plus the cycle cost turn that shared line into the false-sharing slowdown.

Read it bottom-up: adjacency in memory (s01, s02) plus the floor test (s03) plus coherence's per-line ownership rule = false sharing, and the cycle cost is what makes it hurt.

Equipment checklist

Cover the right side and answer each before moving to the mechanism page.

What is an address, and why do we write it in hex? ::: A whole number naming one byte of memory; hex because memory boundaries are powers of two and line up cleanly (0x40 = 64).
Convert 0x1000 and 0x1004 to decimal. ::: $1 \times 1 6^{3} = 4096$ , and $4096 + 4 = 4100$ .
What do $addr (v)$ and $sizeof (v)$ mean? ::: The first byte's address of variable $v$ , and how many consecutive bytes $v$ occupies.
What is a cache, and why does each core have one? ::: A small fast per-core copy of memory; reaching it costs ~1–2 cycles versus ~100–200 for main memory.
What is a cache line (and what does "fence" mean in our figures)? ::: The smallest block the cache ever moves as one unit, $L = 64$ bytes; "fence" is just our picture-nickname for the same block.
Compute the line number of address $A$ . ::: $⌊ A / L ⌋$ — divide by 64 and round down.
What does $⌊ x ⌋$ do, and why floor rather than rounding? ::: Rounds down to the nearest whole number; floor answers "which whole block?" exactly, since rounding up could misplace edge bytes.
When do two variables share a cache line, and what does that condition assume? ::: When $⌊ addr (v_{i}) / L ⌋ = ⌊ addr (v_{j}) / L ⌋$ ; it assumes each variable fits entirely inside one line (a spanning variable can share with two lines).
What do the letters M, E, S, I stand for? ::: Modified, Exclusive, Shared, Invalid — the four cache-line states of the MESI coherence protocol.
What does "invalidate" mean in cache coherence? ::: Force other cores to throw away their now-stale copy of a line before you write it.
How many cores may hold a line in Modified state at once? ::: Exactly one.
What is a cycle, and what is the rough cost gap between a local write and a coherence miss? ::: One CPU clock tick; ~1–2 cycles local versus ~100–200 for a remote-modified line, a ~50–100× gap.

Next: the False sharing problem mechanism page, where these pieces animate into the ping-pong timeline. Related ground you can now safely explore: Cache line size and alignment, Cache coherence protocols, Atomic operations, and Multicore scaling.