Cache Lines, Padding, and the Cost of Trying Again

Several producers reach a shared queue at once. Each tries to claim the next slot by updating the same atomic counter with compare-and-exchange (CAS). Only one can claim that position. The others discover that the counter has changed and try again. Under contention, they can spend a substantial part of their time retrying instead of moving messages.

Those retries have a cost. Repeated atomic update attempts compete for the same cache line, adding coordination between cores. Retrying as fast as possible can increase that competition. Backoff spaces out the attempts: after losing a reservation, a producer waits briefly before trying again. The aim is to reduce interference so the producers collectively complete more useful work. An exponential policy increases that wait after successive contention events, up to a limit.

On x86, _mm_pause() is one way to spend that short wait. It tells the processor that the thread is in a spin loop. Intel's optimization manual describes how PAUSE reduces the execution resources and power consumed by such loops; this can also help a sibling hardware thread sharing the same physical core. The thread stays runnable. Backoff chooses how long to wait between attempts, and this implementation uses one or more PAUSE instructions during that wait.

The tradeoff is responsiveness: waiting too long can delay an attempt that would have succeeded. A pause on every retry and an increasing backoff are therefore separate policies worth measuring. Neither promises a speedup.

This experiment compares multiple producers sharing one MPSC queue with separate SPSC queues feeding one consumer. Alongside retry behavior, I vary memory layout: padding can keep independent writers off the same cache line, while backoff can reduce how often producers compete for a genuinely shared counter. First, we need to see which kind of sharing the queue has.

A cache line contains more than your variable

Suppose one thread writes head and another writes tail. They are different atomic objects, so their updates do not conflict at the C++ object level. If both sit in the same cache line, their writes can still require coordination between cores over that line. This is false sharing: the threads need independent objects, but the coherence granularity groups them together.

Giving the two indices separate lines can remove that particular source of interference. It does not remove communication. The consumer still reads the producer's index and the producer still reads the consumer's index. If all producers CAS the same MPSC head, they are truly sharing one object; padding around it cannot give them independent ownership of that counter.

The animation is a simplified ownership model, not a trace of this VM. Real coherence states, shared reads, write buffers, and timing are omitted. It shows the reason to investigate false sharing; it does not establish that false sharing dominated our benchmark.

Check the layout before timing it

Aligning an entire object only aligns its beginning. Two fields inside that object can still be adjacent. In the code below, each hot field in Separate has its own alignment requirement. On the selected x86-64 compilers, the fields are 64 bytes apart. The program prints offsets and sizes so the layout is visible.

The same program includes the bounded exponential retry loop we will discuss next. It verifies a counter result, not a performance claim. Download it and build with g++ -std=c++20 -O2 -pthread layout-backoff.cpp -o layout-backoff on x86-64.

#include <algorithm>
#include <atomic>
#include <cstddef>
#include <cstdint>
#include <immintrin.h>
#include <iostream>
#include <thread>

struct Packed {
    std::atomic<std::uint64_t> a{0}, b{0};
};
struct Separate {
    alignas(64) std::atomic<std::uint64_t> a{0};
    alignas(64) std::atomic<std::uint64_t> b{0};
};
std::atomic<std::uint64_t> counter{0};

// All threads still contend on this ONE counter. Padding cannot fix that.
void increment() {
    auto expected = counter.load(std::memory_order_relaxed);
    unsigned pauses = 1;
    while (!counter.compare_exchange_weak(
        expected, expected + 1, std::memory_order_relaxed)) {
        for (unsigned i = 0; i < pauses; ++i) _mm_pause();
        pauses = std::min(2 * pauses, 16u);
    }
}

int main() {
    std::cout << "Packed offsets: " << offsetof(Packed, a) << ", "
              << offsetof(Packed, b) << "; bytes: " << sizeof(Packed) << '\n';
    std::cout << "Separate offsets: " << offsetof(Separate, a) << ", "
              << offsetof(Separate, b) << "; bytes: " << sizeof(Separate) << '\n';
    std::thread a([] { for (int i = 0; i < 10000; ++i) increment(); });
    std::thread b([] { for (int i = 0; i < 10000; ++i) increment(); });
    a.join();
    b.join();
    std::cout << "CAS counter: " << counter.load() << " (expected 20000)\n";
    return counter.load() != 20000;
}

Sixty-four bytes is a target choice, not a portable promise about every machine. More spacing also consumes more memory. Our MPSC layout option pads every slot as well as the hot indices. Comparing that with the packed version changes footprint and locality alongside potential false sharing. It is not a surgical experiment on one cache line.

What PAUSE does here

_mm_pause() emits the x86 spin-loop hint described by Intel's instruction documentation. It gives the processor information about a waiting loop. It does not release a lock, park the OS thread, make a payload safe to read, or promise a particular delay across processors.

The queue's memory-ordering operations still provide correctness. The pause affects the retry policy.

The MPSC experiment uses three policies after a failed reservation attempt or an observation that another producer has already claimed the position:

The backoff budget resets for a new push attempt. Full-queue waiting outside the reservation loop is a separate path. The policy does not intentionally delay every successful enqueue.

The reason to try backoff is that an unsuccessful producer may otherwise keep generating contention while another producer makes progress. Waiting a little can reduce that pressure. Waiting too long can also waste a newly available opportunity. There is no useful universal rule that one pause, or sixteen pauses, is optimal.

One pause was slower in this experiment

The primary runs used equal aggregate capacity, a separate consumer CPU, and 30 shuffled rounds. These are median millions of messages per second:

Exponential backoff divided by immediate retry was 1.342×, with a paired-round bootstrap 95% interval of 1.227–1.500×, at four producers. At eight producers it was 1.104×, interval 1.036–1.197×. Those intervals describe this session, not the range of all future machines or workloads.

One pause per retry was slower than immediate retry in both primary configurations. This matters because “add pause” and “use a backoff policy” are often treated as the same optimization. The implementation and the workload both matter. The eight-producer case also shares one producer CPU and changes total capacity; its difference from the four-producer case cannot be attributed only to contention on head.

Padding did not earn a speedup claim

For SPSC, the aligned version divided by the packed version was 0.878× at four producers, with interval 0.808–1.006×. At eight it was 0.915×, interval 0.815–1.019×. The point estimates favor packed storage, but both intervals include parity. This experiment does not establish an alignment benefit.

I would not turn this into “false sharing is a myth,” either. A plausible mechanism is not a guaranteed bottleneck, and a throughput result does not identify the exact hardware cause. The next investigation would separate index layout from slot layout, vary capacity and payload size, and collect appropriate hardware events on a host that exposes them.

The current VM did not expose hardware performance counters. Cachegrind produced simulated cache statistics for several cases, but it serializes execution and does not model cross-core coherence traffic. Those counts cannot prove that this change reduced cache-line bouncing.

Reproduce the variants

The standalone project contains the layout switches and retry policies. On the original nine-vCPU mapping, these commands run the four-producer shared queue with equal capacity:

git clone https://github.com/tedkoomen/resume.git
cd resume/benchmarks/spsc-vs-mpsc
make -j4 fair-build
BENCH_CONTROL_CPU=8 taskset -c 0-4,8 build/fair4/fanin_lockfree_mpsc_b0 100000 3 0 4
BENCH_CONTROL_CPU=8 taskset -c 0-4,8 build/fair4/fanin_lockfree_mpsc_b1 100000 3 0 4
BENCH_CONTROL_CPU=8 taskset -c 0-4,8 build/fair4/fanin_lockfree_mpsc_b2 100000 3 0 4

These are quick smoke runs, not the shuffled 30-round collection. CPU IDs must exist in your allowed set and match the intended NUMA topology. The project README explains the runner and longer confirmation. Use the _stats binaries for retry counts separately: instrumentation adds work to the very path being studied.

Backoff improved the measured MPSC result, but it still depends on other threads getting CPU time. That becomes much more obvious when the waiting loop protects a lock.