Compare-Exchange & Lock-Free Algorithms

Compare-exchange (CAS) operations are the foundation of lock-free programming. They allow you to atomically check if a shared variable's value in the current thread matches an expected value and update it if it does, all in a single operation.

The Problem: Race Conditions in Complex Operations

Consider updating a shared variable based on its current value:

std::atomic<int> counter{0};

void increment_if_even() {
    int current = counter.load();
    if (current % 2 == 0) {
        counter.store(current + 1);  // Race condition!
    }
}

Problem: Between reading and writing, another thread might change the value.

The Solution: Compare-Exchange

Compare-exchange atomically checks and updates a value. Internally, you can think of it as a single instruction that performs the following steps:

def compare_exchange(expected, desired):
    current_value = load(counter)
    if (current_value == expected) {
        store(counter, desired)
        return true
    } else {
        expected = current_value
        return false
    }

Above, you can see that compare-exchange is provided with an expected value of the shared variable which was likely fetched from a load operation previously. Then an operation is done on the expected value, which is only stored back to memory if the shared variable's value hasn't been changed by another thread.

In case the shared variable's value has been changed by another thread, compare_exchange fails and the current value is loaded into the expected variable of the current thread. The current thread can then retry the operation with the new expected value.

In practice, this looks like the following:

std::atomic<int> counter{0};

void increment_if_even() {
    int expected = counter.load();
    while (expected % 2 == 0) {
        if (counter.compare_exchange_strong(expected, expected + 1)) {
            break;  // Successfully updated
        }
        // compare-exchange failed, expected now contains the current value, try again
    }
}

Using compare_exchange_strong allows you to do work that is visible only to the current thread and then make it visible to other threads in a single atomic instruction without requiring any mutexes.

Basic Compare-Exchange Patterns

1. Simple Update

std::atomic<int> value{0};

void set_if_zero(int new_value) {
    int expected = 0;
    value.compare_exchange_strong(expected, new_value);
}

2. Conditional Update

std::atomic<int> max_value{0};

void update_max(int candidate) {
    int current = max_value.load();
    while (candidate > current) {
        if (max_value.compare_exchange_strong(current, candidate)) {
            break;  // Successfully updated
        }
        // current was updated with actual value, retry if needed
    }
}

3. Atomic Swap

std::atomic<int> value{42};

int swap_value(int new_value) {
    int old_value = value.load();
    while (!value.compare_exchange_strong(old_value, new_value)) {
        // old_value was updated, retry
    }
    return old_value;
}

The above is example is very important since it shows how a new value can be computed by a thread and then swapped into the shared variable in a single atomic instruction.

Common Patterns

1. Try-Once Pattern

std::atomic<bool> flag{false};

bool try_set_flag() {
    bool expected = false;
    return flag.compare_exchange_strong(expected, true);
}

2. Retry Loop Pattern

std::atomic<int> counter{0};

void increment() {
    int expected = counter.load();
    while (!counter.compare_exchange_strong(expected, expected + 1)) {
        // expected was updated, retry
    }
}

3. Load-Compare-Exchange Pattern

std::atomic<int> value{0};

void update_if_positive() {
    int expected = value.load();
    while (expected > 0) {
        if (value.compare_exchange_strong(expected, expected * 2)) {
            break;  // Successfully updated
        }
        // expected was updated, check if still positive
    }
}

Performance Considerations

Compare-Exchange vs Mutex

Operation	Mutex	Compare-Exchange	Speed Improvement
Simple update	~100ns	~10ns	~10x faster
Complex update	~100ns	~20ns	~5x faster

When to Use Each

Use Compare-Exchange for:

• Simple atomic updates
• Lock-free data structures
• Performance-critical sections
• When you need non-blocking operations

Use Mutexes for:

• Complex critical sections
• When you need condition variables
• When code clarity is more important than performance

Implement a lock-free stack using compare_exchange_strong. The stack should support push and pop operations without using any mutexes.

#include <atomic>

template<typename T>
class LockFreeStack {
private:
    struct Node {
        T data;
        Node* next;
        Node(T d) : data(d), next(nullptr) {}
    };

    std::atomic<Node*> head{nullptr};

public:
    void push(T value) {
        // TODO: Implement lock-free push using compare_exchange_strong
        // Create a new node and atomically update the head pointer
        // Use a loop to handle concurrent modifications
    }

    bool pop(T& result) {
        // TODO: Implement lock-free pop using compare_exchange_strong
        // Atomically read the head and update it to the next node
        // Return true if successful, false if stack was empty
        // Handle the case where head becomes null
        return false;
    }
};