Atomics: counters, flags and fetch_*

Fix the histogram's counter initialization so the supplied parallel code compiles. Each worker increments shared atomic counters without a mutex around the updates.

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

Return one count per bucket, in bucket-index order. Each input value v contributes once to bucket v % buckets, including repeated values. For example, [0, 1, 4, 4] with three buckets produces [1, 3, 0].

If buckets == 0, return an empty vector without computing any remainders. An empty input with a positive bucket count returns that many zeros. Treat workers == 0 as one worker. Results must be independent of the requested worker count.

The supplied partitioning uses nonempty chunks of size values.len().div_ceil(workers.max(1)). It can start fewer threads than requested and starts none for empty input. Inputs fit in memory; the worker count is a partitioning parameter, not a requirement to create idle threads.

Initialize each counter separately

The starter fails with E0277 because vec![AtomicUsize::new(0); buckets] requires AtomicUsize: Clone, which is not implemented. This remains a compile-time requirement even when a particular call requests zero buckets.

Construct each element independently:

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

These are separate counters, one per bucket. The workers all borrow the same vector; they do not make copies of its counters.

Increment without losing concurrent updates

fetch_add reads the previous value and adds to it as one atomic operation:

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

fn main() {
    let counter = AtomicUsize::new(0);
    assert_eq!(counter.fetch_add(1, Ordering::Relaxed), 0);
    assert_eq!(counter.fetch_add(1, Ordering::Relaxed), 1);
    assert_eq!(counter.into_inner(), 2);
}

Separate load and store operations would not be equivalent. Two workers could both read the same count and then store the same incremented value, losing an update. fetch_add avoids that race in the counting algorithm. Its returned old value can also serve as a ticket, provided the counter is not reset and does not wrap.

An atomic operation is not guaranteed to use one machine instruction or complete in a fixed number of steps. Available standard atomic operations are lock-free, but can use retry loops. Support for atomic widths and operations depends on the target; see the standard library's portability notes.

Why shared borrows are enough

AtomicUsize is Sync, so multiple threads may hold shared references to the counters. thread::scope joins its spawned threads before returning. Those threads can therefore borrow the local vector without outliving it, and no Arc is needed.

Once the scope finishes, consume the vector with counts.into_iter().map(AtomicUsize::into_inner).collect(). into_inner extracts an exclusively owned counter's value without an atomic load. The thread joins have already provided the synchronization needed before collecting the final counts.

Why relaxed ordering works here

Workers only need indivisible increments of each counter. They do not use a count to announce that some separate data is ready. Ordering::Relaxed supplies atomic updates and an ordering of modifications to each individual counter. Completion of the scoped threads establishes when the parent can read the final result.

Stronger ordering such as SeqCst is also correct for these increments, but its additional ordering guarantees are unnecessary here. Whether it changes performance depends on the target and workload. Even relaxed updates can contend when many workers increment the same bucket. A shared atomic histogram is not automatically faster than a sequential loop or per-worker histograms merged afterward.

Atomic addition wraps in debug builds too

Integer atomic fetch_add uses wrapping arithmetic regardless of the ordinary integer overflow-check setting. For example, incrementing an AtomicU8 containing 255 stores 0 and returns 255. Enabling debug overflow checks does not change that operation.

This histogram cannot count more items in one bucket than values.len(), which fits usize, so its increments do not overflow. A long-lived counter in another program may need explicit overflow handling. Choosing a wider integer only increases its range.