rust multithreading at the cache line
rust makes threads safe.
the cpu still makes them pay rent.
that is the part people miss. `Send`, `Sync`, `Arc`, `Mutex`, `RwLock`, atomics, channels, Rayon, Tokio — all of that is rust's language for describing who is allowed to touch memory. below it, the processor only sees cores, cache lines, store buffers, fences, scheduler interrupts, and coherence traffic.
the question is never: can i spawn threads?
the question is: what memory are they going to fight over?
the speedup floor.
amdahl's law is the first wall:
speedup(n) = 1 / ((1 - p) + p/n + o(n))
p is the fraction of the program that can run in parallel. n is the number of worker cores. o(n) is the tax: scheduling, synchronization, cache misses, queueing, allocation, false sharing.
if 95% of the work is parallel and 5% is serial, 16 cores do not give 16x.
1 / (0.05 + 0.95/16) = 9.14x
and that's with zero overhead.
if the serial part is 10%, infinite cores cap at 10x. not because rust is slow. because the math says there is still one part of the program everyone has to wait for.
the second wall: shared writes.
take n items. each item costs c cycles of real computation. every worker also increments one global atomic counter. under contention, that increment costs q cycles because the cache line has to move between cores.
bad shape:
t(p) ≈ n*c/p + n*q
the useful work divides by p. the shared atomic does not.
with c = 20 cycles, q = 80 cycles, p = 8:
t(8) ≈ 2.5n + 80n = 82.5n
single-threaded was roughly 20n. the multithreaded version is slower because the hot loop became a cache-coherence benchmark.
good shape:
t(p) ≈ n*c/p + p*r
each worker accumulates locally. one reduce at the end. r is the cost of merging p results. for large n, the shared part disappears into noise.
this is the real rust multithreading rule: partition first, reduce later.
what rust changes.
rust does not remove contention. it makes contention explicit.
`Arc<T>` gives shared ownership across threads. it does not make `T` internally safe. `Arc<Mutex<T>>` gives shared ownership plus serialized mutation. correct, often useful, and very often the slow path.
a mutex is not slow because the abstraction is bad. a mutex is slow because it turns parallel work into a queue. one owner at a time. fast path is an atomic state change. slow path parks the thread and asks the os scheduler to wake it later. once the lock is hot, your program is no longer running on eight cores. it is running on one critical section with seven cores orbiting it.
`RwLock` only helps if reads dominate, read sections are long enough, writes are rare, and the platform's lock policy doesn't turn the thing into starvation or convoying. for tiny protected data, the bookkeeping can cost more than the read.
atomics are lower, not free.
`Relaxed` means atomicity without ordering constraints. `Release` publishes previous writes. `Acquire` observes them. `SeqCst` adds a single global order for sequentially consistent operations, easier to reason about and sometimes more expensive for the compiler and hardware to preserve.
but no ordering changes the physical unit.
the cache line is the unit.
on mainstream cpus, a cache line is usually 64 bytes. eight `u64`s can sit on the same line. if you create `[AtomicU64; 8]` and give one counter to each worker, rust sees independent indexes. the processor sees one cache line.
core 0 writes slot 0. core 1 writes slot 1. the addresses are different. the cache line is the same. every write invalidates the other core's copy.
that's false sharing.
logically separate. physically shared.
the fix is blunt: pad it, shard it, or stop writing there. use per-thread buffers. use cache-line padding when the field is hot. arrange data so every worker mutates memory it owns.
the alternatives.
`std::thread::spawn` is for real os threads with independent lifetime. long-lived workers, background services, dedicated loops. not one thread per tiny task.
`std::thread::scope` is the clean default for bounded parallel work. you can borrow stack data because rust proves the threads join before the scope exits. less `Arc`, fewer reference-count atomics, less ownership ceremony.
Rayon is the default for cpu-bound data parallelism. if the work is split this slice, process chunks, reduce results, use Rayon. the win is not `.par_iter()` syntax. the win is that the library pushes you toward the architecture the hardware wants: divide, run locally, steal work when chunks are uneven, reduce once.
Tokio is not a cpu parallelism model. it is an async io runtime. if a task waits on sockets, timers, rpc, files, databases, Tokio is the right tool. if a task burns cpu inside a future without yielding, it starves the executor. use `spawn_blocking` for bounded blocking work, or move serious cpu work to Rayon or a dedicated pool.
channels are ownership transfer plus backpressure. not throughput magic.
if producers emit λ items/s and each worker handles μ items/s, stability requires:
λ < p*μ
if λ > p*μ, an unbounded channel just turns overload into memory growth. bounded channels are better because they make pressure real.
crossbeam is the sharper toolbox: fast channels, scoped threads, work-stealing deques, padding utilities, epoch reclamation. use it when `std` is too small and Rayon is too high-level.
lock-free is the last tool. it removes kernel parking, then gives you retry loops, atomics, cache-line traffic, memory reclamation, and harder proofs. under real contention, a lock-free structure can lose to a boring sharded design.
the shape that keeps scaling.
immutable input.
exclusive mutable output.
no shared writes in the inner loop.
one merge at the end.
that is the pattern.
the anti-pattern is `Arc<Mutex<HashMap<K, V>>>` inside every worker. rust made it safe. it did not make it parallel. every core still walks to the same door.
grain size matters too.
if scheduling a task costs h and each item costs c, a chunk of k items spends:
overhead_ratio = h / (k*c + h)
to keep overhead under 1%:
k > 99h/c
if h = 3µs and c = 20ns, k needs to be around 15,000 items. below that, you are not measuring computation. you are measuring the scheduler.
the lower you go, the less multithreading is about threads.
it becomes a memory layout problem.
how many independent cache lines can the machine mutate at once?
if the answer is one, you wrote a serial program with thread syntax.
if the answer is p, where p is the number of useful physical cores, rust can get close to the metal without letting you tear memory apart.
the principle.
the best rust multithreading is not the cleverest synchronization primitive.
it's the design where synchronization almost disappears.
parallelism is independent work, on independent memory, with one controlled merge at the end.