CAS loops: compare_exchange and fetch_update

Compute (∏ values) mod m into a shared AtomicU64, from several threads.

pub fn atomic_product_mod(values: Vec<u64>, m: u64, workers: usize) -> u64

Empty input gives 1 % m. m == 0 returns 0. Treat workers == 0 as 1. The tests run workers = 1, 2, 8 and demand identical answers.

Use u128 for the intermediate. values may contain numbers near u64::MAX, and a * b in u64 would overflow — silently, because this build is -O and overflow checks are off. (u128::from(a) * u128::from(b)) % m is exact.

Modular multiplication is commutative and associative, so the product is the same whatever order the threads apply their factors. That is what makes a genuinely racy computation deterministically testable.

There is no fetch_mul, and there never will be

The starter tries one and gets E0599. Look at what the atomic API actually offers: fetch_add, fetch_sub, fetch_and, fetch_or, fetch_xor, fetch_min, fetch_max, swap. That is not a curated selection — it is the list of read-modify-write operations the hardware implements as single instructions.

Everything else you build yourself, out of the one universal primitive:

fn compare_exchange(&self, current: T, new: T, success: Ordering, failure: Ordering)
    -> Result<T, T>

“If the value is still current, replace it with new and return Ok(old). Otherwise change nothing and return Err(actual).” Atomically.

The retry loop

let mut cur = acc.load(Relaxed);
loop {
    let next = f(cur);
    match acc.compare_exchange_weak(cur, next, Relaxed, Relaxed) {
        Ok(_) => break,
        Err(actual) => cur = actual,   // someone beat us — recompute from theirs
    }
}

Read it as an optimistic transaction: compute assuming nothing changed, then commit only if nothing did. If it did, you did not corrupt anything — you wasted one iteration and try again from the value that actually won.

This is what “lock-free” means. Not “no synchronisation” — there is plenty. It means no thread can block the others: whoever loses a CAS retries, and the winner always makes progress, so the system as a whole cannot stall because one thread was descheduled mid-update. A mutex holder that gets descheduled stops everybody.

It also means CAS loops can starve an individual thread under heavy contention. Lock-free is a system-level guarantee, not a per-thread one.

_weak versus strong, and why _weak here

compare_exchange_weak may fail spuriously — return Err even when the value did match.

That sounds like a defect and is a deliberate hardware concession. On ARM and RISC-V, CAS is compiled from a load-linked/store-conditional pair, and the store-conditional can fail for reasons that have nothing to do with your value — a context switch, an interrupt, another core touching the same cache line. The strong version must therefore add its own retry loop internally to hide those failures.

So: inside a retry loop you want _weak, because you are going to loop anyway and the extra internal loop is pure waste. Use the strong form only for one-shot attempts, where “did I win?” is the answer you need.

This is also the classic intermittent-failure bug: a solution that calls compare_exchange_weak(...).unwrap() works on x86 (where the spurious failure mode barely exists) and fails at random on ARM. Handle the Err — that is what the loop is.

One rule the compiler enforces: the failure ordering may not be stronger than the success ordering. rustc’s invalid_atomic_ordering lint is deny-by-default and catches the syntactic misuses for free.

fetch_update, the same loop with a nicer face

acc.fetch_update(Relaxed, Relaxed, |cur| Some(mul_mod(cur, v, m))).ok();

It writes the retry loop for you, using _weak internally, and lets the closure return None to abandon the update. Prefer it in real code. Write the explicit loop at least once first, so that you know what it is doing when it shows up in a profile.

::: question Why does Relaxed suffice here, when this is a read-modify-write cycle? Because the accumulator does not publish anything.

Ordering exists to make other memory visible: a Release store followed by an Acquire load is how one thread says “the buffer I filled before this store is now safe to read”. Here there is no buffer. The only thing any thread learns from the atomic is the atomic’s own value, and Relaxed already guarantees each variable has a single total modification order that everyone agrees on.

The CAS itself is still atomic under Relaxed — atomicity and ordering are independent properties, and confusing them is the most common misreading of the memory model. Relaxed gives up ordering, never atomicity.

The moment your CAS publishes a pointer to data written beforehand, the success ordering must become AcqRel and the readers’ load Acquire. The next article is about exactly where that line is, and about why this grader cannot test which side of it you are on. :::