CAS loops: compare_exchange and fetch_update

Multiply a list of integers modulo m, using several threads to update one shared AtomicU64:

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

For m > 0, return the product of all input values modulo m. Empty input returns 1 % m. For m == 0, return 0, including when the input is empty. Treat workers == 0 as one worker. The result must not depend on input order or the number of workers.

Keep the starter's scoped-thread structure. It divides nonempty input into chunks, using at most workers.max(1) threads and no more threads than input elements. The shared accumulator starts at 1 % m; each factor must contribute exactly once. Assume enough resources are available to create the threads.

Make multiplication safe before making it atomic

Two u64 values can produce a product too large for u64. Convert both to u128 before multiplying, then reduce modulo u128::from(m). The product of two u64 values fits in u128, and a remainder modulo a nonzero u64 modulus fits back into u64.

For example, multiplying two u64::MAX values modulo 97 gives 11. Wrapping the product in u64 first would give 1, which is the wrong result. Depending on compiler overflow settings, unchecked u64 multiplication may wrap or panic. Neither behavior is the required modular arithmetic.

Check m == 0 before any remainder operation. For m == 1, every result is zero.

Replace the missing operation with a retry loop

The starter calls fetch_mul, which is not an AtomicU64 method on this toolchain. Use compare-and-exchange to implement the modular update. Atomic APIs do not map one-to-one to hardware instructions; generated code depends on the target and enabled CPU features.

compare_exchange(current, next, success, failure) writes next only if the stored value equals current. Success returns Ok(current); failure returns Err(actual) without changing the atomic. The weak version may also fail spuriously, returning Err even when the value matches.

Here is a complete example of updating one factor:

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

fn multiply(acc: &AtomicU64, factor: u64, modulus: u64) {
    assert!(modulus > 0);
    let mut current = acc.load(Ordering::Relaxed);
    loop {
        let next = ((u128::from(current) * u128::from(factor))
            % u128::from(modulus)) as u64;
        match acc.compare_exchange_weak(
            current, next, Ordering::Relaxed, Ordering::Relaxed,
        ) {
            Ok(_) => break,
            Err(actual) => current = actual,
        }
    }
}

fn main() {
    let acc = AtomicU64::new(2);
    multiply(&acc, 5, 7);
    assert_eq!(acc.into_inner(), 3);
}

Recompute next after failure. Another thread may have changed the value; a spurious failure may instead return the same value. In either case, the factor has not yet been applied by this attempt.

A successful comparison checks the current value, not its history. The value could have changed and changed back. That does not hurt this numeric update, which depends only on the current residue, but it matters in algorithms that use a value as an object's identity.

The strong compare_exchange is also valid inside this loop. The weak form can be efficient on some targets because the caller already retries. Neither form should be unwrapped as if concurrent updates cannot fail: both can lose a comparison to another thread.

An alternative: fetch_update

fetch_update handles retries for you. Its closure returns Some(next) to propose a value, or None to stop without updating. This version is accepted too:

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

fn main() {
    let acc = AtomicU64::new(2);
    let result = acc.fetch_update(Ordering::Relaxed, Ordering::Relaxed, |current| {
        Some(((u128::from(current) * 5) % 7) as u64)
    });
    assert_eq!(result, Ok(2));
    assert_eq!(acc.into_inner(), 3);
}

The closure can run multiple times for one successful update. Keep its calculation repeatable; a retry must not charge a customer, consume another input value or otherwise repeat an external effect.

Why Relaxed is enough here

Each update needs to read and replace the accumulator atomically. It does not use the accumulator to signal that other shared data is ready. Relaxed preserves atomicity and the atomic's modification order. Scoped threads join before acc.into_inner() reads the final value.

Modular multiplication is associative and commutative, so every successful ordering of the same factors gives the same answer. Threads contend over the accumulator, but this code does not have a data race.

Compare-and-exchange has separate orderings for success and failure. Failure performs only a load, so its ordering may be Relaxed, Acquire or SeqCst, never Release or AcqRel. The success ordering describes both the load and the store. Valid ordering arguments alone do not prove an algorithm correct.

Publishing other data requires a separate synchronization argument. A release publication paired with an acquire operation that observes it can make prior writes visible; AcqRel is useful when an operation needs both roles. Merely using a pointer does not make AcqRel universally required or sufficient.

Finally, a retry loop offers no fixed bound on one thread's attempts. Lock-free progress concerns the algorithm as a whole, rather than guaranteeing that each participant finishes promptly. This function also creates and joins operating-system threads, so do not describe the entire call as lock-free. Passing output tests is not a proof of memory ordering or progress guarantees.