Compare-and-Swap Algorithms

In this lesson, you will learn how to implement lock-free synchronization using the Compare-and-Swap (CAS) pattern to update shared state without traditional mutexes.

The CAS Concept

At the CPU level, a Compare-and-Swap operation is an atomic instruction that performs a conditional update: "If the value at this memory address is still what I think it is, change it to this new value; otherwise, do nothing."

In Rust, we achieve this using the compare_exchange method available on Atomic types. Instead of locking a thread, CAS allows a thread to attempt an update and verify success. If the check fails—because another thread modified the data first—the operation returns an Err containing the current value, allowing you to retry the logic.

Implementing a Lock-Free Counter

Imagine you want to increment a value without a Mutex. You don't simply read and add; you must ensure the value hasn't changed between the read and the write.

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

fn increment(atomic: &AtomicUsize) {
    let mut current = atomic.load(Ordering::Relaxed);
    loop {
        let new = current + 1;
        // Attempt to swap: only succeed if the value is still 'current'
        match atomic.compare_exchange(
            current, 
            new, 
            Ordering::SeqCst, 
            Ordering::Relaxed
        ) {
            Ok(_) => break, // Success!
            Err(actual) => current = actual, // Update 'current' and retry
        }
    }
}

Why this matters

In lock-based designs (Mutex), threads wait in line, leading to context switches and potential priority inversion. With CAS, threads "optimistically" attempt an operation. In low-contention scenarios, this is significantly faster. However, if many threads fight for the same memory location, the loop may spin repeatedly, wasting CPU cycles. This is why CAS is the foundation for building high-performance, non-blocking data structures like lock-free queues and stacks.

Key Takeaway: Compare-and-Swap allows you to perform atomic updates by optimistically assuming success and gracefully retrying if the underlying memory has changed since your last read.