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

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)

Last modified: Monday, 5 August 2019, 2:59 AM