CAS Contention and Backoff

Learning objective

Explain compare-and-set as a conditional atomic update, show how retry loops under contention amplify both coherence traffic and latency, compare no-backoff, fixed-backoff, and exponential-backoff-with-jitter retry strategies, and explain why "lock-free" does not automatically mean "low latency" — contrasting CAS contention against a single-writer ownership alternative.

Prerequisites

• The Memory Ordering in Java and Rust lab — CAS is itself an atomic read-modify-write, and this lab assumes the atomicity/visibility/ordering distinction from there.
• The Cache Coherence and MESI lab is useful background for "cache-line ping-pong" below, though not required.

Theory

Compare-and-set (CAS)

Compare-and-set is a single hardware-atomic instruction (cmpxchg on x86, ldxr/stxr or cas on ARM) with the shape: "if the current value equals what I expect, replace it with a new value — atomically, as one indivisible step; tell me whether it worked." Unlike a plain store, CAS can fail: if another thread changed the value between when this thread last read it and when it attempts the CAS, the expected value no longer matches, and the operation does nothing except report failure.

loop:
    old = read current value
    new = compute desired value from old
    if compareAndSet(old, new): return   // success
    // else: someone else moved it first — retry

This retry loop is the fundamental building block of lock-free data structures — no lock is ever held, no thread ever blocks waiting for another, but a thread can spin through many failed attempts before it succeeds.

Contention and cache-line ping-pong

Under low contention, CAS usually succeeds on the first attempt. Under contention — many threads repeatedly attempting CAS on the same location — every attempt, whether it succeeds or fails, requires the attempting core to have exclusive access to that cache line, exactly as a write does in the MESI model. When several cores constantly attempt CAS on one location, the line is repeatedly invalidated and re-fetched, core to core — the same cache-line ping-pong the False Sharing and MESI labs describe, except here it's the direct, unavoidable consequence of many threads legitimately wanting to update the same value.

More contenders does not just mean more total work — it means a higher fraction of that work is wasted retries. This is what "contention collapse" means: throughput does not merely plateau as contender count grows, it can fall, because the wasted-retry fraction grows faster than the useful-work fraction.

Backoff and jitter

None of this is universal. A backoff delay well-tuned for one contention level can be wrong for another — see "When backoff helps, and when it doesn't" below.

The single-writer alternative

CAS retry loops are not the only way to update shared state safely. If the architecture can be changed so exactly one thread ever owns the right to write a given piece of state, there is no contention to manage at all: every write succeeds on the first attempt, because nothing else is racing for it. This is not a claim that single-writer designs are always better — they trade away "any thread can update this," and moving that constraint elsewhere doesn't make the coordination problem disappear, it relocates it.

ABA, briefly

A classic CAS hazard: a thread reads value A, but before its CAS executes, another thread changes the value from A to B and back to A. The CAS still succeeds — the value is A — even though the state changed and changed back, which can silently invalidate an assumption the first thread's logic depended on. A successful CAS proves the value is currently what you expected, not that nothing happened in between. Solving this needs a versioned/tagged CAS, hazard pointers, or epoch-based reclamation — substantial topics this lab does not implement (see "Non-goals").

Fairness and starvation

A CAS retry loop makes no fairness promise. Under sustained contention, it is possible for one thread to fail repeatedly while others succeed — a bare CAS loop has no queue and no memory of who tried first, unlike a fair lock. Whether this matters depends entirely on the workload.

Java and Rust

public final class CasCounter {
    private final AtomicLong value = new AtomicLong();

    // updateAndGet already implements the retry loop internally — shown
    // manually once below to make the retry explicit, per the theory above.
    public long incrementViaBuiltin() {
        return value.updateAndGet(v -> v + 1);
    }

    public long incrementManually() {
        long old, updated;
        do {
            old = value.get();
            updated = old + 1;
        } while (!value.compareAndSet(old, updated));
        return updated;
    }
}

public final class SingleWriterCounter {
    // No CAS, no atomics — correct only because exactly one thread ever
    // calls increment(). See theory.md "The single-writer alternative".
    private long value;

    public long increment() {
        return ++value;
    }
}

use std::sync::atomic::{AtomicU64, Ordering};

pub struct CasCounter {
    value: AtomicU64,
}

impl CasCounter {
    pub fn increment_via_builtin(&self) -> u64 {
        // fetch_update already implements the retry loop internally.
        self.value.fetch_update(Ordering::SeqCst, Ordering::SeqCst, |v| Some(v + 1)).unwrap() + 1
    }

    pub fn increment_manually(&self) -> u64 {
        loop {
            let old = self.value.load(Ordering::SeqCst);
            let updated = old + 1;
            if self.value.compare_exchange(old, updated, Ordering::SeqCst, Ordering::SeqCst).is_ok() {
                return updated;
            }
            // else: someone else moved it first — retry
        }
    }
}

pub struct SingleWriterCounter {
    // No atomics needed — correct only because exactly one thread ever
    // calls increment().
    value: u64,
}

impl SingleWriterCounter {
    pub fn increment(&mut self) -> u64 {
        self.value += 1;
        self.value
    }
}

Benchmark methodology

Method: 1, 2, 4, and 8 threads, each repeatedly calling compareAndSet/compare_exchange in a retry loop against one shared counter, measuring aggregate throughput as thread count grows — contrasted against a single-writer counter touched by exactly one thread.

Java (JMH, ops/ms, higher is better):

Rust (Criterion, derived ops/ms from median batch time — batch sizes scale with thread count):

Contention collapse, unambiguously, in both languages: doubling thread count from 1→2 roughly quarters Java's throughput and cuts Rust's by a similar factor — going from zero contention to any contention at all is the steepest drop in both runs, and throughput keeps falling rather than plateauing all the way to 8 threads. The single-writer counter is dramatically faster than even uncontended CAS — roughly 3.5× in Java, and far more in Rust, where a plain non-atomic scalar increment can be optimized far more aggressively than an AtomicLong under HotSpot or a SeqCst Rust atomic. This is exactly why this lab does not present one cross-language "backoff wins by N%" number — absolute baselines differ enormously by language and JIT/compiler behavior; the shape (collapse under contention, single-writer's advantage) is what transfers. See benchmark.md in the code repository for the full write-up, including a real optimizer pitfall this benchmark hit while being built (Rust's initial single-writer measurement was a physically impossible 314.75 picoseconds — LLVM had proven the whole loop dead and eliminated it; black_box fixed it, see rust.md).

Re-run the project in code/ on your own hardware before treating any of this as authoritative for a design decision — thread count, core topology, and contention pattern all change the shape of this curve.

Common mistakes

• Assuming "lock-free" means "fast regardless of contention" — a CAS loop under heavy contention can be slower than a well-implemented lock, because every failed attempt still pays full coherence cost for zero progress.
• Adding backoff everywhere by default — under light contention, backoff only adds latency to attempts that would have succeeded immediately.
• Treating a successful CAS as proof nothing happened to the value in between — see "ABA" above.
• Reaching for a CAS retry loop when the actual fix is architectural — see "The single-writer alternative."
• Assuming CAS retry loops are fair — a thread can, in principle, lose repeatedly under sustained contention.

Investigation task

Using the Java or Rust project in code/:

1. Run the CAS-counter benchmark at 1, 2, 4, and 8 threads and record throughput at each point.
2. Plot throughput against thread count — identify the point where adding threads stops increasing throughput, or starts decreasing it (contention collapse).
3. If you have perf (Linux) or Instruments (macOS) available, look for a cache-miss or coherence-traffic counter and confirm it rises sharply at the same thread count where throughput collapses.
4. Compare against the single-writer benchmark run single-threaded — note that it isn't a fair apples-to-apples comparison (different architectures solve different problems), but observe how its cost scales (or doesn't) as you'd add more work to the same single thread.
5. Write down your CPU model and core count, your measured numbers, and explain any difference from the disclosed numbers above.

Accessibility notes

• The interactive model is fully keyboard operable: the scenario selector and the Java/Rust code tabs are roving-tabindex tablists (arrow keys, Home/End); every step/reset control is a native <button>.
• Every state change is announced to screen readers via an aria-live="polite" region, in addition to the visible per-contender status badges and the state inspector table — state is never colour-only.
• This page has no auto-playing or looping animation; step transitions resolve instantly, so there is nothing beyond the site-wide CSS rule to gate on prefers-reduced-motion.
• With JavaScript disabled, this page's theory, Java and Rust code, benchmark methodology, trade-offs and sources remain fully readable — only the interactive model and the graded quiz require script.

Review questions

Self-check before or after the graded quiz below:

1. Why can a CAS retry loop become slower, not just no-faster, as more threads contend for the same location?
2. What specifically does exponential backoff adapt to that fixed backoff does not?
3. Why doesn't a successful CAS prove nothing changed in between the thread's read and its attempt?
4. Give one condition under which adding backoff would make throughput worse, not better.

Sources

• The Art of Multiprocessor Programming — Herlihy & Shavit, Morgan Kaufmann, 2020.
• Java Concurrency in Practice — Goetz et al., Addison-Wesley, 2006.
• java.util.concurrent.atomic.AtomicLong — Java SE documentation — docs.oracle.com
• The Rust Reference — `compare_exchange`/`fetch_update` — doc.rust-lang.org/std/sync/atomic
• Exponential Backoff and Jitter — Marc Brooker, AWS Architecture Blog — aws.amazon.com/blogs/architecture
• JMH: Java Microbenchmark Harness — openjdk.org/projects/code-tools/jmh
• Criterion.rs User Guide — bheisler.github.io/criterion.rs