CAS vs Lock: Why Benchmarks Pick the Wrong Winner

This article explains why a microbenchmark comparing compare-and-swap (CAS) against a locking primitive can declare the wrong winner, and what to do about it. The short answer: benchmarks often measure uncontended throughput, ignore real-world contention, and overlook the subtle correctness and fairness properties that make locks slower in theory but more predictable in practice.

Formula

The calculator above estimates the per-operation time for a CAS-based update versus a lock-based update under a given contention level. The formulas are deliberately simple to illustrate the crossover point:

• CAS time = (1 + contention × 10) × 20 ns — assumes a base CAS cost of 20 ns and that each retry adds roughly 10 ns of overhead.
• Lock time = (1 + contention × 50) × 100 ns — assumes a base lock acquire/release cost of 100 ns and that contention adds 50 ns per operation due to queueing and context switching.
• Speedup = lock time ÷ CAS time.

These are illustrative numbers, not measured hardware constants. The point is that the ratio flips as contention rises: at low contention CAS wins; at high contention locks can win because CAS retries spin and waste CPU.

Worked Example

Using the defaults: 4 threads, 100,000 updates per thread, contention factor 0.5.

1. CAS time = (1 + 0.5 × 10) × 20 = (1 + 5) × 20 = 120 ns/op.
2. Lock time = (1 + 0.5 × 50) × 100 = (1 + 25) × 100 = 2600 ns/op.
3. Speedup = 2600 ÷ 120 = 21.67×.

At this contention level, CAS appears far faster. But if contention rises to 0.9, CAS time = (1 + 9) × 20 = 200 ns, lock time = (1 + 45) × 100 = 4600 ns — still CAS wins. The real crossover depends on actual hardware and workload, which is why microbenchmarks that ignore contention are misleading.

Background: What CAS and Locks Actually Do

Compare-and-swap is a CPU instruction that atomically compares a memory location to a given value and, if they match, writes a new value. It returns the old value so the caller can retry if the compare failed. Locks, on the other hand, use a mutual-exclusion mechanism — typically a futex on Linux or a monitor in Java — to allow only one thread into a critical section at a time. The fundamental difference is that CAS is optimistic: it assumes no conflict and retries on failure. Locks are pessimistic: they force waiting threads to block or spin until the lock is free.

This difference drives the benchmark problem. A typical microbenchmark runs a tight loop of CAS operations on a single memory location or a lock-protected increment. With one thread, both are trivial. With multiple threads but no actual contention (e.g., each thread works on its own variable), CAS wins because it has no kernel involvement. But the benchmark may not simulate the real contention pattern of the production workload.

Why Benchmarks Pick the Wrong Winner

There are several common reasons a benchmark can mislead:

• Uncontended baseline: Many benchmarks run with few threads or on separate data, so locks never actually block. The lock overhead is just atomic increment plus a syscall-free fast path — which can be nearly as fast as CAS.
• Oversubscription: When threads outnumber CPU cores, locks cause context switching, which is expensive. CAS retries also waste CPU, but the benchmark may not show the system-wide throughput drop.
• Cache effects: CAS on a single shared variable causes cache-line ping-ponging. Locks with a queue (like a mutex) can reduce ping-pong because only the lock holder touches the data. A benchmark that doesn’t measure cache misses misses this.
• Fairness and starvation: CAS loops can starve a thread if others keep winning. Locks usually guarantee eventual progress. A benchmark that only measures total operations may hide the fact that one thread made no progress.
• Amdahl’s law: If the critical section is short, CAS wins; if it’s long, locks win because CAS retries become more likely. The benchmark’s critical section length may not match your code.

How to Read a Benchmark Result

When you see a benchmark claiming “CAS is 10× faster than locks�, ask three questions:

1. How many threads and cores were used? If threads ≤ cores and each thread has a private variable, it’s not a concurrency test.
2. What was the contention level? Did the benchmark actually make threads fight over the same data, or did it use a striped/partitioned design?
3. What metric was reported? Throughput (ops/sec) can hide latency spikes. A lock may have higher average latency but better tail latency under load.

Also check whether the benchmark used a fair lock (e.g., a ticket lock) or an unfair one. Unfair locks can be faster but cause starvation. CAS has no fairness guarantee at all.

Common Misconceptions

“CAS is always lock-free and therefore always faster.� CAS is lock-free in the sense that no thread blocks, but it can still cause livelock — threads spinning forever without progress. Under high contention, the retry loop consumes CPU and can degrade overall system performance.

“Locks always block and are slow.� Modern mutexes use a fast path (atomic compare-and-set on the lock word) and only call the kernel when contention is detected. So an uncontended lock acquire can be nearly as cheap as a CAS. The cost appears when threads actually wait.

“One benchmark can decide the choice.� No. The right choice depends on the critical section size, the number of threads relative to cores, the frequency of updates, and the acceptable latency distribution. A microbenchmark can only tell you about its own synthetic workload.

How to Choose Between CAS and Locks

Use CAS when:

• The critical section is very short (a few instructions).
• Contention is expected to be low or moderate.
• You can tolerate retries and have no fairness requirement.
• You are implementing a lock-free data structure (e.g., a stack or queue).

Use locks when:

• The critical section is long (I/O, complex computation).
• Contention is high and threads would spin too much.
• You need fairness or guaranteed progress.
• Your code is already complex and you want to avoid subtle memory-ordering bugs.

In practice, many systems use a hybrid: a lock-free fast path with a fallback to a lock when contention is detected (e.g., a striped lock or a seqlock).

Alternatives to Both

There are other synchronization primitives that can outperform both CAS and locks in specific scenarios:

• Read-copy-update (RCU): Allows readers to proceed without locks while writers make a copy and swap a pointer. Great for read-heavy workloads.
• Seqlocks: Readers don’t block, but they retry if a writer updated a sequence counter. Good for data that is mostly read.
• Transactional memory: Hardware or software transactions that commit atomically. Not widely available in mainstream CPUs, but research continues.
• Atomics with relaxed ordering: For some counters, you don’t need full sequential consistency; relaxed atomics can be faster than CAS.

Each alternative has its own trade-offs, and none is universally better.

Frequently Asked Questions

Q: Why does my benchmark show CAS is faster, but my real program is slower?
A: Your benchmark probably used low contention or separate variables. In a real program, threads share data, causing cache-line contention and retries. Also, the benchmark may not include the cost of the surrounding code, which can dominate.

Q: Can CAS cause deadlock?
A: No, CAS cannot deadlock because it never blocks. But it can cause livelock — threads spinning forever without progress. This is rare but possible under extreme contention.

Q: Are locks always fair?
A: No. Many mutex implementations are not fair — they may allow a thread to “barge� ahead of waiting threads. If you need strict FIFO ordering, use a ticket lock or a fair queue.

Q: What is the actual cost of a CAS instruction?
A: It varies by CPU and memory model. On x86, a locked CAS can be around 20-50 ns when uncontended, but can be 100+ ns under contention due to cache coherence traffic. ARM and RISC-V have different costs.

Q: Should I always use a lock-free algorithm if I can?
A: No. Lock-free algorithms are harder to reason about and debug. If the performance gain is small and the risk of subtle bugs is high, a well-implemented lock is often better. Measure with a realistic workload first.

Q: How can I benchmark correctly?
A: Use as many threads as your production system, share the same data, and measure both throughput and latency percentiles. Run for a long enough time to warm up JIT or caches. Also test with different contention levels (e.g., 1, 2, 4, 8, 16 threads) and report the scaling curve.

Related

• Smart Home Habits Raising Electricity Bill?
• How to Clean a Foldable Phone Hinge Safely
• Run Qwen3 8B/27B with Longer Context on Limited VRAM

in t | Threads | threads | 4 | 1 | 64
in u | Updates per thread | ops | 100000 | 1 | 10000000
in c | Contention factor (0-1) | - | 0.5 | 0 | 1
out cas_ns | CAS estimated time | ns/op | (1 + c * 10) * 20 | 0
out lock_ns | Lock estimated time | ns/op | (1 + c * 50) * 100 | 0
out ratio | CAS speedup vs lock | x | lock_ns / cas_ns | 2