Part 5 of 7 · 3 min read
False sharing
In plain words: When two cores each keep a copy of the same cache line, the hardware must keep the copies consistent. If one core writes to its copy, the other core's copy becomes out of date and must be dropped, and the next access there must fetch the line again. This protocol is cache coherence. It works automatically, and it is what makes shared variables behave correctly, but it is not free: a line written by one core and then read or written by another has to travel between the cores' caches.
This leads to a surprise. The unit of coherence is the whole line of 64 bytes, not a single variable. If two threads write two different variables that happen to sit on the same line, the hardware treats them as sharing, and the line bounces between the cores on every write, though the program shares nothing. This is false sharing.
The test has two threads, each incrementing its own counter 50 million times. In one version the two counters are 8 bytes apart, on the same line. In the other, 64 bytes of padding separate them, so that they lie on different lines. The increments are atomic (the hardware does each addition as one indivisible step, Level 4):
struct packed { volatile long a; volatile long b; }; /* same cache line */
struct padded { volatile long a; char pad[64]; volatile long b; }; /* different lines */
adjacent counters: 1.73 s padded counters: 0.32 s ratio 5.4
adjacent counters: 1.70 s padded counters: 0.33 s ratio 5.2
adjacent counters: 1.64 s padded counters: 0.33 s ratio 5.0
The padding made the program about 5 times faster, although it does exactly the same work. Neither counter is shared in the sense of the program's meaning. The cost comes from the line moving between the two cores.
The effect depends on the machine and on how the updates are done. In a test with plain (non-atomic) volatile increments, 200 million per thread, the two versions took 0.54 s and 0.52 s, a ratio of about 1.0 to 1.1, so the effect did not show on this machine. The lesson is not that every adjacent variable is slow, but that data written by different threads should be kept on separate cache lines when the writes are frequent, and that measuring is needed to know.
The remedies are to pad per-thread data to the line size, to align it (alignas(64) in C11), or to give each thread local variables and combine the results at the end, as in the parallel sum of page 2, whose per-thread result slots would suffer from false sharing only if they were written often during the work.
False sharing
False sharing is a loss of performance that occurs when threads on different cores write different variables that lie on the same cache line, so the coherence protocol keeps moving the line between the cores even though the threads share no data.
Example: two threads that update neighbouring long counters in one struct can run several times slower than if each counter had its own 64-byte line.
Check yourself: 1. What is the unit in which caches keep data? 2. Why were the padded counters faster? 3. Name two ways to avoid false sharing.