← Labscache-04Memory hierarchy●●○○

False sharing — independent data, shared line, shared cost

cache/04_false_sharing.cneeds: tools/bench.h, pthreads1 steps

0/1 steps

what this lab teaches

Coherence works on whole 64-byte lines. If two cores write two DIFFERENT variables that happen to share a line, each write must first pull the line away from the other core (request-for-ownership), and the line ping-pongs between them. The variables are logically independent; the hardware cannot tell. This lab has N threads each incrementing its OWN counter 100M times, with the counters (a) adjacent, (b) padded to one per line, and for comparison (c) all threads on the SAME counter.

evidence to leave with

Adjacent counters 6x (2 threads) and 12x (4 threads) slower than padded; false sharing as costly as true sharing

first, get the code

run this

$ git clone https://github.com/adit4443ya/debug_labs.git && cd debug_labs

then build it

run this

$ (cd cache && ./build.sh)   -> bin/04_false_sharing (-pthread)
$ Threads pin themselves to CPUs 2, 4, 6, 0: four DIFFERENT physical
$ P-cores (siblings are 2-3, 4-5, 6-7, 0-1). Pinning to siblings would
$ measure something else (shared L1).

walk it, one step at a time

run this

$ ./bin/04_false_sharing

what it printed on the machine that wrote this lab

configuration                                  ms ns/increment
1 thread, own counter (baseline)            886.6         8.87
2 threads, adjacent counters (FALSE)       5081.3        50.81
2 threads, padded counters                  872.6         8.73
2 threads, SAME counter (true sharing)     3636.8        36.37
4 threads, adjacent counters (FALSE)      10762.9       107.63
4 threads, padded counters                  885.6         8.86
4 threads, SAME counter (true sharing)     7728.1        77.28
sizeof(Plain)=8 sizeof(Padded)=64  &plain[1]-&plain[0]=8 bytes

how to read it

- Baseline: one atomic increment (lock xadd) is ~8.9 ns when the line stays in this core's L1. - Padded: 2 or 4 threads, each on its own line: 8.7-8.9 ns. Perfect scaling; the threads never interact. - Adjacent (false sharing): 50.8 ns with 2 threads, 107.6 ns with 4: 6x and 12x slower, for the SAME instructions on DIFFERENT data. Every increment waits for the line to travel from another core's cache (a cross-core transfer is ~40-100 ns), and the more cores, the longer the queue. - Same counter (true sharing): 36 and 77 ns. Note that false sharing was as bad or WORSE than genuinely sharing one counter. The hardware mechanism is identical (line ping-pong); the only difference is that the true-sharing version is at least doing what you asked.

how to find it in real code

- A scaling experiment: run the same per-thread work with 1 thread, then N threads on separate cores. If per-op cost rises with N although the threads "don't share anything", suspect a shared line. - `perf c2c record` / `perf c2c report` (needs root here) names the cache lines and the offsets within them that bounce between cores. - Typical culprits: arrays of per-thread counters or flags; a struct with one hot field written by thread A next to one written by thread B; a lock word next to the data it protects; the head and tail indices of a queue (concurrency lab 02). THE FIX (and its cost): alignas(64) on each concurrently-written hot variable, or std::hardware_destructive_interference_size (C++17; the value is a compiler/target constant and can differ between compilers, so many codebases hardcode 64 and static_assert it). Padding costs memory and cache footprint: pad what is WRITTEN concurrently, not everything. Data that is only read can share lines freely: readers don't bounce lines.

take it further

1. Change `cpus` to {2, 3, 4, 5} (SMT siblings share an L1) and rerun: false sharing gets cheaper (same L1) but the baseline gets slower (the siblings compete for one core's execution units). 2. Replace atomic_fetch_add with a plain `(*ctr)++` (a data race, but instructive): the line still bounces, and the count is wrong. 3. Spread the 4 counters 16 bytes apart instead of 8: still one line, still slow. Then 64: fixed. The threshold is the line, not proximity. ============================================================

read the source · cache/04_false_sharing.c

#include "../tools/bench.h"
#include <pthread.h>
#include <stdatomic.h>
#include <stdalign.h>
#define ITERS 100000000ull
typedef struct { atomic_uint_fast64_t v; } Plain;                                  /* 8 bytes: 8 of these share a line */
typedef struct { alignas(64) atomic_uint_fast64_t v; char pad[56]; } Padded;      /* one per line */
typedef struct { atomic_uint_fast64_t *ctr; int cpu; } Arg;
static void *worker(void *p) {
    Arg *a = (Arg *)p; bench_pin(a->cpu);
    for (uint64_t i = 0; i < ITERS; i++) atomic_fetch_add_explicit(a->ctr, 1, memory_order_relaxed);
    return NULL;
}
static double run(atomic_uint_fast64_t **ctrs, const int *cpus, int nthreads) {
    pthread_t th[8]; Arg args[8];
    uint64_t t0 = bench_ns();
    for (int i = 0; i < nthreads; i++) { args[i].ctr = ctrs[i]; args[i].cpu = cpus[i]; pthread_create(&th[i], NULL, worker, &args[i]); }
    for (int i = 0; i < nthreads; i++) pthread_join(th[i], NULL);
    return (double)(bench_ns() - t0) / 1e6;
}
int main(void) {
    static Plain plain[8]; static Padded padded[8]; static atomic_uint_fast64_t shared;
    const int cpus[4] = {2, 4, 6, 0};                    /* four different P-cores (siblings are 2-3, 4-5, 6-7, 0-1) */
    atomic_uint_fast64_t *c[4];
    printf("%-38s %10s %12s\n", "configuration", "ms", "ns/increment");
    c[0] = &plain[0].v;
    double ms1 = run(c, cpus, 1); printf("%-38s %10.1f %12.2f\n", "1 thread, own counter (baseline)", ms1, ms1 * 1e6 / ITERS);
    for (int n = 2; n <= 4; n += 2) {
        for (int i = 0; i < n; i++) c[i] = &plain[i].v;
        double ms = run(c, cpus, n); printf("%-38s %10.1f %12.2f\n", n == 2 ? "2 threads, adjacent counters (FALSE)" : "4 threads, adjacent counters (FALSE)", ms, ms * 1e6 / ITERS);
        for (int i = 0; i < n; i++) c[i] = &padded[i].v;
        ms = run(c, cpus, n); printf("%-38s %10.1f %12.2f\n", n == 2 ? "2 threads, padded counters" : "4 threads, padded counters", ms, ms * 1e6 / ITERS);
        for (int i = 0; i < n; i++) c[i] = &shared;
        ms = run(c, cpus, n); printf("%-38s %10.1f %12.2f\n", n == 2 ? "2 threads, SAME counter (true sharing)" : "4 threads, SAME counter (true sharing)", ms, ms * 1e6 / ITERS);
    }
    printf("sizeof(Plain)=%zu sizeof(Padded)=%zu  &plain[1]-&plain[0]=%td bytes\n", sizeof(Plain), sizeof(Padded), (char *)&plain[1] - (char *)&plain[0]);
    return 0;
}

◇

Finish the lab: write the evidence note

A lab is done when you can say what it showed on your machine — not when you have read it.