Cache coherence

Some recent work on database internals made me want to strengthen my mental model for concurrent programming primitives. I wrote a thread-safe, lock-free bounded ring buffer entirely by hand (yes, by typing out code). When attempting to optimize the lock-free performance, results were at first confusing, then became clear in a way that sharpened my intuition for these concepts, so I’m documenting my notes here.

This is a single reader, single writer (or SPSC) bounded circular buffer. It uses monotonic read and write pointers, and wraps them around the buffer capacity to identify a slot.

The reader calls ring_buffer.pop() and the writer calls ring_buffer.push(); both operations read both pointer values:

• The reader checks whether the buffer is empty (read_ptr == write_ptr), and if not, reads the value at the read pointer index and increments the read pointer.
• The writer checks whether the buffer is full (write_ptr - read_ptr >= capacity), and if not, writes the value at the write pointer index and increments the write pointer.

A naive first optimization I tried was cache padding: if we pad the read & writer pointers so that they’re on separate cache lines we should have less cache invalidation between the threads and better performance. I ran benchmarks, and the elapsed time rose roughly 100%, twice the baseline.

I then pursued another idea: because we use monotonic pointers, when the reader and writer read the opposite thread’s indices, they don’t actually need the current value:

• The reader needs to know if it’s caught up to the writer: read_ptr == write_ptr.
• The write pointer now is guaranteed to be no less than any past write pointer the reader might have seen.
• So if the reader caches the last write pointer it saw, if read_ptr < last_seen_write_ptr, there is no need to read the cross-thread atomic value. The reader only needs an atomic read of the write pointer when it catches up to the last write pointer it saw.

The inverse also holds for the writer reading the read pointer.

After making this change, I once again ran benchmarks, and saw no statistically significant change.

I then tried adding back the cache padding between the pointers along with the local caching, and saw a 2x speedup from baseline.

My understanding:

• Baseline: both pointers share one cache line. The writer and reader each update their respective pointer. Each pointer update invalidates the other core’s cached copy. The other core must fetch the line again before its next access.
• Cache padding only: each pointer occupies a separate cache line, but both threads still read both pointers. Each core therefore holds a copy of both lines. A pointer update invalidates the other core’s copy. Two cache lines now take part in the coherence traffic instead of one.
• Local caching only: each thread avoids many loads of the other pointer. However, both pointers still share one cache line. Each pointer update still invalidates the other core’s copy of that line, so the optimization provides little benefit.
• With both changes: each pointer occupies a separate line, and each thread usually accesses only its own pointer. The producer or consumer reads the other pointer only near the full or empty boundary. Each pointer line therefore tends to remain local to its core, which greatly reduces coherence traffic.

Relative elapsed time:

Cache padding alone did not reduce contention. It only helped once the access pattern let each thread stay mostly on its own cache line.