False Sharing, Visualized

Recently I’ve been going through the Systems Performance book and it described an interesting situation that I wanted to visualize. A simple program writes to a field in memory, say a counter, from two threads. It gets slower the more threads you add, even though they don’t contend for the same spot in memory.

type counters struct {
    a atomic.Uint64
    b atomic.Uint64
}
 
var c counters
go func() { for range n { c.a.Add(1) } }()
go func() { for range n { c.b.Add(1) } }()

Two million increments in total, spread across more goroutines:

Each goroutine gets its own counter, so the four goroutine case is four counters in a row.

Why is this slow? And why does it get worse as more cores are added?

Walk through this example. Each press of Step is one write to either A or B in memory by CPU 0 or CPU 1. The next write then alternates which CPU is writing. An M means that CPU modified and owns that row of memory and an I means its copy is now stale. Invalidations at the top counts how many times that happened.

Cache lines

The reason is cache lines, each row in the figure represents one. When a CPU reads from memory it doesn’t only grab the address it’s trying to read, it grabs a contiguous block around it and pulls the whole block into its cache. The exact size depends on the system but is usually 64 bytes.

This is almost always a win because the next thing you read is usually nearby. For example, when walking an array of 64-bit integers, one fetch brings in the next seven elements too, which avoids seven reads from memory.

Again this does differ by system but the L3 cache is shared across all cores within a CPU, and then each core gets its private/local caches called L2 and L1. For example Apple Silicon, where the benchmark ran, has no L3 and shares L2 within a core cluster instead, but the mechanism is the same.

The hardware only tracks memory in whole cache lines. So a write to A invalidates the line that holds B on the other core, even though nothing in the code modifies B. This is called false sharing, because the two cores share a line but none of the data. This behavior of the hardware is called cache coherence which is the guarantee that the caches never return stale data to the CPU.

Cache invalidations are slow because the next write to that position in memory needs to pull back the line from the other core or L3, which costs at least an L3 hit, around 43 cycles, compared to 3 to 9 cycles when pulling from the CPU’s L1 or L2 cache.¹

Padding

The solution here is padding, which is to add extra data to the objects that you’re operating on across threads in order to push them to separate cache lines. This is typically throwaway memory that will never be used but it is worth it because it will stop the overhead incurred by persistent cache invalidations and allow you to parallelize.

In Go the idiom is to use a cpu.CacheLinePad between the fields, because the size differs by architecture (64 bytes on amd64, 128 on arm64).

import "golang.org/x/sys/cpu"
 
type counters struct {
    a atomic.Uint64
    _ cpu.CacheLinePad
    b atomic.Uint64
}

The first struct is packed, which means the counters are next to each other. The second is padded by a cache line.

At four goroutines the padded version takes 2.2 ms against 52.9 ms packed.

Here’s the same example as before, but with the A and B sections of memory padded onto separate cache lines.

You can see that this properly allows each CPU to update their respective parts in memory without having any cache invalidations.

Go’s standard library does this too, for example in sync.Pool.

Here’s a more configurable simulation. Try adding a third CPU with Packed on, then switch to Padded and run it again.

Variables written from different threads should not share a cache line. If a parallel loop with no locks is slower than the serial version, check this issue first.

Hopefully this was an interesting short post with a visualization. I’m thinking about doing more of these smaller posts, with deeper dives in between, so let me know if you found it interesting!