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
Rust's error handling is nice here.
Getting Memory To Threads
Can use
move
closure to move data into threadCan 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 channelsNeed
mpmc
to distribute messages among threadsData 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 threadSync
: Safe to share a non-mut reference to value with another thread
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
- For example
RwLock<T>
: A mutex that will give out many shared immutable refs or one mutable ref at a timeCondvar
: Just don'tAtomicUsize
et al: Ensures that read-modify-write operations happen as an atomic thingProvides 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 anRc
: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 notSync
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)