Fetch, Modify, Exchange: Advanced Atomics for Fearless Lock-Free Programming

If basic atomics (load and store) are the stop flags and progress counters of the concurrency world, advanced atomics (fetch_add, fetch_sub, compare_exchange) are the building blocks of lock-free algorithms—data structures and coordination patterns that achieve thread safety without ever acquiring a lock. No contention. No deadlocks. No priority inversion. Just hardware-level instructions that read, modify, and write values in a single indivisible operation.

The jump from basic to advanced atomics is the jump from "I can set a flag" to "I can build a concurrent counter, a lock-free stack, or a work-stealing queue." It's also the jump from "I understand Relaxed ordering" to "I need to think about Acquire/Release semantics." But don't let that intimidate you—the practical patterns are straightforward, and the payoff in performance-critical code is substantial.

At RantAI, advanced atomics power our concurrent ID generators, work distribution systems, and statistics collectors—hot paths where mutex contention would be a bottleneck. This article, drawn from Chapter 5, Section 5.2.3 of our guide "The Rust Programming Language," covers fetch_add, compare_exchange, and the patterns that make lock-free programming practical.

fetch_add: The Atomic Counter That Replaces Mutex<i32>#

use std::sync::atomic::{AtomicUsize, Ordering::Relaxed};
use std::sync::Arc;
use std::thread;

fn main() {
    let counter = Arc::new(AtomicUsize::new(0));
    let mut handles = vec![];

    for _ in 0..10 {
        let counter = Arc::clone(&counter);
        handles.push(thread::spawn(move || {
            for _ in 0..1000 {
                counter.fetch_add(1, Relaxed);  // Atomic increment
            }
        }));
    }

    for handle in handles {
        handle.join().unwrap();
    }

    println!("Final count: {}", counter.load(Relaxed));  // Always 10000
}

fetch_add(1, Relaxed) atomically reads the current value, adds 1, stores the result, and returns the previous value—all in a single CPU instruction. Ten threads each incrementing 1000 times always produces exactly 10000. No mutex. No lock. No contention.

The fetch_ family includes fetch_add, fetch_sub, fetch_or, fetch_and, fetch_xor, and fetch_max/fetch_min. Each performs a read-modify-write operation atomically.

Practical Pattern: Atomic ID Generator#

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

static NEXT_ID: AtomicU64 = AtomicU64::new(1);

fn generate_id() -> u64 {
    NEXT_ID.fetch_add(1, Relaxed)  // Returns the ID BEFORE incrementing
}

fn main() {
    // Safe to call from any thread, any time — always unique
    println!("ID: {}", generate_id());  // 1
    println!("ID: {}", generate_id());  // 2
    println!("ID: {}", generate_id());  // 3
}

Global, thread-safe, lock-free ID generation. Each call returns a unique ID. No mutex, no contention, no ordering concerns. This pattern is used in logging systems, request tracking, and anywhere you need unique identifiers in a concurrent environment.

compare_exchange: The Foundation of Lock-Free Algorithms#

compare_exchange (CAS—Compare And Swap) is the most powerful atomic operation. It atomically checks if a value equals an expected value, and if so, replaces it with a new value. If the value has changed (another thread modified it), the operation fails and returns the current value.

use std::sync::atomic::{AtomicU32, Ordering::Relaxed};

fn main() {
    let value = AtomicU32::new(5);

    // Try to change 5 → 10 (succeeds because current value IS 5)
    match value.compare_exchange(5, 10, Relaxed, Relaxed) {
        Ok(prev) => println!("Changed {} to 10", prev),   // "Changed 5 to 10"
        Err(actual) => println!("Expected 5, found {}", actual),
    }

    // Try to change 5 → 20 (fails because current value is now 10, not 5)
    match value.compare_exchange(5, 20, Relaxed, Relaxed) {
        Ok(prev) => println!("Changed {} to 20", prev),
        Err(actual) => println!("Expected 5, found {}", actual),  // "Expected 5, found 10"
    }
}

The CAS Retry Loop: The Canonical Pattern#

use std::sync::atomic::{AtomicU32, Ordering::Relaxed};

fn atomic_multiply(value: &AtomicU32, multiplier: u32) {
    let mut current = value.load(Relaxed);
    loop {
        let new = current * multiplier;
        match value.compare_exchange(current, new, Relaxed, Relaxed) {
            Ok(_) => break,           // Success — value was updated
            Err(actual) => current = actual,  // Another thread changed it — retry
        }
    }
}

The CAS retry loop is the fundamental pattern of lock-free programming: load the current value, compute the new value, try to swap. If another thread changed the value between your load and your CAS, retry with the updated value. This loop always terminates (assuming finite contention) and never locks.

Arc: Shared Ownership for Cross-Thread Data#

While not strictly an atomic operation, Arc<T> (Atomic Reference Counting) deserves mention because it's the standard way to share owned data across threads:

use std::sync::Arc;
use std::thread;

fn main() {
    let data = Arc::new(vec![1, 2, 3, 4, 5]);

    let mut handles = vec![];
    for i in 0..5 {
        let data = Arc::clone(&data);  // Atomic reference count increment
        handles.push(thread::spawn(move || {
            println!("Thread {} sum: {}", i, data.iter().sum::<i32>());
        }));
    }

    for handle in handles {
        handle.join().unwrap();
    }
    // When all Arcs are dropped, the data is freed — exactly once
}

Arc::clone atomically increments a reference count. When each Arc is dropped, the count is atomically decremented. When it reaches zero, the data is freed. All using atomic operations—no mutex, no GC, deterministic deallocation.

Memory Ordering: When Relaxed Isn't Enough#

For the CAS patterns above, Relaxed is often sufficient because the CAS itself provides the necessary atomicity. But when you're using atomics to coordinate access to non-atomic data, you need Acquire/Release:

use std::sync::atomic::{AtomicBool, Ordering::{Acquire, Release}};

static DATA_READY: AtomicBool = AtomicBool::new(false);
static mut SHARED_DATA: u64 = 0;  // Non-atomic — protected by the flag

fn producer() {
    unsafe { SHARED_DATA = 42; }          // Write the data first
    DATA_READY.store(true, Release);       // Then signal "data is ready"
    // Release ensures the data write is visible before the flag
}

fn consumer() {
    while !DATA_READY.load(Acquire) {}     // Wait for the signal
    // Acquire ensures we see the data written before the flag
    let value = unsafe { SHARED_DATA };
    println!("Got: {}", value);            // Guaranteed to print 42
}

Release on store ensures all writes before the store are visible to any thread that Acquire-loads the value. This is the "publish" pattern—write data, then release-store a flag to signal it's ready.

Broader Implications: Building Blocks for High-Performance Systems#

Advanced atomics are the foundation of lock-free data structures that power high-performance concurrent systems: concurrent queues, lock-free hash maps, work-stealing schedulers. Libraries like crossbeam build on these primitives to provide safe, high-level concurrent data structures.

At RantAI, we use fetch_add for statistics and ID generation, compare_exchange for lock-free state transitions, and Arc for shared ownership everywhere. The combination provides high-throughput concurrent coordination without the overhead or complexity of mutex-based synchronization.

Practical Applications & Strategic Takeaways#

For newcomers: fetch_add replaces Mutex<i32> for counters. Arc replaces Rc for cross-thread shared ownership. Master these two before diving into CAS.

For performance engineers: CAS retry loops are the foundation of lock-free algorithms. They're more complex than mutexes but eliminate contention entirely. Use them for hot-path state transitions.

For architects: Layer your concurrency primitives: fetch_add for counters, CAS for state machines, Mutex for complex state, RwLock for read-heavy state. Each has its optimal use case.

Our Commitment to Open Knowledge#

RantAI is committed to open education. Advanced atomics are covered in Chapter 5, Section 5.2.3 of our guide, "The Rust Programming Language," freely available online.

Explore these concepts further: https://trpl.rantai.dev

Support Our Mission & Get Your Handbook#

• Get the Handbook on Amazon KDP: https://www.amazon.com/dp/B0DHCMD3F2

• Get the Handbook on Google Play Books: https://play.google.com/store/books/details?id=INwfEQAAQBAJ

Have you built lock-free data structures with CAS? What was your experience with the retry loop pattern? Share below!

#RustLang #Atomics #LockFree #CAS #CompareAndSwap #RantAI #LearnRust #Performance #Concurrency #SystemsProgramming