The benchmark said zero retries_

In May a benchmark handed me two numbers about the same queue, from the same run. The first number: zero retries. The second: per-operation cost climbing from 16.6 ns/op with one producer to just over 99 ns/op with eight, a 6x slowdown.

The queue was a lock-free MPSC ring whose producers push through a compare-and-swap retry loop, and the retry counter was mine: the harness tallied how many times the loop went around before a push succeeded. If nobody ever retries, the loop body runs exactly once per push, so I expected the cost to stay roughly flat as producers were added, and it climbed 6x instead. One of the two numbers was measuring something other than what I thought it measured, and it took the CPU's own performance counters to find out which one.

What the ring is for

The ring lives in the concurrency layer inside astral, alongside an SPSC ring, an MPSC variant built on ticket reservation instead of CAS retries, and an epoch-based reclamation scheme the rings lean on for safe memory reuse. The module is about 1,350 lines in total.

The reason any of it is hand-rolled: an inference runtime spends a large share of its time handing buffers between threads. Tokenization, scheduling, execution, and sampling are separate stages, and every boundary between them crosses a queue. If a handoff blocks on a lock or spins on a failing CAS, the cost lands directly on tokens per second, because there is no layer of indirection between the queue and the serving loop to absorb it. So the queues have to be fast, and I have to actually know they are fast. The zero-retries number came from the MPSC push path, so that is where I started.

The old push path

The original MPSC push had the shape every lock-free queue tutorial teaches. This is a self-contained illustration, compiled fresh for this post rather than lifted from the source, but the shape is exactly what I had:

// standalone illustration, compiled fresh for this post, not the astral source
uint64_t cas_reserve(CasRing& r) {
    for (;;) {
        uint64_t t    = r.tail.load(std::memory_order_relaxed); // observe the tail
        uint64_t want = t + 1;                                  // what I want it to become
        if (r.tail.compare_exchange_strong(t, want,
                                            std::memory_order_acq_rel,
                                            std::memory_order_relaxed))
            return t;                                           // won: slot t is mine
        // lost the race: another producer's increment landed between the
        // load and the compare, so go around against the new tail.
    }
}

The loop does this: load the shared tail, compute the value tail should become, then execute an atomic compare-exchange that says, if tail still holds what I loaded, replace it with my value, otherwise report failure. Success means the producer owns slot t outright. Failure means another producer's increment landed in the window between the load and the compare, so the observed value is stale and the loop goes around against the new tail.

Clang -O2 emits this loop for the standalone reproduction:

; clang++ -O2 -std=c++17 -S -masm=intel (x86-64), cas_reserve
LBB0_1:
    mov       rcx, qword ptr [rdi]        ; observe the current tail
    lea       rdx, [rcx + 1]              ; the value I want it to become
    mov       rax, rcx                    ; comparand for cmpxchg
    lock cmpxchg qword ptr [rdi], rdx     ; needs the line exclusive first
    jne       LBB0_1                      ; taken exactly when the compare lost

Two costs live in those four lines. The first is the lock cmpxchg. It needs the cache line holding tail in exclusive state before it can execute, so under contention it pays for coherence traffic: the line has to travel from whichever core last owned it before the compare can even run.

The second is the jne, a conditional branch whose outcome is decided by whether another core beat you inside a window a few nanoseconds wide. The branch is taken exactly when the compare lost, so under contention its behavior is set by the race, not by anything in the surrounding code.

With a single producer the loop is fine. The line stays resident in one core's cache, the CAS always succeeds, the branch always falls through, and the cost sits at about 17 ns/op. Add producers and it degrades, and by eight producers the same push cost just under 100 ns/op.

Zero retries, 6x slower

The harness counted retries directly: every trip around the loop before a successful push incremented the counter. Under contention it reported zero.

Taken at face value, that number clears the CAS loop completely. If nobody ever retries, the loop body executes exactly once per push, contention or not, and the slowdown must live somewhere else: the allocator, the scheduler, false sharing inside the harness itself, anywhere but the compare-exchange.

The timing said otherwise. A 6x cost increase that tracks producer count is the signature of producers interfering with each other, and the only shared state on the push path was the tail counter and the ring slots. I did not have a mechanism that let both numbers be true. So one of them was measuring something other than what I believed, and the question was which one to distrust first. The retry counter was my own code and could be wrong in ways I had not thought of. The timing was wall-clock arithmetic over millions of operations. Rather than argue one against the other, I wanted a third source of evidence that neither could contaminate: the CPU's performance monitoring unit, the PMU, which counts events in hardware regardless of what my code reports.

One question per capture

The capture discipline matters more than the tooling. The PMU has a limited number of programmable counters. Ask perf stat for more events than the hardware can host at once and it multiplexes: each event is counted for a fraction of the run and scaled up, which injects interpolation error. On a benchmark whose entire signal is a few nanoseconds per operation, that error can be the size of the effect you are hunting. So the capture gets split: one run per question, a small event set per run, and the same producer counts across runs so the trends line up point for point. The shape of it:

# one question per capture
perf stat -e branches,branch-misses         ./bench_ring --producers 4
perf stat -e cache-references,cache-misses  ./bench_ring --producers 4

Run that across a sweep of producer counts and the output is two trend lines: branch misses against producer count, and cache misses against producer count.

Two trend lines

Read together, the two trends say where to look next.

Cache misses rising while branch misses stay flat would mean real cross-core memory contention: another core keeps taking the line you need, the miss counter tallies the trips, and the bill is DRAM and coherence latency. The fix for that lives in data layout: padding, per-producer sharding, batching to amortize the transfers. The loop's control flow would be innocent.

Branch misses rising while cache misses stay flat means the data is arriving fine and the pipeline itself is the bill. The front end keeps guessing a branch wrong and flushing. The fix for that is control flow: find the branch whose outcome has become unpredictable and remove it.

Both rising means both problems, and the memory side gets fixed first because it usually drives the other. Neither rising sends you back to the harness, because the ring is cleared and the slowdown lives outside it.

My run landed on one side: branch misses climbed to 16.9% at two producers and roughly 19.5% at four, and cache misses stayed flat, under 1%. At eight producers the miss rate eased back to about 12.4% even as the cost kept climbing; I did not chase that wrinkle down, and the diagnosis does not depend on it. So the data was arriving fine and the constant flushing had to be coming from control flow. The only data-dependent branch on the path was the one after the compare-exchange.

One footnote on that flat cache-miss line, because it confused me for a few minutes. The failure mechanism I am about to describe is cache-line arbitration, so you might expect it to show up in a cache counter. The events I was watching count misses that go out to memory. A hot line bouncing between two cores' private caches gets served by the coherence fabric, core to core, and barely moves that counter. So the flat line ruled out the DRAM story without ruling out arbitration, and the arbitration showed up where arbitration actually hurts here: in the branch.

At this point the diagnosis is narrow. Nothing is waiting on memory, and one branch is missing about a fifth of the time. What is left to explain is why that branch, specifically, became unpredictable.

What arbitration does to a branch

A locked read-modify-write needs its cache line in exclusive state. When another core owns the line, the coherence protocol has to move it: a read-for-ownership goes out, the owner gives the line up, ownership transfers, and only then does the compare execute. With producers on several cores all hammering the same tail counter, the line is in constant motion.

Whether your CAS succeeds depends on whether another core's increment landed between your load and your locked compare. That window is nanoseconds wide. Who wins it is decided by which core happens to hold the line in modified state at that instant and by the order the interconnect services requests. None of that is visible to the program; the only signal it gets is the failed compare afterward.

So the outcome of that jne is decided by arbitration timing between cores, not by anything the program computes, and that matters because of how a branch predictor works.

What the predictor cannot learn

A branch predictor works by finding correlation between a branch's past outcomes and its next one; local history, global history, and the tagged geometric tables in a modern front end all index that history differently. A branch resolved by inter-core arbitration timing has no correlation to find. The information that decides its outcome lives in another core's cache controller, invisible to everything the predictor can index on.

If the CAS fails one time in five, with the failures scattered by timing noise rather than any repeating pattern, the predictor settles on the majority direction and eats a miss on nearly every failure. So the miss rate on that branch converges toward the failure rate itself. A better predictor does not fix this, because more history and bigger tables only help when the deciding information reaches the predictor at all, and this information never leaves the other core's cache controller.

Each miss costs a pipeline flush: everything younger than the branch is thrown away, the front end refetches from the correct target, and the machine spends tens of cycles on a wide core rebuilding what it discarded. The misses also compound. By the time the pipeline refills and the compare-exchange re-executes, the line has often moved again, so the retry rides straight into the same race with the same odds.

That explains the slowdown. It does not yet explain why the retry counter read zero.

The arithmetic that reconciles the two numbers

The two measurements sit badly next to each other: my harness said retries were zero, and the PMU said the branch after the compare-exchange missed roughly 19.5% of the time.

The answer was one abstraction level up from where I had been looking. The harness counts a retry when try_push returns false, and try_push returns false in exactly one case: the ring is full. A failed compare-exchange never surfaces there. The reservation loop lives inside try_push, and on a lost race it goes around and tries again without ever returning, so the loss is structurally invisible to the caller. My counter was answering the question "how often was the ring full," and the ring was never full; the zero is exact, printed to four decimal places. The question I thought I was asking, how often a reservation lost the race, was not measured by anything in my harness. The only instrument that saw those losses was the PMU: a CAS losing roughly one race in five, with the losses scattered by timing the predictor cannot index, misses on the order of 20% on that branch, and 19.5% is what the counter read.

So neither number was an artifact. The zero was a correct answer to a question I did not mean to ask, and the miss rate was the answer to the one I did. The word retries had quietly meant two different loops, the capacity loop in my harness and the reservation loop inside the queue, and until the PMU forced the distinction I had been reading one as if it were the other.

The ticket reservation

The expensive thing is a conditional branch whose outcome is an inter-core race. Backoff does not fix that; it spaces the races out and leaves the branch just as unpredictable when they happen. What follows from the diagnosis is removing the conditional, and that is what the ticket redesign does. The same standalone illustration, the ticket path this time:

// reservation: one unconditional atomic, no failure case
uint64_t ticket_reserve(TicketRing& r) {
    return r.tail.fetch_add(1, std::memory_order_relaxed);
}

// publish: wait on this slot's own sequence, then store and release
void ticket_publish(Slot* ring, uint64_t capacity,
                    uint64_t ticket, void* item) {
    Slot& s = ring[ticket & (capacity - 1)];    // capacity is a power of two
    while (s.sequence.load(std::memory_order_acquire) != ticket)
        cpu_pause();                            // spin on this slot only
    s.value = item;
    s.sequence.store(ticket + 1, std::memory_order_release);
}

The producer executes one unconditional atomic increment on the tail and receives the previous value back: its ticket. There is no failure case. The hardware serializes concurrent increments and every caller gets a distinct number, so the reservation succeeds by construction.

The ticket maps to a slot, and the producer waits on that slot's own sequence counter until the counter equals its ticket, which means the slot is free for this lap. Then it writes the item and stores ticket plus one with release ordering to publish it, the same publish discipline the old loop used. The per-slot sequence is the whole handshake: the consumer advances the same counter from its side, so the slot becomes reservable again a lap later. A per-slot sequence counter is the standard way to make a bounded MPMC reservation total, so the loop never has to fail.

The reservation now cannot fail, and the waiting happens on a per-slot counter that only one producer and the consumer touch, not on the shared tail.

At the instruction level, the same clang -O2 output:

; clang++ -O2 (x86-64), ticket_reserve
    mov       eax, 1
    lock xadd qword ptr [rdi], rax        ; unconditional; rax is my ticket
    ret                                   ; no jne, nothing to retry

Be clear about what did not change. The xadd pays the same locked cache-line traffic on the tail that the CAS did: producers still serialize through one atomic increment, the tail line still moves between cores, and each fetch_add still waits its turn for exclusive ownership. What changed is that no control flow depends on winning a race anymore; nothing branches on the outcome of the increment.

What about the wait loop that remains? It branches, but on a plain acquire load of the slot's own sequence counter, and its behavior is nothing like the CAS branch. In the common case the slot is already available and the loop exits immediately; under load it spins until one specific writer hands over one specific slot. Either way the pattern is stable within a contention regime, and a stable pattern is something a predictor can learn.

One scoping point I keep repeating because it is easy to garble: the MPSC ticket path deliberately keeps one locked read-modify-write, the fetch_add reservation. The zero-locked-instructions claim that appears later in this post belongs to the SPSC hot path only. I do not know how to hand distinct slots to concurrent producers without at least one atomic read-modify-write, so when a queue advertises none at all, the first thing to check is whether it is actually multi-producer.

What the numbers did

The real result is the flattening. From two producers up the ticket path holds a band of roughly 18 to 21 ns/op essentially independent of producer count, where the CAS path climbed 5.5x over the same sweep. At eight producers the ticket path came out 5.5x faster, and the contended ticket cost, 17.82 ns/op, is about what the CAS path cost with no contention at all.

Both columns come from one capture, the two rings run back to back on the same host. It is a separate capture from the run in the opening figure, which is why its eight-producer CAS cost reads 97.18 where the opening run read 99.28; a pinned rerun of the same sweep lands at 101.86 for the CAS path with the ticket band at 20 to 21, and the ratio stays close to 5.5x in all three.

Blocking instead of busy

The redesign costs something, and the cost is not in the numbers: it changes what a producer can do when the ring is full. Look back at the two code listings. The CAS version could return busy: a producer that found the ring full could hand the decision back to its caller, and the caller could back off, drop the work, or try a different queue. The ticket version cannot. Once fetch_add executes, the producer owns a slot number and is committed; if the ring is full, it blocks on its slot's sequence counter until space opens up.

I wrote that tradeoff directly into the header comment, next to the signature, so nobody, including me in six months, has to rediscover it: producers block on a reserved slot instead of getting busy back the way the old loop could. For astral's internal fan-in paths, where every producer is expected to get through eventually and the right response to pressure is to wait, that is the behavior I want. At a public API boundary it would be the wrong call, because a caller there may need the busy answer back, and this design takes that option away at the moment the ticket is issued.

What changed, and what did not

The MPSC ring still has one contended atomic on its reservation path. That line still moves between cores, and the design is not magically free of serialization. What disappeared is the branch whose answer came from an inter-core race. The replacement turns the race into an unconditional ticket, then waits on a slot with one producer and one consumer.

The original retry counter was not buggy. It answered "was the ring full?" exactly, while I read it as "did the compare-exchange lose?" Those are two different loops. The PMU capture forced me to separate them, and the counter now names the condition it actually measures.

One number remains unexplained: the branch-miss rate fell from 19.5% at four producers to 12.4% at eight even while cost rose. I kept the point in the results and do not yet have a mechanism for it.