False sharing problem

What Is False Sharing?

False sharing occurs when multiple processor cores modify logically independent variables that happen to reside in the same cache line. This triggers cache coherence protocols (like MESI) to invalidate and transfer the line between cores, creating contention despite no actual data sharing.

Why it happens:

• Cache coherence operates at cache line granularity (typically 64 bytes)
• Compilers/allocators pack data structures densely
• Adjacent array elements or struct fields land in the same line
• Each core's write invalidates the line in other cores' caches

The critical insight: The hardware cannot tell that you're accessing different bytes. It only knows: "Someone wrote to this 64-byte block, so I must invalidate everyone else's copy."

The Mechanism: Cache Line Ping-Pong

Derivation from First Principles

Let's build up why this happens:

Step 1: Cache coherence granularity

• Memory is divided into blocks (cache lines) of size $L$ bytes (typically $L = 64$)
• Address $A$ maps to cache line $\lfloor A / L \rfloor$
• Two addresses $A_1, A_2$ share a line if: $\lfloor A_1 / L \rfloor = \lfloor A_2 / L \rfloor$

Step 2: MESI protocol constraint

• A line can be Modified in at most one cache
• Write to Modified line: local, fast (1-2 cycles)
• Write to Shared/Invalid line: must acquire exclusive ownership
  • Send invalidation to all other caches
  • Wait for acknowledgments
  • Transition to Modified
  • Cost: 50-200 cycles (remote cache access)

Step 3: False sharing scenario

Consider two cores accessing different variables:

• Core 0 writes to address $A_0$ (variable counter[0])
• Core 1 writes to address $A_1$ (variable counter[1])
• If $\lfloor A_0 / 64 \rfloor = \lfloor A_1 / 64 \rfloor$, they share a cache line

Timeline:

Time    Core 0                Core 1              Line State
0       Write counter[0]        -                   Modified in C0
1       -                       Write counter[1]    → Invalidate C0
                                    → Modified in C1
2       Write counter[0]        -                   → Invalidate C1
                                    → Modified in C0
3       -                       Write counter[1]    → Invalidate C0
                                    → Modified in C1
...     (ping-pong continues)

Cost per false sharing write: $T_{\text{false}} = T_{\text{coherence}} + T_{\text{write}} \approx 100-200 \text{ cycles}$

Compare to isolated write: $T_{\text{local}} = T_{\text{write}} \approx 1-2 \text{ cycles}$

Slowdown factor: $\text{Overhead} = \frac{T_{\text{false}}}{T_{\text{local}}} \approx 50-100\times$

Concrete Examples

The Solution: Cache Line Padding

Goal: Ensure each core's data occupies a separate cache line.

Common Mistakes

Detection and Measurement

How to detect false sharing:

1. Profiling tools:

   • Linux perf c2c (cache-to-cache): Shows which cache lines have high coherence traffic
   • Intel VTune: "Memory Access Analysis" highlights contended cache lines
   • AMD μProf: Cache line contention view

2. Performance counters:

   • Monitor MEM_LOAD_RETIRED.FB_HIT (load from fill buffer, sign of recent invalidation)
   • OFFCORE_RESPONSE.DEMAND_RFO.L3_MISS.REMOTE_HITM (remote cache hit-modified, false sharing signature)

3. Symptoms:

   • Code scales poorly (2cores slower than 1core per throughput)
   • High L3 cache miss rate despite good locality
   • CPU utilization low but no obvious blocking

Quantifying the cost:

Let $W$ = writes per core, $T_{\text{coh}}$ = coherence latency (fetch line from a remote cache), $T_{\text{local}}$ = local write latency.

Without false sharing — every write hits a line already in Modified state locally: $T_{\text{per-write}} = T_{\text{local}} \approx 1\text{-}2 \text{ cycles}$

With false sharing — in the worst case, every write finds the line stolen by another core, so it must pay the coherence penalty once to re-acquire it: $T_{\text{per-write}} = T_{\text{coh}} + T_{\text{local}} \approx 100\text{-}200 \text{ cycles}$

Key correction — the per-write penalty does NOT scale with core count. Each contended write incurs exactly one coherence miss (fetch the line back from whoever stole it), regardless of how many cores participate in the ping-pong. Adding more cores makes it more likely your line gets stolen before your next write (raising the probability of paying the penalty toward 1), but it never makes a single write pay the penalty multiple times.

Per-write slowdown factor: $S = \frac{T_{\text{coh}} + T_{\text{local}}}{T_{\text{local}}} \approx \frac{T_{\text{coh}}}{T_{\text{local}}} \approx 100\times$

This is independent of $N$. So the realistic worst-case slowdown is bounded by the ratio $T_{\text{coh}}/T_{\text{local}}$ (~50–100×), not by $N \times (T_{\text{coh}}/T_{\text{local}})$.

Total time (worst case, every write contended): $T_{\text{total}} = W \times (T_{\text{coh}} + T_{\text{local}}) \quad\text{vs.}\quad W \times T_{\text{local}}$

The Big Picture: When to Worry

High risk scenarios:

• Per-thread counters/statistics (arrays indexed by thread ID)
• Shared data structures with per-core fields (like the ThreadData struct)
• Lock-free data structures with adjacent metadata
• Producer-consumer ques where head/tail pointers are close

Low risk scenarios:

• Read-only data (no invalidations)
• True data sharing (cores need to see each other's updates anyway)
• Single-writer patterns (one core modifies, others read)

Connections

• Cache coherence protocols — MESI/MOESI are the mechanisms that cause false sharing overhead
• Cache line size and alignment — Understanding64-byte granularity is foundational
• Lock-free data structures — Often vulnerable to false sharing in metadata
• NUMA architectures — False sharing is even more expensive cross-socket
• Memory allocators — jemalloc/tcmalloc can reduce false sharing with per-thread arenas
• Atomic operations — Provide correctness but don't prevent false sharing
• Multicore scaling — False sharing is a major barrier to linear speedup

#flashcards/hardware

What is false sharing? :: When multiple cores write to logically independent variables that reside in the same cache line, causing unnecessary cache coherence traffic and performance degradation.

Concept Map

Hinglish (regional understanding)

Hinglish (regional understanding)