Cache Coherence, False Sharing, Branch Prediction, and NUMA

CPU Caches and Locality treated one core and its caches. This lesson adds the effects that appear when several cores share memory, plus two other hardware features that decide how fast a loop runs: the branch predictor and the memory layout of multi-socket machines. After it, a reader can explain why two threads writing different variables can slow each other down, and fix it.

Cache coherence and MESI

Each core has a private L1 and L2 cache, so two cores can hold copies of the same line. Cache coherence is the guarantee that a write by one core is eventually seen by every other core and that all cores agree on the order of writes to a single line. x86 and ARM implement it in hardware with variants of the MESI protocol. Each cached line is in one of four states:

A core that wants to write a line it holds in S or I sends a request that invalidates every other copy, and waits for the line in M. The unit of ownership is the whole 64-byte line, not the variable.

Example 1: a MESI model with two cores

The program models one line and two cores. Each operation prints the resulting states and the messages sent between caches.

import java.util.Arrays;

public class MesiModel {
    enum State { M, E, S, I }

    static final State[] state = { State.I, State.I };
    static int messages;

    static void read(int core) {
        int other = 1 - core;
        String note;
        if (state[core] != State.I) {
            note = "hit";
        } else if (state[other] == State.I) {
            state[core] = State.E;
            messages++;
            note = "miss, loaded from memory";
        } else {
            state[other] = State.S;               // M writes back, E downgrades
            state[core] = State.S;
            messages++;
            note = "miss, copied from core " + other;
        }
        print("core " + core + " read ", note);
    }

    static void write(int core) {
        int other = 1 - core;
        String note;
        if (state[core] == State.M || state[core] == State.E) {
            note = "hit, no message";
        } else {
            if (state[other] != State.I) {
                state[other] = State.I;
                note = "invalidate core " + other;
            } else {
                note = "read for ownership";
            }
            messages++;
        }
        state[core] = State.M;
        print("core " + core + " write", note);
    }

    static void print(String op, String note) {
        System.out.printf("%-12s %-8s %s%n", op, Arrays.toString(state), note);
    }

    public static void main(String[] args) {
        read(0);
        write(0);
        write(0);
        read(1);
        write(1);
        write(0);
        System.out.println("messages = " + messages);
    }
}

core 0 read  [E, I]   miss, loaded from memory
core 0 write [M, I]   hit, no message
core 0 write [M, I]   hit, no message
core 1 read  [S, S]   miss, copied from core 0
core 1 write [I, M]   invalidate core 0
core 0 write [M, I]   invalidate core 1
messages = 4

A line used by one core stays in E or M and costs nothing after the first load. Once two cores write it in turn, every write sends a message and waits for the other core to give the line up. That round trip costs tens of nanoseconds, comparable to an L3 access.

Store buffers and invalidation queues

Waiting for invalidations on every write would stall the core. Real cores therefore put each store into a store buffer, a small per-core queue, and keep executing. The store reaches the cache (and becomes visible to other cores) later, when the line is owned. A load by the same core checks its own store buffer first, so the core always sees its own writes.

The receiving side has a similar shortcut on some CPUs: an invalidation queue acknowledges an invalidation at once and applies it later, so a core can read a stale copy for a short time. x86 has store buffers but behaves as if invalidations are applied immediately. ARM and POWER expose both effects.

The consequence: a store followed by a load of a different variable can appear, to another core, to happen in the opposite order. Coherence still holds per line; the order across different lines is what changes. Visibility and Reordering shows how Java code observes this and which language rules prevent it.

Example 2: store-buffer reordering in a model

Two threads run x = 1; r1 = y and y = 1; r2 = x. With no buffering, at least one store happens before both loads, so r1 == 0 && r2 == 0 is impossible. The program enumerates every interleaving twice: once with stores going straight to memory, once with each store waiting in a buffer until a separate drain step.

import java.util.TreeSet;

public class StoreBufferModel {
    // events per thread: 'S' store own variable, 'D' drain buffer, 'L' load other variable
    static void explore(String t0, String t1, int i0, int i1,
                        int[] mem, int[] buf, int[] reg, TreeSet<String> out) {
        if (i0 == t0.length() && i1 == t1.length()) {
            out.add("r1=" + reg[0] + " r2=" + reg[1]);
            return;
        }
        if (i0 < t0.length()) step(0, t0, t1, i0 + 1, i1, t0.charAt(i0), mem, buf, reg, out);
        if (i1 < t1.length()) step(1, t0, t1, i0, i1 + 1, t1.charAt(i1), mem, buf, reg, out);
    }

    static void step(int t, String t0, String t1, int i0, int i1, char ev,
                     int[] mem, int[] buf, int[] reg, TreeSet<String> out) {
        int[] m = mem.clone(), b = buf.clone(), r = reg.clone();
        int own = t, other = 1 - t;            // thread 0 owns x (index 0), thread 1 owns y
        switch (ev) {
            case 'W' -> m[own] = 1;                        // store straight to memory
            case 'S' -> b[t] = 1;                          // store into own buffer
            case 'D' -> { if (b[t] == 1) m[own] = 1; }     // buffer drains to memory
            case 'L' -> r[t] = m[other];                   // load from memory
        }
        explore(t0, t1, i0, i1, m, b, r, out);
    }

    public static void main(String[] args) {
        TreeSet<String> direct = new TreeSet<>(), buffered = new TreeSet<>();
        explore("WL", "WL", 0, 0, new int[2], new int[2], new int[2], direct);
        for (String a : new String[] {"SDL", "SLD"})
            for (String b : new String[] {"SDL", "SLD"})
                explore(a, b, 0, 0, new int[2], new int[2], new int[2], buffered);
        System.out.println("no store buffer:   " + direct);
        System.out.println("with store buffer: " + buffered);
    }
}

no store buffer:   [r1=0 r2=1, r1=1 r2=0, r1=1 r2=1]
with store buffer: [r1=0 r2=0, r1=0 r2=1, r1=1 r2=0, r1=1 r2=1]

With buffers, both loads can run while both stores still sit in the buffers, so r1=0 r2=0 appears. This is store-load reordering, the one reordering x86 performs. A full fence instruction (such as mfence or a lock-prefixed instruction on x86) makes the core wait until its store buffer drains before later loads run. Java emits such a fence for volatile writes, as the memory model section explains.

False sharing

False sharing happens when two threads write different variables that live on the same cache line. The program logic shares nothing, but the hardware shares the line, so each write invalidates the other core's copy, as in the last two steps of Example 1. The variables can be two fields of one object, two neighbouring array elements, or the end of one object and the start of the next.

Example 3: counting line transfers for two counters

This model gives each of two cores its own counter and lets them increment in turn. It counts how often a write must take the line from the other core, once with both counters on one line and once on separate lines.

public class FalseSharingModel {
    static long transfers(int lineOfA, int lineOfB, int increments) {
        int[] owner = { -1, -1 };              // which core holds each line in M
        long moves = 0;
        for (int i = 0; i < increments; i++) {
            for (int core = 0; core < 2; core++) {
                int line = core == 0 ? lineOfA : lineOfB;
                if (owner[line] != core) {
                    if (owner[line] != -1) moves++;   // taken from the other core
                    owner[line] = core;
                }
            }
        }
        return moves;
    }

    public static void main(String[] args) {
        int n = 1_000_000;
        System.out.println("same line:      transfers = " + transfers(0, 0, n));
        System.out.println("separate lines: transfers = " + transfers(0, 1, n));
    }
}

same line:      transfers = 1999999
separate lines: transfers = 0

On one line almost every increment moves the line between cores. On separate lines each core keeps its line in M and no write leaves the core. Real threads do not alternate exactly, so the real number of transfers is lower, but it grows with the write rate of both threads.

Example 4: unpadded and padded counters with real threads

Each thread increments its own volatile long 50 million times. In Unpadded the two fields sit next to each other in one object. In Padded a superclass of eight unused long fields (64 bytes) separates them. The JVM may reorder fields within one class but keeps superclass fields before subclass fields, so the class hierarchy keeps the padding in place.

public class PaddedCounters {
    static final class Unpadded {
        volatile long a;
        volatile long b;
    }

    static class A { volatile long a; }
    static class PadAB extends A { long p1, p2, p3, p4, p5, p6, p7, p8; }
    static final class Padded extends PadAB { volatile long b; }

    static final int N = 50_000_000;

    static void runPair(Runnable first, Runnable second) throws InterruptedException {
        Thread t1 = new Thread(first), t2 = new Thread(second);
        t1.start(); t2.start();
        t1.join(); t2.join();
    }

    public static void main(String[] args) throws InterruptedException {
        Unpadded u = new Unpadded();
        runPair(() -> { for (int i = 0; i < N; i++) u.a++; },
                () -> { for (int i = 0; i < N; i++) u.b++; });

        Padded p = new Padded();
        runPair(() -> { for (int i = 0; i < N; i++) p.a++; },
                () -> { for (int i = 0; i < N; i++) p.b++; });

        System.out.println("unpadded totals correct: " + (u.a == N && u.b == N));
        System.out.println("padded totals correct:   " + (p.a == N && p.b == N));
    }
}

unpadded totals correct: true
padded totals correct:   true

Both versions are correct, because each field has one writer (u.a++ on a volatile is safe only for that reason). The difference is speed. On the 4-core Xeon used for this lesson, the unpadded pair took 1.8 to 2.4 seconds and the padded pair 0.55 to 0.8 seconds, about three times faster for the same work. The exact factor depends on the CPU and on whether the two threads land on cores that share an L2 cache.

Padding has costs: every padded object uses more memory, and 64 bytes is not always enough. Some Intel CPUs prefetch pairs of adjacent lines, which is why JDK and library code often pads with 128 bytes. The lock-free queue in Lock-Free Queues applies the same hierarchy technique to its head and tail indices.

Example 5: @Contended

The JDK has an annotation that asks the JVM to add the padding itself: @jdk.internal.vm.annotation.Contended. The JDK uses it on the cells of LongAdder (Striped64.Cell) and on ConcurrentHashMap.CounterCell. Two restrictions apply to application code:

• The package jdk.internal.vm.annotation is not exported, so javac needs --add-exports java.base/jdk.internal.vm.annotation=ALL-UNNAMED.
• The JVM flag RestrictContended is true by default (checked with -XX:+PrintFlagsFinal on JDK 25), which makes the JVM ignore the annotation outside the JDK. Running with -XX:-RestrictContended turns it on.

The example checker compiles with plain javac and cannot pass --add-exports, so this block is not run by it. It uses JOL (Java Object Layout, a library that prints field offsets) to show the effect.

import jdk.internal.vm.annotation.Contended;
import org.openjdk.jol.info.ClassLayout;

public class ContendedLayout {
    static final class Counters {
        @Contended volatile long a;
        @Contended volatile long b;
    }

    public static void main(String[] args) {
        System.out.println(ClassLayout.parseClass(Counters.class).toPrintable());
    }
}

Commands, with the JOL jar in the current directory:

javac --add-exports java.base/jdk.internal.vm.annotation=ALL-UNNAMED -cp jol-core-0.17.jar ContendedLayout.java
java -XX:-RestrictContended -cp jol-core-0.17.jar:. ContendedLayout

Representative output on JDK 25 (x86-64, compressed class pointers), trimmed to the field lines:

 12 132        (alignment/padding gap)
144   8   long Counters.a                N/A
152 128        (alignment/padding gap)
280   8   long Counters.b                N/A
Instance size: 288 bytes

Without -XX:-RestrictContended the same class is 32 bytes with a at offset 16 and b at 24, on one line. The padding width comes from -XX:ContendedPaddingWidth, 128 bytes by default. Fields annotated with the same group name, @Contended("group"), are padded as a block and stay together.

Branch prediction

A core runs instructions in a pipeline: it fetches and starts later instructions while earlier ones finish. At a conditional branch it does not yet know which way to go, so a branch predictor guesses from the branch's history and continues on the guessed path. A correct guess costs nothing. A wrong guess (a misprediction) discards the work done on the wrong path, about 15 to 20 cycles on current x86 cores. Branches that follow a pattern are predicted almost perfectly; branches on random data are wrong about half the time.

Example 6: sorted and unsorted data in a predictor model

The model is a 2-bit saturating counter, a common basic predictor: a counter from 0 to 3 predicts "taken" when it is 2 or more, and moves one step toward each actual outcome. The loop sums values of at least 128, once over random bytes and once over the same values sorted.

import java.util.Arrays;
import java.util.Random;

public class BranchModel {
    static long mispredictions;

    static long sumLarge(int[] data) {
        int counter = 0;
        long sum = 0;
        mispredictions = 0;
        for (int v : data) {
            boolean taken = v >= 128;
            boolean predicted = counter >= 2;
            if (taken != predicted) mispredictions++;
            counter = taken ? Math.min(3, counter + 1) : Math.max(0, counter - 1);
            if (taken) sum += v;
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] data = new int[1 << 20];
        Random rnd = new Random(1);
        for (int i = 0; i < data.length; i++) data[i] = rnd.nextInt(256);
        int[] sorted = data.clone();
        Arrays.sort(sorted);

        long s1 = sumLarge(data);
        long m1 = mispredictions;
        long s2 = sumLarge(sorted);
        long m2 = mispredictions;
        System.out.println("same sum: " + (s1 == s2));
        System.out.println("unsorted mispredictions: " + m1);
        System.out.println("sorted mispredictions:   " + m2);
    }
}

same sum: true
unsorted mispredictions: 523804
sorted mispredictions:   2

On random data the model mispredicts about half of the 1,048,576 branches. On sorted data the branch is "not taken" for the first half and "taken" for the second, so the counter is wrong only twice at the switch. Real predictors use longer history and are more accurate than this model, but random data defeats every predictor. A plain Java loop like sumLarge without the model code, run 20 times over the same arrays on the lesson's machine, took about 115 ms unsorted and about 20 ms sorted.

Example 7: branchless code

A loop can avoid the branch by computing a mask. For v in 0 to 255, (v - 128) >> 31 is -1 (all bits set) when v < 128 and 0 otherwise, because the arithmetic shift copies the sign bit. v & ~mask is then v or 0, with no conditional jump.

import java.util.Arrays;
import java.util.Random;

public class Branchless {
    static long withBranch(int[] data) {
        long sum = 0;
        for (int v : data) if (v >= 128) sum += v;
        return sum;
    }

    static long branchless(int[] data) {
        long sum = 0;
        for (int v : data) {
            int mask = (v - 128) >> 31;            // -1 if v < 128, else 0
            sum += v & ~mask;
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] data = new int[1 << 20];
        Random rnd = new Random(1);
        for (int i = 0; i < data.length; i++) data[i] = rnd.nextInt(256);
        int[] sorted = data.clone();
        Arrays.sort(sorted);

        System.out.println("mask(5) = " + ((5 - 128) >> 31) + ", mask(200) = " + ((200 - 128) >> 31));
        System.out.println("unsorted equal: " + (withBranch(data) == branchless(data)));
        System.out.println("sorted equal:   " + (withBranch(sorted) == branchless(sorted)));
        System.out.println("sum = " + branchless(data));
    }
}

mask(5) = -1, mask(200) = 0
unsorted equal: true
sorted equal:   true
sum = 100333179

The branchless version does the same work for every element, so its speed does not depend on the data. On the lesson's machine it ran in about 2 ms for 20 passes on both arrays, faster than the branching loop even on sorted data. A loop without branches is also a candidate for SIMD (vector) instructions, which the JIT compiler can use to process several elements per instruction. The JIT can make some branches branchless on its own (a conditional move, cmov on x86) when profiling shows them unpredictable, so the source-level rewrite pays off only where a profiler shows mispredictions. Branchless code is harder to read and can be slower when the branch is predictable and skips expensive work.

NUMA

On a machine with two or more CPU sockets, each socket has its own memory controller and DRAM. A core reaches memory on its own socket (local) faster than memory on another socket (remote), which goes over the link between sockets. This design is NUMA (non-uniform memory access), and each socket with its memory is a NUMA node. Remote access typically adds tens of nanoseconds and has lower bandwidth. Cache-line transfers between cores on different sockets (Example 1) are also slower than within one socket.

Linux allocates a page on the node of the thread that first touches it, so memory written by one thread and read by threads on another socket ends up remote. Latency-sensitive services are often pinned to one node for that reason. The machine used for this lesson has a single node.

Example 8: context switches

A context switch happens when the OS stops one thread on a core and runs another. The kernel saves and restores registers (a few microseconds of direct cost), and the new thread starts with caches and TLB entries that belong to the old one, which often costs more than the switch itself. A switch is voluntary when the thread blocks (sleep, lock wait, I/O) and involuntary when the scheduler preempts it. Linux counts both per thread in /proc/thread-self/status.

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;

public class ContextSwitches {
    static long voluntary() throws IOException {
        for (String line : Files.readAllLines(Path.of("/proc/thread-self/status"))) {
            if (line.startsWith("voluntary_ctxt_switches:")) {
                return Long.parseLong(line.split("\\s+")[1]);
            }
        }
        return -1;
    }

    public static void main(String[] args) throws Exception {
        long before = voluntary();
        for (int i = 0; i < 20; i++) Thread.sleep(1);
        long afterSleep = voluntary();

        long spin = 0;
        for (int i = 0; i < 1_000; i++) spin += i;
        long afterSpin = voluntary();

        System.out.println("counter found: " + (before >= 0));
        System.out.println("sleeps switched at least 20 times: " + (afterSleep - before >= 20));
        System.out.println("short spin loop switches: " + (afterSpin - afterSleep) + ", spin = " + spin);
    }
}

counter found: true
sleeps switched at least 20 times: true
short spin loop switches: 0, spin = 499500

Each Thread.sleep blocks the thread, so the kernel switches it off the core every time. The short loop never blocks and causes no voluntary switch. This is the trade-off behind busy-spinning in low-latency code: a spinning thread keeps its core and its caches but burns the core, while a blocking thread frees the core but pays a switch and cold caches when it wakes. A main thread that is preempted during the spin would show an involuntary switch, which is why the program reads only the voluntary counter.

Interview points

• MESI tracks each cache line as Modified, Exclusive, Shared, or Invalid; a write needs the line in M, which invalidates other copies.
• Coherence is per line; ordering between different lines is what store buffers and invalidation queues relax.
• x86 allows only store-load reordering, caused by store buffers; a volatile write in Java adds a fence that drains the buffer.
• False sharing is contention on a line, not on a variable; fix it by padding (64 or 128 bytes) or by giving each thread its own data.
• Field order inside a class is chosen by the JVM, so manual padding uses a class hierarchy.
• @Contended needs --add-exports at compile time and -XX:-RestrictContended at run time outside the JDK; LongAdder uses it internally.
• Unpredictable branches cost about 15 to 20 cycles each when mispredicted; sorting the data or branchless code removes the cost.
• On NUMA machines, memory is allocated on the node of the first touching thread; pin threads and memory to one node for consistent latency.
• A context switch costs microseconds directly and more through cold caches; spinning avoids it at the cost of a busy core.

Summary

• Writes to one line from two cores send an invalidation and a line transfer on every switch of writer.
• A store buffer lets a later load complete before an earlier store is visible, which produces r1=0 r2=0 in the store-buffer test.
• Two volatile counters in one object ran about three times slower than padded ones on a 4-core Xeon.
• @Contended padded a two-field class from 32 to 288 bytes with ContendedPaddingWidth at its default 128.
• A 2-bit predictor model mispredicted 523,804 of 1,048,576 random branches and 2 sorted ones.
• UseNUMA is off by default; Linux places pages on the first-touching thread's node.
• Thread.sleep causes a voluntary context switch on every call.