Concurrency

Why Parallel?

• Hot topic. Meh

• CPUs/memory aren't getting faster, just more parallel

• Big Data / Machine Learning etc

• Some things are naturally concurrent: user input, agent-based systems, etc

• Note that parallel ⇒ concurrent but not vice-versa

Why Not Parallel?

• Generally harder to get right

• Only gives linear speedups

Rust's Parallel Story

• Eliminates shared-memory errors

• Eliminates data races

• Low overhead

• Parallel systems are still hard: partitioning, deadlocks, termination, etc

Approaches To Parallelism

• Background thread

• Worker pool

• Pipeline

• Data parallel

• "Sea of synchronized objects"

Approaches To Parallel Comms / Sync

• Channels

• Mutexes, semaphores, etc

• Shared memory, maybe with CPU-atomic operations

Fork/Join, Shared Memory

• The "old-school" approach

• http://github.com/pdx-cs-rust/parallel

• Rust's error handling is nice here.

Getting Memory To Threads

• Can use move closure to move data into thread

• Can use Arc to share data across threads

Rayon

• Uses "map-reduce" paradigm with worker pool

• The demo here is not too good a match to Rayon's use case

Channels

• Nice way to get values sent for long-running threads

• mpsc: allows building DAGs of channels

• Need mpmc to distribute messages among threads

• Data is actually moved or shared across channels; efficient

Send + Sync

• Marker traits for thread safety

• Automatically maintained (for the most part) by the compiler

• Send: Safe to move value to another thread

• Sync: Safe to share a non-mut reference to value with another thread

• Send and Sync are auto-derived for structs / enums

Synchronization

• Mutex<T>: Wraps a value in a mutex lock

  • For example mutex = Mutex::new(0_usize)
  • Only one thread may complete mutex.lock() at a time
  • That thread gets a mutable reference to the wrapped data
  • Other threads are blocked until first releases lock
  • Returns a Result because mutex poisoning
  • For example *mutex.lock().unwrap() = 5

• RwLock<T>: A mutex that will give out many shared immutable refs or one mutable ref at a time

• Condvar: Just don't

• AtomicUsize et al: Ensures that read-modify-write operations happen as an atomic thing

  • Provides methods like .fetch_add(1, Ordering::SeqCst)

  • The "memory ordering" should probably just always be set to that

  • Not as great as they sound

Arc

• Imagine wrapping a Mutex<T> with an Rc: Rc<Mutex<T>>. This will give us a refcounted locked value.

• Sadly, we know that the read-modify-write when incrementing or decrementing a refcount can screw up due to parallel data races: Rc is not Sync

• No prob: Mutex<Rc<T>>. But wait, now the refcount will never go to 0 because the mutex.

• No prob: <Rc<Mutex<Rc<T>>>…

• Solution is atomic refcount Arc, which is sync. Arc<Mutex<T> is a pretty normal thing.

Examples

• http://gitlab.com/BartMassey/one-way

• http://github.com/pdx-cs-git/collatz

Book Misc

• Nice book example of iterator construction for pipelining

• MPMC discussion (but note section title is wrong)