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.

The hardware counters showed branch-recovery pressure, while the disassembly exposed the retry loop that the caller-level counter had missed. I replaced conditional reservation with one ticket increment and measured both versions.

The ring in Astral

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 bounded queues for worker fan-in and token delivery. Their synchronization cost lands directly on runtime work, so I measured how each queue scaled with producer count.

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 loads the shared tail, computes its replacement, and attempts a compare-exchange. Success reserves slot t. Failure means another producer changed the tail after the load, so the loop retries with the new value.

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

The lock cmpxchg needs exclusive ownership of the cache line holding tail. Under contention, that line moves between producer cores before the comparison can run.

The following jne branches when another core wins the reservation first. Its outcome depends on a race a few nanoseconds wide.

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.

The zero count did not include failed CAS reservations, so it could not explain the sixfold slowdown around the shared tail and ring slots.

I checked a third source: the CPU performance monitoring unit, or PMU. It counts hardware events independently of the queue's own instrumentation.

What the hardware counters could show

perf multiplexed the requested events because the hybrid processor did not have enough PMU slots to count them all at once. At four producers, the core events were active for about 78% of the interval and the efficiency-core events for about 53%.

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

Branches and branch misses on each PMU shared the same active fraction, so their ratio was still useful for deciding what to inspect. The queue timings came from the benchmark's own clock.

The two trends

Branch mispredictions rose with producer count across the complete benchmark. That made the compare-exchange retry branch worth inspecting, though the event cannot identify one source branch by itself. Generic cache misses are incomplete too. A hot line can move between cores without reaching the last-level cache or DRAM.

Branch misses reached 16.9% at two producers and 19.5% at four while generic cache misses stayed below 1%. At eight producers, branch misses fell to 12.4% even as cost rose. This supports branch cost and argues against increasing DRAM misses. Direct retry instrumentation or sampled branch records would be needed to attribute those misses to the compare-exchange loop.

The flat cache-miss line rules out increasing misses at the measured cache level. Coherence can still move a hot line directly between cores, and the locked compare still needs exclusive ownership of the tail line.

Cache-line arbitration

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.

CAS succeeds only if no other core increments the tail between the load and locked compare. Which producer wins depends on cache-line ownership and the order in which the interconnect services requests. The program sees only success or failure.

That arbitration timing becomes the input to the jne.

An unpredictable retry branch

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 19.5% is not a retry rate. It shows that the complete workload spent real front-end work recovering from mispredictions, while the source and assembly identify the retry branch as the race-dependent branch worth removing.

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);
}

One unconditional atomic increment returns the previous tail value as a ticket. Concurrent increments are serialized by hardware, and every producer receives a distinct number.

The ticket selects a slot. The producer waits until that slot's sequence equals the ticket, writes the item, and publishes ticket + 1 with release ordering. The consumer advances the same sequence when it releases the slot for the next lap.

After claiming a ticket, the producer no longer reports the ring as full. It waits on the sequence counter for its assigned slot, which only that ticket owner and the consumer advance. It can still wait indefinitely if the consumer or an earlier ticket owner stops.

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

Each xadd still needs exclusive ownership of the shared tail line, so producers serialize through one contended atomic increment. The ticket path performs exactly one locked operation per reservation and has no branch on success.

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.

The shared ticket ring still performs one locked read-modify-write because every producer reserves from the same tail. That is a property of this ownership model, not a rule for every MPSC-facing queue.

When I know the producer set ahead of time, I can give each producer its own SPSC lane and let the consumer poll the lanes. Astral's SpscFanIn takes that route, so producers do not share a reservation counter in the hot path. The cost moves into fixed producer ownership, memory for every lane, and the consumer's lane scan.

I kept the ticket ring for the runtime work queue because submissions can arrive from arbitrary application threads. Under that constraint, one fetch_add is the shared reservation I chose.

The measured result

The ticket path remains between roughly 18 and 21 ns/op from two through eight producers, 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.

The two rings were measured back to back on the same host. This comparison is separate from the opening measurement, which is why the eight-producer CAS value is 97.18 here and 99.28 in the first figure. The difference between those sessions does not change the decision: the ticket ring stayed near 18 to 21 ns/op while the CAS loop stayed near 100.

The ticket commits the producer

The redesign changes behavior when the ring is full. The CAS version can return busy, letting the caller back off, drop the work, or try another queue. After fetch_add, the ticket version owns a future slot and must wait for it.

Changing the reservation also changed the contract. After fetch_add, a producer owns a future slot. In this design, it cannot return busy without leaving a hole for the consumer, so it has to wait for that slot.

I use the ticket ring only on internal paths where every work item must eventually get through. I would not put it behind a non-blocking public API, where the caller may need to back off or drop the work. I put that rule beside the type because it is part of the queue's behavior, not a benchmark footnote.

One unresolved result

The counter now names the full-queue returns it actually measures. The ticket ring still serializes producers through one atomic tail increment, but it removes failed reservations and their branch.

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.