mechanical sympathy

the picture

"mechanical sympathy" is a racing driver's phrase (Jackie Stewart's): you drive better when you understand how the car works. for code, the car is the memory hierarchy.

think of a library. the book on your desk is the L1 cache (grab it instantly). the shelf behind you is L2 (stand up, turn around). the stacks downstairs are main memory (a walk). and the librarian is clever: when you take a book, they bring the whole shelf section it was in (a cache line), and if you keep taking books left to right, they start fetching the next sections before you ask (prefetching). read the library in order and you barely wait. pick books at random and you spend your day on the stairs.

how far away is memory?

the honest way to measure latency is to make every load depend on the previous one, so the CPU can't overlap them: build a random cycle through an array (next[i] holds the index to visit after i), and follow it. the time per step is the time for one trip to wherever that data lives.

int p = 0;
for (int i = 0; i < steps; i++) p = next[p];   // each load needs the result of the last one

same instruction, same loop: 1.5 ns when the array fits in L1, 124 ns when it doesn't fit anywhere. everything else in this chapter is a consequence of that curve.

walking memory: in order or not

a 4096 × 4096 int grid (64 MB, far bigger than any cache), summed three ways. measured with JMH, reported per element:

15 times slower for swapping two loop variables. the random order is the interesting middle: every access misses, but the addresses come from an index array, so the CPU can have many misses in flight at once. the pointer chase above couldn't, because each address depended on the last load. "how many misses can overlap" is a big part of why some cache-unfriendly code is only slow and some is catastrophic.

why arrays beat linked lists

the same million numbers, summed from different containers:

two lessons in one chart. first, the textbook one: following pointers is slower than walking an array, and a LinkedList is pointers all the way down (node → next node, node → value). second, the one people miss: freshly built collections are often laid out in order in memory, because the allocator hands out addresses one after another (TLABs), so even a LinkedList gets some prefetching help. shuffle the elements so the references point all over the heap, and both lists fall off a cliff. a long-lived, much-modified collection in a real app looks like the shuffled rows. (ArrayList vs LinkedList has the rest.)

this is also what valhalla is about: letting List<Point> store the points' fields inline, like an int[], instead of an array of references to objects scattered around the heap.

false sharing

caches work in lines, and so does keeping caches coherent between cores. when one core writes to a line, every other core's copy of that line is invalidated. normally that's how threads see each other's writes. but it happens per line, not per variable:

here's the experiment, small enough to run:

import java.util.concurrent.atomic.AtomicLongArray;
 
// two threads, two counters. only the distance between the counters changes.
static long run(int slotA, int slotB) throws InterruptedException {
    AtomicLongArray a = new AtomicLongArray(64);
    Runnable inc1 = () -> { for (int k = 0; k < 50_000_000; k++) a.set(slotA, a.get(slotA) + 1); };
    Runnable inc2 = () -> { for (int k = 0; k < 50_000_000; k++) a.set(slotB, a.get(slotB) + 1); };
    Thread t1 = new Thread(inc1), t2 = new Thread(inc2);
    long start = System.nanoTime();
    t1.start(); t2.start(); t1.join(); t2.join();
    return (System.nanoTime() - start) / 1_000_000;
}
 
void main() throws InterruptedException {
    run(16, 17); run(16, 48);                       // warm up the JIT
    for (int i = 0; i < 3; i++) {
        IO.println("8 bytes apart: " + run(16, 17) + " ms    256 bytes apart: " + run(16, 48) + " ms");
    }
}

one run printed:

8 bytes apart: 409 ms    256 bytes apart: 162 ms
8 bytes apart: 178 ms    256 bytes apart: 138 ms
8 bytes apart: 423 ms    256 bytes apart: 126 ms

see the middle line? each run allocates a new array, and that time it happened to land so that slots 16 and 17 sat on different lines. to pin it down i swept a pair of adjacent counters across 16 positions inside one array: exactly 2 positions out of 16 were fast (89 to 125 ms), 8 slots apart, the rest took 289 to 346 ms. that's a 64-byte line. (macOS reports hw.cachelinesize as 128 on this chip, and the JVM's own padding default, ContendedPaddingWidth, is 128 too, which is the safe choice across CPUs.)

the fixes, roughly in order of preference:

• don't share hot counters at all. give each thread its own and combine at the end, or use a LongAdder, which spreads a counter over padded cells for exactly this reason (atomics and CAS).
• put the hot fields in separate objects, allocated at different times, or pad them: 128 bytes between two values that different threads write.
• @Contended does the padding for you in the JDK's own classes (Thread, ConcurrentHashMap's counter cells, LongAdder's Cell). it's internal (jdk.internal.vm.annotation): user code needs --add-exports and -XX:-RestrictContended, so it's rarely worth it outside a library.

branch prediction

a modern core is a pipeline dozens of instructions deep. at an if, it can't wait to find out which way to go, so it guesses and keeps going; a wrong guess throws that work away. guesses are excellent when the branch follows a pattern, and a coin flip when it doesn't.

the classic test: sum the values ≥ 128 in an array of random bytes, once unsorted and once sorted (where the branch goes "no" for the first half and "yes" for the second):

almost 2× here, honestly measured. that's far less dramatic than the famous stack overflow question about exactly this loop, and it can be zero: C2 can replace a simple if like this with a branch-free conditional select, and when it does, sorted and unsorted run at the same speed. whether it does depends on the JVM version, the CPU and how the loop is shaped. which is the real lesson: measure your case, don't assume the textbook's.