Sync: T is Sync exactly when &T is Send

Sum values by splitting the vector into chunks, summing each chunk on its own scoped thread, and adding every chunk sum into one shared total.

pub fn shared_accumulate(values: Vec<i64>, workers: usize) -> i64

Contract

• Return the sum of all elements of values. An empty vector returns 0.
• workers is the number of chunks to aim for. Treat workers == 0 as 1. If workers is larger than values.len(), there are not enough elements for that many chunks. The starter's chunking (values.len().div_ceil(workers) elements per chunk) then produces fewer chunks, none of them empty.
• The answer must not depend on workers. The tests use worker counts from 0 to 16 and check only the returned total, not how many threads ran.
• Overflow is outside the contract. In every test, the sum of the absolute values fits in i64, so no grouping of the additions can overflow.

Summing each chunk and adding the returned sums after joining the threads would avoid sharing anything. This exercise uses a shared cell on purpose, because sharing one value between threads is what the Sync trait is about.

Two marker traits

Send and Sync are marker traits: they have no methods, and the compiler implements them automatically for a type whose fields all implement them.

• T: Send means a value of type T may be moved to another thread.
• T: Sync means a &T (a shared reference to T) may be used from several threads at the same time.

The starter's error

The starter shares a RefCell<i64> between scoped threads. RefCell gives interior mutability: it lets code change the value behind a shared & reference by checking the borrowing rules at run time (borrow_mut() panics if the value is already borrowed) instead of at compile time. Each spawned closure captures total, which is a &RefCell<i64>. Rust 1.98.1 reports, in part:

error[E0277]: `RefCell<i64>` cannot be shared between threads safely
   |
   = help: the trait `Sync` is not implemented for `RefCell<i64>`
   = note: required for `&RefCell<i64>` to implement `Send`
note: required because it's used within this closure
note: required by a bound in `Scope::<'scope, 'env>::spawn`

Read the notes from the bottom up. Scope::spawn requires its closure to be Send. The closure holds a &RefCell<i64>, so that reference must be Send. A shared reference &T is Send only when T is Sync, and RefCell<i64> is not. (The full message also notes that std::sync::RwLock can be used instead. An RwLock<i64> would work here too, but every access in this exercise is a write, so a Mutex is the simpler choice.) The standard library documents the link as a definition:

T is Sync if and only if &T is Send.

In other words, handing a &T to another thread is safe exactly when sharing a T between threads is safe. Sync is still its own trait (you write T: Sync in bounds), but this equivalence is what it means.

Why RefCell is not Sync

RefCell keeps a borrow counter in an ordinary, non-atomic integer. If two threads called borrow_mut() at once, both could read "not borrowed" before either wrote "borrowed", and both would get a &mut i64 to the same value. Unsynchronized concurrent writes to that counter are a data race, and two live &mut references to one value break Rust's aliasing rules. Both are undefined behavior, so RefCell does not implement Sync. (It is still Send when its contents are: moving the whole RefCell to one other thread is fine.)

Interior mutability without synchronization is the most common reason a type is not Sync; Cell, RefCell and Rc (whose reference count is a plain integer) are examples. It is not the only reason. Raw pointers are not Sync, and a struct is Sync only if all of its fields are, so a type that contains any non-Sync field is also not Sync unless its author writes an unsafe impl.

The fix: Mutex<i64>

Mutex<T> provides interior mutability with synchronization: lock() blocks until no other thread holds the lock, then returns a guard that gives access to the value. Because only one thread can use the value at a time, Mutex<i64> is Sync. Replace RefCell<i64> with std::sync::Mutex<i64> and borrow_mut() with lock(), and the program compiles.

• lock() returns a Result. It is Err if the mutex is poisoned, which happens when a thread panicked while holding the lock. Here no thread panics while holding it, so .expect("mutex poisoned") is a reasonable way to unwrap it.
• Mutex::into_inner(self) returns the value at the end without taking the lock. It consumes the mutex, so no other reference to it can exist and there is nothing to wait for. It still returns a Result, because it reports poisoning too. get_mut(&mut self) relies on the same reasoning to borrow the value in place without locking, and also returns a Result.

When two workers finish at about the same time, one waits for the other to release the lock. This waiting is called contention:

An AtomicI64 updated with fetch_add is also Sync and passes the tests. For a single integer counter it avoids a lock, though whether it is faster in a given program is something to measure.

Why Mutex and RwLock have different bounds

The standard library implements Sync for these two locks with different conditions:

unsafe impl<T: ?Sized + Send> Sync for Mutex<T> {}
unsafe impl<T: ?Sized + Send + Sync> Sync for RwLock<T> {}

(?Sized allows unsized types such as [i64], and unsafe impl means the library authors, not the compiler, are responsible for the claim.)

A Mutex<T> gives at most one thread access to the T at a time. Different threads may take turns, so the value effectively moves between threads, which is what Send allows. T never has to be shared, so T: Sync is not needed.

An RwLock<T> allows several readers to hold &T at the same time, on different threads. That is sharing, so T must be Sync. A writer on any thread can also get &mut T and, for example, swap the value out, so T must be Send as well. Each bound follows from what the lock lets threads do with the T.

Checking a bound at compile time

A generic function with a bound and an empty body asks the compiler whether a type satisfies the bound:

use std::cell::RefCell;
use std::sync::Mutex;

fn assert_sync<T: Sync>() {}

fn main() {
    assert_sync::<Mutex<i64>>();   // compiles
    assert_sync::<RefCell<i64>>(); // error[E0277]: the program does not build
}

A failed check stops compilation, so the negative case cannot be part of a passing submission, and Rust has no run-time function that reports whether a type is Sync. You may keep a positive check such as assert_sync::<Mutex<i64>>() in your solution, but the tests only check the returned total.