Compare-and-Swap Retry Loops Under Contention

A lock-free update loop is three lines: load the value, compute the new value, compare-and-swap, and go back to the start if the swap failed. With two threads it beats a mutex, because a mutex that contends costs a syscall and a scheduler round trip while a failed compare-and-swap costs a few hundred cycles. With twenty threads it loses badly, and on some machines it loses to a plain mutex by an order of magnitude. The loop is the same loop; the contention is what changed.

The mechanism is worth stating precisely, because the performance of the loop is not a property of the loop. It is a property of the arrival process and the duration of the critical work, and the standard lock-free idiom has no defence against either.

What one iteration costs

An iteration of the loop performs a load of the shared word, a computation on the loaded value, and an atomic compare-and-swap. The compare-and-swap succeeds only if the word still holds the value that was loaded. On success the thread is done in one pass. On failure the thread retries, and the failure is caused by another thread having won the race in the interval between the load and the swap.

The failure mode is not merely a wasted attempt. The compare-and-swap that fails has already taken exclusive ownership of the cache line, which invalidates every other core’s copy. So a failed attempt costs not only its own work but also degrades every other thread’s subsequent load, forcing them to fetch the line from memory or from the winner. Under contention the line becomes a shared resource that every thread both reads and writes, and the traffic on it grows with the square of the number of threads while the useful work grows linearly.

The standard formulation makes the amplification visible. For $n$ threads that each attempt one update, the expected number of total attempts grows faster than linearly in $n$ even under the optimistic assumption that attempts are independent; the classic reference-count increment is the canonical illustration. With $n$ threads that all try to increment, the number of retries for the last thread to succeed is large because it must win against all the others repeatedly.

Consider a simple case: a counter incremented by $n$ threads. Each thread loads the value, computes the next, and swaps. If all load at once, exactly one wins and $n-1$ fail. Each of those retries and one wins among them. The expected total number of attempts is $\sum_{i=1}^{n} 1/i$ per success, so the total attempts for $n$ successes is $n \ln n$. Per successful update, the threads collectively perform $\ln n$ attempts. At $n = 4$ that is 1.4 attempts per update; at $n = 32$ it is 3.5; at $n = 256$ it is 5.5. The per-update cost grows, but slowly, and with 256 threads the raw numbers become large.

That model is optimistic because it assumes perfectly simultaneous attempts. In practice the retries synchronize: every failing thread immediately retries and they collide again, in lockstep, so the attempts cluster and the effective $n$ stays high. This is why the measured degradation is often worse than the model.

Threads	Attempts per successful update, $H_n$	Contended line transfers
2	1.5	3
8	2.7	22
32	4.1	131
128	5.5	704

The transfer column is the important one: each attempt costs at least one ownership transfer, and each failure invalidates other copies. The line becomes a bus on which every thread is a speaker, and the cost of the traffic is charged to the threads that are trying to do useful work.

Why backoff helps and why it is not enough

The first and most effective mitigation is exponential backoff: after a failure, sleep for a random interval that grows with the number of consecutive failures, then retry. The randomness decorrelates the threads so that they do not collide again, and the growth bounds the retry rate against a long-running competitor.

The effect is substantial because the amplification is a product of collisions and collisions require timing. Backoff reduces the collision rate by spreading arrivals, and with exponential growth the aggregate retry rate stays bounded even if some thread is starved. This is the same argument that network congestion control uses, and the same caveat applies: the sleep must be on the order of the critical section duration, and that duration is not known to the code.

#include <stdatomic.h>
#include <threads.h>

/* Bounded exponential backoff around an atomic compare-and-swap. */
int backoff_update(_Atomic long *p, long (*f)(long)) {
    unsigned ns = 1u;                     /* backoff budget in nanoseconds */
    for (int tries = 0; tries < 64; tries++) {
        long old = atomic_load_explicit(p, memory_order_relaxed);
        long neu = f(old);
        if (atomic_compare_exchange_weak_explicit(
                p, &old, neu, memory_order_seq_cst, memory_order_relaxed))
            return 0;
        struct timespec ts = { .tv_nsec = ns };
        thrd_sleep(&ts, NULL);            /* thrd_sleep returns non-zero on interrupt */
        if (ns < 4096u) ns <<= 1;         /* cap the growth */
    }
    return -1;                            /* give the caller a way out */
}

Two details matter here. atomic_compare_exchange_weak_explicit is used rather than the strong form because the weak form is permitted to fail spuriously and compiles to a plain load-linked / store-conditional pair on architectures that need one, which is generally cheaper; the loop already handles failure, so the spurious case is free. And the bounded retry count is deliberate: an unbounded loop gives a livelock the appearance of progress, while a bounded one lets the caller fall back to a different strategy.

Backoff does not remove the fundamental scaling term, however. With enough threads the successful-path cost still includes the coherence transfer of the line to whoever wins, and the winner changes on every operation. A lock-free counter and a mutex-protected counter both serialize on one cache line; the lock-free one simply does the serialization without a scheduler involvement. The limit is the same, which is why the counter is the wrong structure to optimize and the right structure to shard.

Replacing the retry with a different structure

Four structures avoid the retry entirely, and each has a different cost.

Shard the state. One counter per thread, each on its own line, summed on read. No retries, no coherence traffic in the steady state, and a read that is not linearizable. When the operation is a counter or an accumulator rather than a conditional update, this is almost always right, and the details are in Sharded Counters, Padding, and False Sharing.

Batch the updates. A thread that accumulates a hundred operations in a local buffer and applies them with one conditional update performs one compare-and-swap per hundred operations. The contention per operation falls by the batch factor, and the delay rises by the batch window. This is the same trade as Batching and the Amortization of Per-Item Cost, applied to the atomic operation rather than the syscall.

Use a combining tree. Threads contend in pairs, then pairs contend, in a tree of depth $\log n$. Total contention on any one word is at most two threads, so the retry rate is bounded independent of $n$. The cost is depth: an update takes $\log n$ sequential steps, so latency rises with thread count even as throughput holds. This is the right structure when the aggregate rate is the metric and the per-operation latency is not.

Use the hardware’s transaction support. Transactional memory, where available, lets a thread perform several reads and writes speculatively and commit only if no other thread interfered, with the conflict resolved by the hardware rather than by a software retry loop. It replaces the compare-and-swap with a commit that is cheaper when contention is low and aborted when it is high. The abort rate under contention is the same phenomenon as the retry rate, so the technique does not escape the scaling limit; it moves the implementation into hardware.

Detecting the regime you are in

The three regimes have distinguishable external signatures, and identifying which one applies determines whether any of the above is worth doing.

In the cheap regime, throughput rises linearly with thread count until the cores are saturated, and the retry rate is a small fraction of the attempt rate. A counter of failed compare-and-swaps against total attempts, sampled per thread, identifies this directly.

In the saturated regime, throughput plateaus as threads are added while the retry-to-success ratio rises. The plateau means the atomics have replaced the real work as the bottleneck; the ratio rising means the plateau is caused by collisions rather than by a core limit. A useful confirmation is that throughput also stops improving when the working set is reduced to nothing, which rules out memory bandwidth.

In the pathological regime, throughput falls as threads are added. This is the one that automation rarely surfaces, because the run with fewer threads is not part of the comparison. A sweep over thread counts, from one upward, is the only reliable way to see it, and the peak is usually at a thread count far below the core count.

Hardware performance counters make the same distinction without touching the code: the count of remote cache line fetches and the ratio of cycles to instructions for the region both rise sharply when a line is being transferred between cores rather than accessed locally. Those counters attribute the cost to memory rather than to the loop, which is why the diagnosis often begins with the observation that the “CPU-bound” loop is spending most of its cycles waiting for cache lines.

What lock-free does not mean

The word “lock-free” describes a progress guarantee, not a performance property. A lock-free algorithm guarantees that some thread makes progress in a finite number of steps regardless of what other threads do; a wait-free one guarantees that every thread does. Neither says anything about the rate, and the behaviour of the standard retry loop at high thread counts is precisely what the guarantee permits: some thread makes progress, so the algorithm is lock-free, while all the others spin.

That gap between the progress guarantee and the throughput curve is where most of the practical difficulty lives. The loop is correct and it is fast when uncontended, and the interesting decisions are all about the contention regime: shard when the state permits it, batch when the interface permits it, queue when fairness matters, and measure the thread count at which the loop’s rate stops rising. Systems that assume the loop scales because it has no lock are the ones that discover the cache line instead.