False Sharing and Cache Lines

Problem

A colleague parallelizes a histogram computation: eight worker threads each own one slot in an array counts[8] of 64-bit integers, and each thread increments only its own slot in a tight loop, a hundred million times. No locks are needed, since no two threads touch the same variable. On an 8-core machine the parallel version is slower than running the loop on one core.

Explain what is happening at the hardware level, estimate how much slower it should be, and describe the fix. Then explain how you would confirm the diagnosis with measurement rather than by argument.

• Assume a typical x86 or ARM server: 64-byte cache lines, private L1/L2 per core, a shared L3, and a MESI-style coherence protocol.
• Be quantitative: use reference latencies for a cache hit versus a coherence miss.

Examples

The concrete scenario, with the numbers a measurement would show:

• counts is declared as int64_t counts[8] (or a Python/NumPy array, or a Java long[8]), so all eight slots occupy bytes 0 to 63 of a contiguous region: exactly one 64-byte cache line if the array starts on a line boundary, and two adjacent lines otherwise.
• Single-threaded loop: for i in range(10^8): counts[0] += 1 runs in ~0.1 s in C (about 1 ns per increment, an L1 hit plus a dependent add).
• Eight-threaded version with each thread doing 10^8 increments to its own slot: expected time ~0.1 s (perfect parallelism); observed ~1-3 s.
• After padding each slot to its own 64-byte line (alignas(64) per element, or a stride of 8 in the array), the eight-thread version takes ~0.1 s as expected.
• The interviewer may also present a struct with a read-mostly field and a hot write-mostly field next to each other, and a lock placed next to the data it protects; the same phenomenon.

Hints

1. The hardware does not track ownership per variable. What is the unit of ownership in a coherent cache?
2. When core A writes to a line that core B has cached, what must happen to B's copy before A's write can complete, and how long does that take compared with an L1 hit?
3. If all eight threads' variables share a line, how many cores are fighting for exclusive ownership of it, and how often?