Parallelizing a hot loop across multiple threads is supposed to make things faster. Sometimes it does the opposite. Here's a benchmark that should be a clean win for parallelism, and isn't.
The benchmark
Eight threads. Each thread has its own counter: one slot in a shared array of longs. Each thread increments only its own slot, a billion times. They never write to each other's slots. There is no logical contention.
long[] counters = new long[8];
// Each thread i runs:
for (int j = 0; j < 1_000_000_000; j++) {
counters[threadIndex]++;
}On an 8-core machine, you'd expect this to run roughly 8x faster than a single thread doing the same total work. In practice, the parallel version can run 5–10x slower than the single-threaded version. Not marginally slower. Catastrophically slower.
The code is correct. The data is separate. The hardware is lying to you.
Cache lines and why they matter
CPUs don't move memory one byte at a time, or even one word at a time. They move it in chunks called cache lines, typically 64 bytes on x86 and ARM systems, though some architectures use 128. A cache line is the minimum unit of transfer between RAM and cache, and also the minimum unit of coherence between CPU cores.
A long in Java is 8 bytes. Eight longs in a contiguous array therefore occupy
exactly 64 bytes: one cache line. When all eight thread counters land in the same array,
they share a single cache line.
When Thread 0 increments counters[0], the CPU needs to write to that cache
line. To do that, it needs exclusive ownership of the cache line. That means
it sends an invalidation message to every other CPU core that holds a copy of that line.
Thread 1 increments counters[1]: same line, same process. Now Thread 0's
copy is invalidated, and Thread 1 holds the exclusive copy. This continues at billions of
operations per second, with all eight cores fighting over ownership of one 64-byte chunk
of memory.
The data isn't actually shared. But the hardware doesn't know that. The hardware only knows about cache lines.
The MESI protocol
The mechanism underlying this is the MESI protocol, a cache coherence protocol used by most modern CPUs. MESI stands for the four states a cache line can be in:
Modified means this core has the only copy and it's been written. All other cores' copies have been invalidated. Before any other core can read the value, this core must write back to RAM.
Exclusive means this core has the only copy and it's still clean. It can be written to without notifying anyone; the transition to Modified is local.
Shared means multiple cores have a copy and all copies are clean. Any core can read; any write requires first acquiring exclusive ownership, which means invalidating all other copies.
Invalid means this core's copy is stale. The next read triggers a cache miss and a fetch from the core that holds the current copy (or from RAM).
In the false sharing benchmark, every counter increment is a write. Each write on core N sends invalidation messages to the other seven cores, transitions those cores' cache line state to Invalid, and waits for an acknowledgment before proceeding. At a billion increments per thread, this is a billion invalidation round-trips. The inter-core communication latency (typically 10–50 ns depending on physical core proximity on the die) dominates the entire benchmark.
This is called false sharing: multiple threads appearing to contend over shared data when they aren't logically sharing anything. The sharing is an artifact of the physical layout in memory.
The fix: padding
The fix is to ensure that each counter lives on its own cache line, with no other thread's data sharing that line. In Java, the blunt approach is to pad each counter with enough dummy fields to consume the rest of a 64-byte cache line.
static final class PaddedCounter {
long value;
long p1, p2, p3, p4, p5, p6, p7; // 7 * 8 = 56 bytes of padding
}
PaddedCounter[] counters = new PaddedCounter[8];
Each PaddedCounter instance now occupies 64 bytes of object body (ignoring
the object header, which adds another 12–16 bytes and pushes the object to its own
cache line in practice). The counters no longer share a cache line. Thread 0 can write
to counters[0].value without touching the cache line any other thread cares
about.
Run the padded benchmark and the numbers flip: the parallel version is close to 8x faster than single-threaded, as expected.
Java 8 added the @Contended annotation (in the sun.misc package,
now jdk.internal.vm.annotation) to do this automatically. The JVM adds padding
around annotated fields or classes to prevent false sharing. It requires the JVM flag
-XX:-RestrictContended to use in application code (it's unrestricted in the
JDK's own internals). The LongAdder class in the standard library is a good
example of something that uses striping across cache lines internally to handle high
contention on a single logical counter.
Where this actually comes up
False sharing isn't just a microbenchmark pathology. It shows up in real systems when engineers lay out concurrent data structures without thinking about cache line boundaries.
High-frequency per-thread or per-CPU counters are the classic case: metrics, telemetry, work-stealing deque pointers. If you're building a task scheduler and each worker thread maintains a head and tail pointer in a shared structure, those pointers on the same cache line will cause false sharing under load.
Ring buffers are a well-documented case. The LMAX Disruptor, a high-performance inter-thread messaging library, was designed explicitly around cache line boundaries. The sequence number (the write cursor), the consumer gating sequences, and the ring buffer entries are all laid out to land on separate cache lines. The original Disruptor paper from 2011 describes the performance difference as dramatic: contended ring buffer implementations were losing most of their throughput to coherence traffic.
Lock-free data structures are another hotspot. The head and tail pointers of a concurrent queue are both frequently written by different threads. If they share a cache line, every enqueue invalidates the dequeue thread's copy and vice versa. Separating them is one of the first things a serious implementation does.
The bug is in the address
What makes false sharing unusual among performance bugs is that it's invisible in the logic. The algorithm is correct. The data is logically separate. The fix has nothing to do with the computation; it's purely about where in memory things live.
Profiling will eventually find it. CPU performance counters can measure cache line invalidations and coherence misses directly. Tools like Intel VTune, Linux perf with the right hardware events, or async-profiler with CPU sampling will show threads stalled on memory operations even though the code looks trivially simple.
The intuition to build is this: if you have multiple threads each writing frequently to their own piece of data, and that data is adjacent in memory, assume false sharing until you can prove otherwise. Cache lines don't care about your abstraction boundaries.
Back to writing