Atomics: counters, flags and fetch_*

Build a histogram in parallel with no locks at all.

pub fn atomic_histogram(values: Vec<usize>, buckets: usize, workers: usize) -> Vec<usize>

Each value lands in bucket v % buckets. Split the values across workers scoped threads that all increment the same Vec<AtomicUsize>, then return the counts. buckets == 0 returns []; treat workers == 0 as 1.

The tests run workers = 1, 4, 16 and demand identical counts.

The cheapest correct shared state

An atomic is a value the hardware can read-modify-write in one indivisible step. fetch_add compiles to a single instruction on every platform you care about — no lock, no guard, no blocking, no poisoning, nothing to hold too long, nothing to acquire in the wrong order.

let n = counter.fetch_add(1, Ordering::Relaxed);

Every fetch_* returns the PREVIOUS value, which is genuinely useful — fetch_add(1, ..) hands you a unique ticket number as a side effect of counting. It also catches people out, so read it once and remember it.

The portable set: AtomicBool, AtomicUsize/AtomicIsize, AtomicPtr, and AtomicU8/16/32/64 with their signed twins. The 64-bit ones are missing on some 32-bit targets, gated behind cfg(target_has_atomic = "64").

Why there is no Arc in this problem

Atomics are Sync. So &AtomicUsize is Send, so a shared reference to one can cross a thread boundary — and with thread::scope supplying the lifetime, &Vec<AtomicUsize> is all you need. No Arc, no clone per worker, no atomic refcount to pay for on top of the atomic you actually wanted.

This is the payoff for having learned Sync as “T: Sync means &T: Send“ rather than as a magic word.

“Relaxed is enough here” — and why

You will meet the memory orderings properly in the next two items. For a histogram the answer is Relaxed, and the reason is worth having now:

each counter stands entirely alone. No worker publishes data that another worker reads. Nobody uses a count to decide whether some other memory is ready. There is nothing to order against, so the only guarantee needed is the one Relaxed gives: the operation is atomic, and the modifications to that one variable have a single agreed order.

Relaxed does not mean “fast and slightly wrong”. It means “atomic, with no promises about anything else”. When there is nothing else, it is exactly right. Reach for SeqCst by default and you have written a slower program and told the next reader that ordering matters here, which is worse than being slow.

The obstacle in the starter

error[E0277]: the trait bound `AtomicUsize: Clone` is not satisfied
   |     let counts: Vec<AtomicUsize> = vec![AtomicUsize::new(0); buckets];

vec![elem; n] evaluates elem once and clones it. Atomics deliberately are not Clone: cloning a counter would give you a second, independent counter that shares nothing with the first, which is never what anybody writing that line meant. The type system refuses rather than surprising you.

let counts: Vec<AtomicUsize> = (0..buckets).map(|_| AtomicUsize::new(0)).collect();

And at the end, into_iter().map(AtomicUsize::into_inner) reads them all out without any synchronisation, because owning the value proves nobody else can reach it.

::: question Why is const COUNTER: AtomicUsize = AtomicUsize::new(0); a bug, and how many warnings does it produce? Three, from two different tools, and all of them warn-by-default — so all three fail this course’s gate.

warning: a `const` item should not be interior mutable
         [clippy::declare_interior_mutable_const]
warning: a `const` item with interior mutability should not be borrowed
         [clippy::borrow_interior_mutable_const]
warning: taking a mutable reference to a `const` item
         [const_item_interior_mutations]   <- rustc's own

A const is not a variable, it is a value that is inlined at every use site. So COUNTER.fetch_add(1, Relaxed) creates a brand-new atomic, increments it, and throws it away. Every single time. The counter never changes and the program silently counts nothing.

static COUNTER: AtomicUsize = AtomicUsize::new(0); is the fix: a static is one object at one address that everything refers to. And it works with no ceremony because AtomicUsize::new is a const fn — the same reason static M: Mutex<Vec<u8>> = Mutex::new(Vec::new()) needs no lazy_static any more.

Three warn-by-default lints firing on one line is unusually generous. The toolchain is teaching the const versus static distinction directly, which is worth taking as a general lesson: when several independent lints agree, the code is not merely unidiomatic. :::

One thing this build changes

The grader compiles with -O, which means release mode: integer overflow wraps silently rather than panicking. A fetch_add on an AtomicU8 past 255 wraps to 0 and says nothing. It cannot happen with the inputs here, and it is worth knowing before you size a counter: use usize/u64, or say wrapping and mean it.