Introduction

Compare-and-swap, usually abbreviated as CAS, is a core atomic primitive for lock-free programming in C++11 and later. It lets a thread update shared state only if that state still equals an expected value. In modern C++ this is exposed through std::atomic and compare_exchange_weak or compare_exchange_strong.

CAS Semantics in C++11

CAS compares an atomic value with expected. If they match, it writes desired atomically and returns true. If they do not match, it writes the current atomic value back into expected and returns false.

That second behavior matters. Many bugs come from forgetting that expected is modified on failure.

Basic example:

1#include <atomic>
2#include <iostream>
3
4int main() {
5    std::atomic<int> value{10};
6    int expected = 10;
7    int desired = 42;
8
9    bool ok = value.compare_exchange_strong(expected, desired);
10
11    std::cout << "success: " << ok << "\n";
12    std::cout << "value: " << value.load() << "\n";
13    std::cout << "expected after call: " << expected << "\n";
14}

On success, value becomes 42. On failure, expected becomes the observed value.

weak Versus strong

compare_exchange_strong fails only on genuine mismatch. compare_exchange_weak may fail spuriously, which means it can return false even when values match. Spurious failure is allowed so some architectures can generate faster instructions.

Practical rule:

• use strong when attempting once
• use weak in retry loops

Typical weak loop pattern:

1#include <atomic>
2#include <iostream>
3
4int main() {
5    std::atomic<int> counter{0};
6
7    for (int i = 0; i < 1000; ++i) {
8        int expected = counter.load(std::memory_order_relaxed);
9        while (!counter.compare_exchange_weak(
10            expected,
11            expected + 1,
12            std::memory_order_release,
13            std::memory_order_relaxed)) {
14            // expected is refreshed automatically on failure
15        }
16    }
17
18    std::cout << "counter: " << counter.load() << "\n";
19}

The loop retries until update succeeds.

Memory Ordering and CAS

CAS operations support memory order arguments. This controls visibility guarantees between threads. Many lock-free bugs come from incorrect memory ordering choices.

Common pair:

• success: memory_order_release or memory_order_acq_rel
• failure: memory_order_relaxed or memory_order_acquire

For beginners, memory_order_seq_cst is simpler and safer, though potentially slower.

1std::atomic<int> x{0};
2int expected = 0;
3bool ok = x.compare_exchange_strong(
4    expected,
5    1,
6    std::memory_order_seq_cst,
7    std::memory_order_seq_cst
8);

Use explicit orderings only when you understand the synchronization graph you need.

Lock-Free Stack Push Example

CAS is often used to update linked-list heads in lock-free structures.

1#include <atomic>
2#include <iostream>
3
4struct Node {
5    int value;
6    Node* next;
7};
8
9std::atomic<Node*> head{nullptr};
10
11void push(int v) {
12    Node* node = new Node{v, nullptr};
13    node->next = head.load(std::memory_order_relaxed);
14    while (!head.compare_exchange_weak(
15        node->next,
16        node,
17        std::memory_order_release,
18        std::memory_order_relaxed)) {
19    }
20}
21
22int main() {
23    push(1);
24    push(2);
25    Node* h = head.load(std::memory_order_acquire);
26    while (h) {
27        std::cout << h->value << "\n";
28        h = h->next;
29    }
30}

This demonstrates the classic retry pattern, though full production code must also handle safe memory reclamation.

Real-World Concerns

CAS is powerful but not a universal replacement for mutexes. Under heavy contention, constant retries can waste CPU and reduce throughput. Lock-based approaches can be better for fairness or complex multi-step critical sections.

Another concern is ABA problems in pointer-based lock-free structures. A value can change from A to B and back to A, causing CAS to succeed even though intermediate state existed. Techniques such as tagged pointers or hazard pointers are used to mitigate this.

Common Pitfalls

• Forgetting that expected is overwritten when CAS fails.
• Using compare_exchange_weak once without a retry loop.
• Choosing memory orders inconsistently across related loads and stores.
• Assuming lock-free code is always faster under high contention.
• Ignoring ABA and reclamation issues in pointer-based designs.

Summary

• CAS atomically updates a value only when expected and current values match.
• strong is for single-attempt semantics, weak is for retry loops.
• Memory ordering is part of correctness, not only performance.
• CAS enables lock-free patterns but adds complexity around contention and reclamation.
• Use CAS intentionally where its trade-offs are justified.