False sharing

Deep dive

Decision table

Code

use std::sync::atomic::{AtomicU64, Ordering::Relaxed};
use std::thread;
use std::time::Instant;

/// 128 B: covers 64-byte lines plus Intel adjacent-line prefetch, and Apple 128-byte lines.
#[repr(align(128))]
pub struct CachePadded<T>(pub T);

fn hammer<C: Sync>(cells: &[C], get: impl Fn(&C) -> &AtomicU64 + Sync) -> f64 {
    let t = Instant::now();
    thread::scope(|s| {
        for c in cells {
            let get = &get;
            s.spawn(move || for _ in 0..10_000_000 { get(c).fetch_add(1, Relaxed); });
        }
    });
    t.elapsed().as_secs_f64()
}

fn main() {
    let n = 4;
    let packed: Vec<AtomicU64> = (0..n).map(|_| AtomicU64::new(0)).collect(); // all in one line
    let padded: Vec<CachePadded<AtomicU64>> = (0..n).map(|_| CachePadded(AtomicU64::new(0))).collect();
    println!("packed {:.2}s", hammer(&packed, |c| c));
    println!("padded {:.2}s", hammer(&padded, |c| &c.0)); // typically several to tens of times faster
}

// Struct layout: separate fields by writer.
pub struct Queue {
    pub head: CachePadded<AtomicU64>, // written by the consumer
    pub tail: CachePadded<AtomicU64>, // written by the producer
    // read-only after construction (capacity, buffer pointer) can share a line with either
}

C, C++, Java, Go equivalents:

struct counter { _Alignas(128) _Atomic unsigned long v; };          /* C11 */
// C++17: alignas(std::hardware_destructive_interference_size) std::atomic<long> v;  (GCC: 64 on x86, ABI-unstable)
// Linux kernel: struct foo { ... } ____cacheline_aligned_in_smp;
// Java: @jdk.internal.vm.annotation.Contended (needs -XX:-RestrictContended outside the JDK; pads 128 B)
// Go: _ cpu.CacheLinePad  (golang.org/x/sys/cpu)

Efficiency

• Cost: an ownership transfer of a shared line is order of 50-100 ns on one socket, more across sockets, paid on every write by a different core. Padding costs 128 B per item. Bound: cache-coherence latency, not compute or bandwidth.
• Levers:
  • pad per-thread items to 128 B — padded vs packed counters, typically several to tens of times faster (Code above) — per-thread or per-core slots
  • split fields by writer, one line per writer — no ping-pong between producer and consumer indices — queues, rings
  • contiguous chunks per thread instead of interleaved elements — only chunk edges share lines — data-parallel loops
  • accumulate thread-locally, publish rarely (sharded counters) — removes the shared write — statistics
  • do not pad large arrays — avoids trading contention for cache misses (1M slots × 128 B = 128 MB) — many small objects
• Naive → standard → state of the art:
  • packed per-thread counters · every increment pulls the line, order of 50-100 ns
  • cache-line padded cells · line stays local, order of ns
  • thread-local batches or per-CPU data · order of 1 ns per update

Detecting it

• Linux: perf c2c record -- ./app then perf c2c report: lines with many HITM (load hit a modified line in another core) and the offsets accessed within them.
• Intel VTune "Memory Access" analysis, AMD uProf; on macOS, Instruments counters for L1/L2 misses.
• Quick test: pad the suspected struct and re-measure; if throughput changes a lot with thread count, it was contention.

Pitfalls

• #[repr(align(128))] on a wrapper but storing Vec<AtomicU64> elsewhere: alignment applies to the type you actually store.
• C++ before C++17: new ignores over-alignment; use aligned_alloc or C++17's aligned new.
• std::hardware_destructive_interference_size is a compile-time guess (64 on GCC/x86) and does not cover the 128-byte prefetch effect.
• Thread-local accumulators allocated together in one Vec without padding: the same bug, one level up.
• Padding every element of a large array (e.g. 1M slots × 128 B = 128 MB) trades contention for cache misses; pad only per-thread or per-core items.
• Sharing that is true (all threads increment one counter) is not fixed by padding; use sharded counters.
• Measuring on one core or with SMT siblings hides the cost: siblings share L1, no line transfer.

Implementations

Sources

• Intel, Intel 64 and IA-32 Architectures Optimization Reference Manual (false sharing, adjacent cache line prefetch).
• Josep Torrellas, Monica S. Lam, John L. Hennessy, False Sharing and Spatial Locality in Multiprocessor Caches, IEEE Transactions on Computers, 1994. paper
• Linux perf-c2c(1) manual page (cache-to-cache contention analysis). docs
• crossbeam-utils CachePadded documentation (per-architecture padding choices). docs · code