Cache Lines and False Sharing — Slowed Down by Your Neighbour

In one line

The cache moves in 64-byte line units and cores pass ownership back and forth in those line units, so even different variables, if they sit on the same line, degrade each other's performance.

Why this was needed

In a multicore system, several cores can each load the same memory into their own caches. If one core changes a value and another core keeps seeing the old value, the program falls apart. So the hardware runs a cache coherence protocol (of the MESI family). For a core to modify a line, it must invalidate the other cores' copies and obtain exclusive ownership.

The important fact here is that the unit of this ownership contest is not the variable but the cache line.

How it works

Suppose thread A diligently increments counter a, and thread B diligently increments counter b. They are entirely different variables and need no lock. But if a and b are declared side by side in a struct and end up in the same 64-byte line, then every time A writes, that line is invalidated in B's cache, and every time B writes, it is invalidated in A's. Logically there is no sharing, but at the hardware level they are constantly taking it from each other. This is called false sharing.

The symptom is characteristic. You add threads, but throughput does not grow, or even falls. No matter how hard you search for lock contention, none turns up. That is because there are no locks.

The response is simple. Place the data that each core writes on different cache lines. Add padding to the struct, or align array elements to a multiple of the line size.

There is one more trap of a similar kind. It is the split lock. If the operand of an atomic operation straddles two cache lines, the CPU cannot use the fast coherence path and has to take an external bus lock. It takes more than 800 cycles, and unrelated cores also stall in the meantime. The Linux kernel provides a feature to detect this, and the default value of the boot parameter split_lock_detect is warn. If the kernel log is printing related warnings, it is likely to be a real performance problem.

What you see in the field

High-performance queues, counter arrays, and per-thread statistics collectors are the typical victims. Particularly dangerous is an array designed with "each thread writes only to its own slot, so no lock is needed." If the slot size is 8 bytes, eight slots fit in one line, and eight threads fight over one line.

Conversely, you can also exploit this principle. If you gather fields that are read together onto one line, a single miss fetches them all. Put together values that are used together read-only, and separate values that different cores write. The rule boils down to this single line.

What you will do in the next lab

You measure this line-by-line behavior in time. You sweep an array with various strides to see how read cost differs depending on how much of each line is used and discarded, and traverse the same matrix in row-major and column-major order to see how many times the access order alone widens the gap. Finally you split the traversal into pieces to reverse that loss.