Learn Rust Series (#66) - Atomics: AtomicUsize, fetch_add, and Compare-and-Swap

avatar

Learn Rust Series (#66) - Atomics: AtomicUsize, fetch_add, and Compare-and-Swap

rust-banner.png

What will I learn

  • You will learn what an atomic type is: a value the hardware can read-modify-write without tearing;
  • how AtomicUsize and friends replace a Mutex for a single shared number, with no lock and nothing to poison;
  • what fetch_add, load, and store do, and why they are indivisible across threads;
  • what compare-and-swap (compare_exchange) is, and why it is the atom every lock-free algorithm is built from;
  • the CAS-loop pattern for building any read-modify-write operation the hardware does not give you directly.

Requirements

  • A working modern computer running macOS, Windows or Ubuntu;
  • An installed Rust toolchain (via rustup, from rustup.rs);
  • The previous sixty-five episodes, especially Arc, Mutex, and threads;
  • The ambition to learn systems programming from the ground up.

Difficulty

  • Intermediate

Curriculum (of the Learn Rust Series):

Learn Rust Series (#66) - Atomics: AtomicUsize, fetch_add, and Compare-and-Swap

At the very end of the last episode I left you with a nagging little question, and I promised we would open it up today. When two threads race to lock() the same Mutex, something has to decide who wins -- and it cannot be another lock, or we would have an infinite regress of locks-protecting-locks. So what is at the bottom? What does the CPU itself offer that lets a program build a mutex in the first place? The answer is the subject of this episode: the atomic operation, the smallest indivisible unit of shared-memory coordination there is. Every lock, every channel, every reference count in Arc (episode 34), and every lock-free data structure we build in the next two episodes bottoms out in atomics. This is bedrock. Below it there is only the hardware ;-)

The word "atomic" comes from the Greek for indivisible, and that is exactly the guarantee. An atomic operation is one that the CPU performs as a single, uninterruptible step: no other thread can ever observe it half-finished. That sounds modest, but it is the whole ballgame, because -- as we are about to see -- the reason ordinary shared-memory code is so dangerous is precisely that the operations we think of as single steps are secretly three or four steps, and another thread can wedge itself into the gaps. Atomics close the gaps.

First, though, as always, last episode's homework.

Solutions to Episode 65 Exercises

Episode 65 was Mutex, RwLock, and lock poisoning. All three exercises exercised the Arc<Mutex<T>> idiom and its read-write cousin.

Exercise 1 asked you to wrap a counter in Arc<Mutex<i32>>, increment it from ten threads, join them all, and print the exact total:

use std::sync::{Arc, Mutex};
use std::thread;

fn main() {
    let counter = Arc::new(Mutex::new(0));
    let mut handles = Vec::new();
    for _ in 0..10 {
        let c = Arc::clone(&counter);           // bump the refcount, not the data
        handles.push(thread::spawn(move || {
            *c.lock().unwrap() += 1;            // lock, add, release at the semicolon
        }));
    }
    for h in handles { h.join().unwrap(); }
    println!("{}", *counter.lock().unwrap());   // 10, exactly, every run
}

The key insight is that the Mutex serialises the ten += 1 operations, so no update is ever lost. The temporary guard on the increment line is dropped at the semicolon, releasing the lock immediately -- exactly the "hold it briefly" habit we talked about. Hang on to this example: in a few paragraphs we do the very same job with no lock at all.

Exercise 2 wanted an RwLock<Vec<i32>> shared across a thread::scope, with three reader threads printing the length while one writer pushes a value, then a print of the final contents:

use std::sync::RwLock;
use std::thread;

fn main() {
    let data = RwLock::new(vec![1, 2, 3]);
    thread::scope(|s| {
        for _ in 0..3 {
            s.spawn(|| {
                let r = data.read().unwrap();          // many readers at once
                println!("reader sees {} items", r.len());
            });
        }
        s.spawn(|| {
            data.write().unwrap().push(4);             // one exclusive writer
        });
    });
    println!("final: {:?}", *data.read().unwrap());    // final: [1, 2, 3, 4]
}

Because thread::scope (episode 62) guarantees every spawned thread finishes before the scope returns, the closures can borrow data directly with no Arc in sight. The exact interleaving of the prints varies from run to run -- that is concurrency being honest with you -- but the readers never tear and the writer never overlaps them.

Exercise 3 was the poisoning drill: panic on purpose while holding a guard, catch the panic with join, then recover the inner value with into_inner:

use std::sync::{Arc, Mutex};
use std::thread;

fn main() {
    let data = Arc::new(Mutex::new(0));
    let d = Arc::clone(&data);
    let _ = thread::spawn(move || {
        let mut g = d.lock().unwrap();
        *g = 42;
        panic!("crash while holding the lock");   // poisons the Mutex
    }).join();                                     // join swallows the panic

    let value = match data.lock() {
        Ok(g) => *g,
        Err(poisoned) => *poisoned.into_inner(),   // deliberately recover
    };
    println!("recovered value: {value}");          // recovered value: 42
}

The into_inner() on the PoisonError is the one conscious line that says "yes, I know a holder panicked, and I have decided this value is fine to use". That is poisoning working as designed: it does not hide the data, it makes you sign for it. Right, homework cleared -- now, atomics.

An atomic value

An atomic type wraps a single primitive and exposes operations the CPU performs indivisibly. The standard library gives you a family of them in std::sync::atomic: AtomicUsize, AtomicIsize, AtomicU8 through AtomicU64, AtomicBool, and AtomicPtr. The two most basic operations are store (write a value) and load (read it back), and both take an extra argument -- an Ordering -- which describes the memory guarantees around the operation. We will treat Ordering as a black box marked Relaxed for now and open it up properly next episode; today, focus on the indivisibility, not the ordering:

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

fn main() {
    let counter = AtomicUsize::new(0);
    counter.store(10, Ordering::Relaxed);
    let current = counter.load(Ordering::Relaxed);
    println!("{current}"); // 10
}

Notice what is not here. There is no guard, no lock(), no Result, and nothing that can be poisoned. The type itself is the synchronisation -- the atomicity is baked into the operation, not bolted on with a separate lock object. Where a Mutex<usize> is a lock plus a value plus a poison flag plus a guard, an AtomicUsize is just a usize the hardware promises to touch cleanly. For a single number, that is an enormous simplification.

One subtle but important point: the atomic methods take &self, not &mut self. You can mutate an atomic through a shared reference. That is interior mutability (episode 32), the same idea as Cell and RefCell, except where RefCell enforces its borrow rules at runtime with a counter (and is not thread-safe), the atomic enforces nothing at the type level and instead leans on the hardware to make concurrent mutation safe. This is exactly why atomics are Sync (episode 61) while Cell is not.

fetch_add: the atomic counter

Here is the crux of the whole matter. Why does a plain counter += 1 race across threads? Because that innocent-looking line is really three machine steps: read the current value into a register, add one, write the result back. If two threads both read 7, both compute 8, and both write 8, then two increments have produced a single increase -- one update vanished into thin air. That lost-update bug is the classic data race, and it is why exercise 1 above needed a Mutex at all.

fetch_add fuses those three steps into one indivisible operation. It adds the given amount to the atomic and returns the previous value, and no other thread can interleave in the middle. So many threads hammering the same counter never lose an update, with no lock anywhere:

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

fn main() {
    let counter = Arc::new(AtomicUsize::new(0));
    let mut handles = Vec::new();
    for _ in 0..8 {
        let c = Arc::clone(&counter);
        handles.push(thread::spawn(move || {
            for _ in 0..1000 {
                c.fetch_add(1, Ordering::Relaxed); // atomic read-modify-write, no lock
            }
        }));
    }
    for h in handles { h.join().unwrap(); }
    println!("{}", counter.load(Ordering::Relaxed)); // 8000, exactly
}

Compare this line-for-line with the Mutex counter from exercise 1. Same shape, same Arc for shared ownership, same exact answer -- but no lock(), no guard, no unwrap, and no poisoning to reason about. Under heavy contention the atomic version is also usually faster, because it never puts a thread to sleep: fetch_add typically compiles down to a single locked machine instruction (lock xadd on x86), whereas a Mutex may involve a system call to park and wake a waiting thread.

The fetch_* family is broad: fetch_sub, fetch_or, fetch_and, fetch_xor, fetch_max, fetch_min. Every one of them is a complete read-modify-write the hardware supports directly, returning the old value so you can see what you changed. If your shared state is one integer or one bitfield, one of these is very likely all you need.

Compare-and-swap: the lock-free atom

But the hardware only offers a fixed menu of read-modify-write operations. What if you want an operation that is not on the menu -- say, "multiply the counter by three" or "set it to the larger of itself and my candidate"? For that there is one operation that can express every read-modify-write there is, and it is the single most important primitive in all of concurrent programming: compare-and-swap, spelled compare_exchange in Rust.

The idea reads almost like a sentence: "if the value is still what I expect it to be, replace it with this new value; otherwise, do nothing and tell me what it actually is". It takes an expected value, a new value, and two orderings (one for success, one for failure -- ignore them for now):

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

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

    let result = value.compare_exchange(5, 10, Ordering::SeqCst, Ordering::SeqCst);
    println!("{:?}", result);                      // Ok(5): it was 5, so it is now 10
    println!("{}", value.load(Ordering::SeqCst));  // 10

    let failed = value.compare_exchange(5, 20, Ordering::SeqCst, Ordering::SeqCst);
    println!("{:?}", failed);                      // Err(10): it was not 5, no change made
}

Read the return type carefully, because it is doing a lot of work. On success you get Ok(old_value); on failure you get Err(actual_value). Either way you learn the value that was there when the operation ran. That is the whole trick: compare-and-swap lets a thread attempt a change conditionally, and find out atomically whether it succeeded or whether someone else got there first. From that one conditional swap, every lock-free algorithm ever written is assembled.

The CAS loop

A single compare_exchange on its own is a bit like a single if. It becomes a general-purpose tool through the CAS loop (CAS = compare-and-swap): read the current value, compute the new value from it, and try to swap it in; if someone changed the value out from under you between the read and the swap, the swap fails and hands you the fresh value, so you just loop and try again with the new starting point. This pattern builds any atomic read-modify-write, even ones the hardware does not offer directly. Here is an atomic "raise to at least this much", a max-update that the plain fetch_max happens to give us but which is worth building by hand to see the machinery:

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

fn atomic_raise_to(a: &AtomicI64, candidate: i64) -> i64 {
    let mut current = a.load(Ordering::Relaxed);
    loop {
        if candidate <= current {
            return current; // already big enough, nothing to do
        }
        match a.compare_exchange_weak(current, candidate, Ordering::Relaxed, Ordering::Relaxed) {
            Ok(prev) => return prev,          // we won the race, our value is in
            Err(actual) => current = actual,  // someone else changed it; retry with their value
        }
    }
}

fn main() {
    let max = AtomicI64::new(3);
    atomic_raise_to(&max, 7);
    atomic_raise_to(&max, 5); // 5 < 7, so no change
    println!("{}", max.load(Ordering::Relaxed)); // 7
}

Trace one iteration and the pattern is clear: we snapshot current, decide what we want, and ask the hardware to install it only if nobody moved the value in the meantime. If the swap fails, we do not panic and we do not block -- we simply update our snapshot to the value the hardware just handed us and go round again. That is what "lock-free" means in practice: threads never wait on each other, they retry.

You will notice I used compare_exchange_weak inside the loop rather than plain compare_exchange. The weak variant is allowed to fail spuriously -- to report failure even when the value did match -- because on some CPU architectures (ARM, for instance) that is dramatically cheaper to implement. Inside a retry loop a spurious failure is completely harmless: you just loop once more. So the rule of thumb is: use compare_exchange_weak when you are already in a loop, and reserve the strong compare_exchange for a one-shot attempt where a spurious failure would be a bug. Small distinction, real performance difference on the right hardware.

AtomicBool as a flag

Not every atomic is a counter. The simplest genuinely useful one is a boolean flag, and it is perfect for signalling a worker thread to stop -- no lock, no channel, no ceremony, just one shared bool the hardware lets you flip safely:

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

fn main() {
    let stop = Arc::new(AtomicBool::new(false));
    let worker_stop = Arc::clone(&stop);
    let worker = thread::spawn(move || {
        let mut ticks = 0u64;
        while !worker_stop.load(Ordering::Relaxed) {
            ticks += 1;
            if ticks > 1_000_000 { break; } // guard so the example always terminates
        }
        ticks
    });
    stop.store(true, Ordering::Relaxed); // tell the worker to wind down
    let ticks = worker.join().unwrap();
    println!("worker ran and then stopped: {}", ticks > 0); // true
}

This "shutdown flag" is one of the most common atomic patterns in real systems: a long-running loop checks a flag each iteration, and any other thread can raise the flag to ask it to stop. There is a closely related method, swap, which atomically stores a new value and returns the old one -- handy for a one-shot "claim" where only the very first thread to flip false to true should win. And compare_exchange on an AtomicBool gives you the same claim with an explicit success/failure result, which is exactly one of today's exercises.

Atomic or Mutex

So when do you reach for an atomic, and when for a Mutex? Both protect shared mutable state, and the deciding question is scope. An atomic guards exactly one primitive value, with a single indivisible operation per touch. A Mutex (episode 65) guards an arbitrarily large, multi-field structure across a whole critical section of many operations:

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

fn main() {
    let with_mutex = Mutex::new(0usize);
    *with_mutex.lock().unwrap() += 1;          // lock, mutate, unlock

    let with_atomic = AtomicUsize::new(0);
    with_atomic.fetch_add(1, Ordering::Relaxed); // one indivisible step

    // same result; the atomic needs no lock, no guard, and cannot be poisoned
    println!("{} {}", *with_mutex.lock().unwrap(), with_atomic.load(Ordering::Relaxed)); // 1 1
}

The rule I carry in my head is simple. If the shared state is a single counter, a single flag, or a single pointer, reach for an atomic -- it is smaller, faster, and has no poisoning to worry about. The moment consistency has to span more than one value -- "increment this counter and push to that Vec, and both must be seen together" -- reach for a Mutex, because the atomic can only make one value indivisible at a time, and two separate atomics can be observed in an inconsistent in-between state.

And here is the honest warning, because atomics are deceptively subtle. As soon as several atomics must agree with each other, or an atomic is being used to guard access to other data (the classic "publish a pointer, then let readers dereference it" pattern), you are no longer in the cosy world of Relaxed. You are into memory ordering: the rules about what one thread is guaranteed to see about another thread's writes, and in what order. That is a genuinely deep topic, and getting it wrong produces bugs that appear only on some CPUs, only under load, only sometimes. So my advice for now is deliberately conservative: use atomics for a lone counter or flag with Relaxed, and use a Mutex for anything where more than one value has to stay consistent. We will earn the right to be braver next time.

How Python and Go would frame this

A glance sideways sharpens the picture, as it usually does in this series. Python does not really have user-level atomics, because the Global Interpreter Lock (GIL) makes many single bytecode operations effectively atomic already -- but "effectively" is carrying weight, and the moment you need a guaranteed-correct counter the idiom is still a lock:

import threading

counter = 0
lock = threading.Lock()

def bump():
    global counter
    for _ in range(1000):
        with lock:          # a lock, because Python has no AtomicUsize.fetch_add
            counter += 1

threads = [threading.Thread(target=bump) for _ in range(8)]
for t in threads: t.start()
for t in threads: t.join()
print(counter)              # 8000

Even here the counter += 1 is the same three-step read-modify-write we started with, and the with lock: is what stops threads from interleaving. Python leans on a big coarse lock (the GIL) plus small explicit ones; it has no notion of a single value the hardware updates atomically, so there is nothing like fetch_add or compare_exchange to reach for.

Go, being a systems language, does have real atomics, in the sync/atomic package, and they map almost one-to-one onto Rust's:

import "sync/atomic"

var counter atomic.Int64

func bump() {
    for i := 0; i < 1000; i++ {
        counter.Add(1) // atomic, like Rust's fetch_add
    }
}

// counter.CompareAndSwap(old, new) is Go's compare_exchange

counter.Add(1) is fetch_add, and CompareAndSwap is compare_exchange. The big difference is not the operations but the defaults: Go's atomics always use the strongest, sequentially-consistent ordering, hiding the Ordering choice from you entirely. Rust exposes that choice, which is more to learn but also lets you tell the compiler and CPU exactly how little synchronisation you can get away with -- and on a hot counter, Relaxed is meaningfully cheaper than sequential consistency. Same primitives, but Rust hands you the dial that Go welds shut.

Wrapping up

So that is the bedrock. An atomic type wraps a single primitive in operations the CPU performs indivisibly, so a shared counter or flag needs no lock at all -- no guard, no Result, nothing to poison. store and load move a value in and out; fetch_add and its siblings are complete read-modify-writes that never lose an update; and compare_exchange -- compare-and-swap -- is the conditional swap from which every lock-free algorithm is built. The CAS loop turns that one conditional swap into any read-modify-write you can dream up: read, compute, try-to-swap, retry if you lost the race.

The judgement to carry forward is the scope test. One primitive value that many threads touch -> reach for an atomic. Consistency that has to span more than one value -> reach for a Mutex. And the moment your atomics have to agree with each other or guard other data, know that you have stepped onto the edge of memory-ordering territory and slow down.

Which is exactly where we are going next. I have spent this whole episode waving Ordering::Relaxed and Ordering::SeqCst around like magic words, promising to explain them later. Later is the next episode. We will find out what Relaxed, Acquire, Release, and SeqCst actually mean, why a value written by one thread might not be visible to another the way you expect, and how these orderings are the difference between a lock-free structure that works and one that corrupts memory only on Tuesdays. It is the deepest water in the whole series -- and once you can swim in it, the two lock-free structures after it will feel almost easy ;-)

Exercises

  1. Use AtomicUsize::fetch_add from several threads to count how many events occurred across all of them, join the threads, and confirm the exact total matches what you expect.
  2. Use compare_exchange on an AtomicBool to implement a one-shot "claim" from multiple threads: only the first thread to swap false to true should win, and it should print that it won.
  3. Write a CAS loop over an AtomicI64 that atomically doubles the stored value, then call it from two threads and reason about the final result.

Bedankt voor het lezen, en tot de volgende keer! ;-)

@scipio

stem stemsocial steemstem rust programming
0
0
0.000
0 comments