465: Message Passing vs Shared Memory

Difficulty: 3 Level: Intermediate Compare two correct approaches to concurrent state: channels (message passing) vs `Arc<Mutex<T>>` (shared memory) — and know when to choose each.

The Problem This Solves

You need multiple threads to update a shared data structure — say, a word-frequency counter. Both approaches are correct, but they have very different characteristics. Picking the wrong one either kills performance or makes reasoning about your code unnecessarily hard. With shared memory (`Arc<Mutex<HashMap>>`), every thread grabs the lock for every word. This is fast when updates are tiny and frequent, but the mutex becomes a bottleneck if threads spend significant time holding it. Under high contention, threads spend more time waiting than working. With message passing, each thread accumulates a partial result and sends it all at once. There's no contention during computation — threads work independently. The merge step at the end is the only coordination point. The downside: you're allocating and sending intermediate `HashMap`s, which has overhead for very fine-grained updates.

The Intuition

Message passing says "share data by communicating a result once"; shared memory says "communicate by accessing shared data many times" — message passing is easier to reason about and scales better under high contention; shared memory is faster for high-frequency tiny updates. The Go proverb applies: do not communicate by sharing memory; share memory by communicating.

How It Works in Rust

use std::collections::HashMap;
use std::sync::{mpsc, Arc, Mutex};
use std::thread;

let words = vec!["foo", "bar", "foo", "baz", "bar", "foo"];

// --- Message Passing Approach ---
let (tx, rx) = mpsc::channel::<HashMap<&str, usize>>();

let words_mp = words.clone();
thread::spawn(move || {
 let mut local: HashMap<&str, usize> = HashMap::new();
 for word in words_mp {
     *local.entry(word).or_insert(0) += 1;  // accumulate locally
 }
 tx.send(local).unwrap();                    // send result once
});

let result_mp = rx.recv().unwrap();             // no contention during processing

// --- Shared Memory Approach ---
let shared: Arc<Mutex<HashMap<&str, usize>>> = Arc::new(Mutex::new(HashMap::new()));
let shared2 = Arc::clone(&shared);

thread::spawn(move || {
 for word in &words {
     let mut map = shared2.lock().unwrap();  // lock per update — contention here
     *map.entry(word).or_insert(0) += 1;
 }
});

What This Unlocks

High-contention aggregation: message passing wins — threads compute independently, merge once at the end.
Fine-grained counters: shared memory wins — a per-key `AtomicUsize` is faster than round-tripping through a channel for every increment.
Actor design: message passing naturally leads to the actor model — no shared state at all.

Key Differences

Concept	OCaml	Rust
Message passing	Manual queue + result accumulation	`mpsc::channel` + partial `HashMap`
Shared memory	`ref` + `Mutex`	`Arc<Mutex<HashMap>>`
Lock granularity	Manual	Per `lock()` call
Ownership transfer	Copied or GC-managed	Moved into channel — zero-copy
Best for	Batch, independent workers	Fine-grained, high-frequency updates
Reasoning difficulty	Easier (no shared state)	Harder (must reason about lock ordering)

// 465. Message passing vs shared memory
use std::sync::{Arc, Mutex, mpsc};
use std::collections::HashMap;
use std::thread;

fn count_words(s: &str) -> HashMap<String,usize> {
    let mut m = HashMap::new();
    for w in s.split_whitespace() { *m.entry(w.to_lowercase()).or_insert(0)+=1; }
    m
}

fn merge(mut a: HashMap<String,usize>, b: HashMap<String,usize>) -> HashMap<String,usize> {
    for (k,v) in b { *a.entry(k).or_insert(0)+=v; } a
}

fn msg_passing(texts: Vec<String>) -> HashMap<String,usize> {
    let (tx,rx) = mpsc::channel::<HashMap<String,usize>>();
    for t in texts { let tx=tx.clone(); thread::spawn(move || { tx.send(count_words(&t)).unwrap(); }); }
    drop(tx);
    rx.iter().fold(HashMap::new(), merge)
}

fn shared_mem(texts: Vec<String>) -> HashMap<String,usize> {
    let shared = Arc::new(Mutex::new(HashMap::<String,usize>::new()));
    let hs: Vec<_> = texts.into_iter().map(|t|{let s=Arc::clone(&shared); thread::spawn(move || {
        let local=count_words(&t); let mut g=s.lock().unwrap();
        for (k,v) in local { *g.entry(k).or_insert(0)+=v; }
    })}).collect();
    for h in hs { h.join().unwrap(); }
    Arc::try_unwrap(shared).unwrap().into_inner().unwrap()
}

fn main() {
    let texts = vec!["the fox".to_string(),"the cat".to_string(),"fox cat fox".to_string()];
    let r1 = msg_passing(texts.clone());
    let r2 = shared_mem(texts);
    println!("results match: {}", r1==r2);
    println!("fox count: {}", r1.get("fox").unwrap());
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test] fn test_same() {
        let t=vec!["a b c".to_string(),"a d".to_string()];
        assert_eq!(msg_passing(t.clone()), shared_mem(t));
    }
}

(* 465. Message passing vs shared memory – OCaml *)
let count_words text =
  List.length (List.filter ((<>) "") (String.split_on_char ' ' text))

(* Message passing: collect results *)
let (send,_,recv) =
  let q=Queue.create () let m=Mutex.create () let c=Condition.create () in
  (fun v -> Mutex.lock m; Queue.push v q; Condition.signal c; Mutex.unlock m),
  (),
  (fun () -> Mutex.lock m; while Queue.is_empty q do Condition.wait c m done;
    let v=Queue.pop q in Mutex.unlock m; v)

(* Shared memory: update global counter *)
let total=ref 0 let mutex=Mutex.create ()

let () =
  let texts=["hello world";"foo bar baz";"one two three four"] in
  let ts=List.map (fun t -> Thread.create (fun () -> send (count_words t)) ()) texts in
  List.iter Thread.join ts;
  let mp_total = List.fold_left (fun a _ -> a + recv ()) 0 texts in
  Printf.printf "message passing: %d\n" mp_total;

  let ts=List.map (fun t -> Thread.create (fun () ->
    let n=count_words t in Mutex.lock mutex; total:= !total+n; Mutex.unlock mutex) ()
  ) texts in
  List.iter Thread.join ts;
  Printf.printf "shared memory: %d\n" !total