The benchmark said zero retries_

One benchmark reported zero retries while the same queue slowed from 16.6 ns/op with one producer to 99.28 ns/op with eight. Both numbers came from the same run.

The queue reserved slots through a compare-and-swap loop, but the counter labeled "retries" measured full-queue returns at the caller. Failed reservations stayed inside the queue and never reached it.

This article follows the mismatch through hardware counters and disassembly, then measures the ticket reservation that replaced the conditional retry. The counters expose an avoidable branch cost; they do not make the shared cache-line traffic disappear.

What the ring is for

The ring lives in Astral's concurrency layer beside SPSC, ticket-based MPSC, fixed-lane fan-in, and MPMC structures. A separate epoch manager handles conversation lifetime; the rings do not depend on it for slot reuse.

Astral uses these bounded queues for worker fan-in and token delivery. Their synchronization cost lands directly on runtime work, so the queue benchmark needs to explain its own scaling rather than hiding behind a throughput average.

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 labeled its counter "retries," but incremented it when try_push returned false. In this ring that means the queue was full; a failed compare-and-swap retries inside try_push and never reaches the caller. Under contention the counter therefore 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.

What the counter capture can support

The preserved run requested cycles, instructions, branches, branch misses, cache references, and cache misses together. On this hybrid processor that exceeded the available PMU slots, so perf multiplexed and scaled the events. At four producers the core-PMU events ran for about 78% of the interval and the atom-PMU events for about 53%.

perf stat -e cycles,instructions,branches,branch-misses,cache-references,cache-misses \
  ./bench_ring --producers 4

That is weaker evidence than separate pinned captures. Branches and branch misses on one PMU share the same running fraction, so their ratio remains useful as a directional signal, but I do not use this run for precise cycle attribution. The queue timings come from the benchmark's own clock.

Two trend lines

Read together, the two trends say where to look next, but only within the limits of the events being counted.

Rising branch misses prove that the front end is paying for unpredictable control flow. A flat generic cache-miss count does not prove that coherence is cheap: cache-to-cache ownership transfers can move a hot line between cores without appearing as last-level misses or DRAM traffic.

My run showed branch misses climbing to 16.9% at two producers and 19.5% at four while generic cache misses stayed under 1%. At eight producers the branch-miss rate eased to 12.4% even as cost kept rising. The result identifies a substantial branch cost and rules out a growing DRAM-miss story; it does not separate that cost from the locked operation's cache-line arbitration.

The flat cache-miss line therefore rules out one explanation, increasing misses that reach the measured cache level, without clearing the memory side of the instruction. The locked compare still needs exclusive ownership of the tail line, and the branch still depends on whether that compare wins.

At this point the useful finding is narrower: one branch misses about a fifth of the time, and the generic cache event does not explain the rest of the latency.

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 looks for correlation in past outcomes and surrounding control flow. A compare-and-swap retry depends partly on when other cores modify the same word, information the local branch history does not fully encode. The measured miss rate shows that this branch was difficult to predict on this workload.

The branch-miss rate is not a direct CAS-failure counter, so I cannot turn 19.5% into an exact retry rate. It is enough to establish that the retry branch carries real front-end cost under contention.

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 one avoidable part of 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 when the ring is full. A failed compare-and-swap never surfaces there. The reservation loop stays inside try_push and tries again, so the loss is invisible to the caller. My counter was answering "how often was the ring full?" The PMU answered a different question: "how often did the processor mispredict branches on this run?" Disassembly connected the rising branch cost to the reservation loop, without pretending the PMU counted failed compares directly.

So neither number was an artifact. The zero was a correct answer to a question I did not mean to ask, and the branch misses exposed work the caller-level counter could not see.

The ticket reservation

The old reservation can execute extra locked compares and an unpredictable branch before one push succeeds. The ticket redesign makes reservation unconditional: one atomic increment produces one ticket, with no failed reservation branch. 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. Each xadd still needs exclusive ownership of the shared tail line, so producers still serialize through one contended atomic increment. What changed is the multiplier: one locked operation per successful reservation, instead of one or more locked compares, and no branch on whether the increment won.

The wait loop remains, but it polls one slot's sequence counter after reservation. In the common case the slot is ready; under backpressure the producer waits for the consumer to release that specific slot. The benchmark measures the combined result rather than assuming that branch is free.

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 ticket ring still has one contended atomic on its reservation path. That line still moves between cores, and the design is not free of serialization. What disappeared is failed reservation attempts and the branch on their outcome. The replacement assigns one 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.