False sharing and cache lines

Key points

• CPUs move memory in cache lines of about 64 bytes. Two variables inside one line are a single unit to the hardware.
• When core 1 writes its own counter, the line is invalidated on core 2, which must re-fetch it before touching its own counter.
• Nothing is logically shared, so no lock can help. The cost is invisible in the code and shows up only as poor scaling.
• Pad hot per-thread fields into separate lines. That is exactly what LongAdder does with its striped cells.
• Adjacent array slots are the usual trap: counter[threadId] looks ideal and is the worst possible layout.

Example

import java.util.concurrent.atomic.AtomicLongArray;

public class Main {
    static final int THREADS = 4;
    static final int ITERATIONS = 2_000_000;

    public static void main(String[] args) throws InterruptedException {
        time(1); time(16);                       // warm the JIT up first
        long crowded = time(1);                  // slots 0,1,2,3: one 64-byte cache line
        long padded = time(16);                  // slots 0,16,32,48: one line each

        System.out.println("neighbouring slots : " + crowded + " ms");
        System.out.println("padded slots       : " + padded + " ms");
        System.out.println("same work, same threads, no lock - only the layout changed");
        System.out.println("LongAdder pads for you, which is why it wins under contention");
    }

    static long time(int stride) throws InterruptedException {
        AtomicLongArray cells = new AtomicLongArray(THREADS * stride);
        Thread[] ts = new Thread[THREADS];
        long start = System.nanoTime();
        for (int t = 0; t < THREADS; t++) {
            int slot = t * stride;               // every thread owns its own slot
            ts[t] = new Thread(() -> { for (int i = 0; i < ITERATIONS; i++) cells.incrementAndGet(slot); });
            ts[t].start();
        }
        for (Thread t : ts) t.join();
        return (System.nanoTime() - start) / 1_000_000;
    }
}

Give every hot counter its own cache line, or use LongAdder and stop thinking about it.