/rust-concurrency

Rust Concurrency Cheat Sheet

Apache License 2.0Apache-2.0

Rust Concurrency Cheat Sheet

Safety

Rust ensures data race safety through the type system (Send and Sync marker traits) as well as the ownership and borrowing rules: it is not allowed to alias a mutable reference, so it is not possible to perform a data race.

Overview

  Problem
Parallelism Multi-core utilization
Concurrency Single-core idleness
  Solution Primitive Type Description Examples
Parallelism Multithreading Thread T: Send Do work simultaneously on different threads std::thread::spawn
Concurrency Single-threaded concurrency Future Future Futures run concurrently on the same thread futures::future::join, futures::join, tokio::join
Concurrency
+Parallelism		 Multithreaded concurrency Task T: Future + Send Tasks run concurrently to other tasks; the task may run on the current thread, or it may be sent to a different thread async_std::task::spawn, tokio::task::spawn

Futures

pub trait Future {
    type Output;
    fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output>;
}

pub enum Poll<T> {
    Ready(T),
    Pending,
}
  • Future has to be polled (by the executor) to resume where it last yielded and make progress (async is lazy)
  • &mut Self contains state (state machine)
  • Pin the memory location because the future contains self-referential data
  • Context contains the Waker to notify the executor that progress can be made
  • async/await on futures is implemented by generators
  • async fn and async blocks return impl Future<Output = T>
  • calling .await attempts to resolve the Future: if the Future is blocked, it yields control; if progress can be made, the Future resumes

Futures form a tree of futures. The leaf futures commmunicate with the executor. The root future of a tree is called a task.

Tasks and threads

Computation Examples
Lightweight (e.g. <100 ms) async_std::task::spawn, tokio::task::spawn
Extensive (e.g. >100 ms or I/O bound) async_std::task::spawn_blocking, tokio::task::spawn_blocking
Massive (e.g. running forever or CPU-bound) std::thread::spawn

Streams

pub trait Stream {
    type Item;
    fn poll_next(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Option<Self::Item>>;

    fn size_hint(&self) -> (usize, Option<usize>) { ... }
}
  Parallelism
Iterator rayon
Stream tokio, parallel-stream
Operation Relationship Examples
Create futures::stream::iter, futures::stream::once, futures::stream::repeat, futures::stream::repeat_with, async_stream::stream
Create (via channels) futures::channel::mpsc::Receiver, tokio_stream::wrappers::ReceiverStream
Iterate futures::stream::StreamExt::next, futures::stream::StreamExt::for_each, futures::stream::StreamExt::for_each_concurrent
Transform 1-1 futures::stream::StreamExt::map, futures::stream::StreamExt::then, futures::stream::StreamExt::flatten
Filter 1-1 futures::stream::StreamExt::filter, futures::stream::StreamExt::take, futures::stream::StreamExt::skip
Buffer 1-1 futures::stream::StreamExt::buffered, futures::stream::StreamExt::buffer_unordered
Combine n-1 futures::stream::StreamExt::chain, futures::stream::StreamExt::zip, tokio_stream::StreamExt::merge, tokio_stream::StreamMap, tokio::select
Split 1-n futures::channel::oneshot::Sender::send, async_std::channel::Sender::send

Share state

  Threads Tasks
channel std::sync::mpsc (Send), crossbeam::channel (Send, Sync) futures::channel::oneshot, tokio::sync::mpsc, tokio::sync::oneshot, tokio::sync::broadcast, tokio::sync::watch, async_channel::unbounded, async_channel::bounded, oneshot
mutex std::sync::Mutex, parking_lot::Mutex tokio::sync::Mutex

Marker traits

  • Send: safe to send it to another thread
  • Sync: safe to share between threads (T is Sync if and only if &T is Send)
Type Send Sync Owners Interior mutability
Rc<T> No No multiple No
Arc<T> Yes (if T is Send and Sync) Yes (if T is Send and Sync) multiple No
Box<T> Yes (if T is Send) Yes (if T is Sync) single No
Mutex<T> Yes (if T is Send) Yes (if T is Send) single Yes
RwLock<T> Yes (if T is Send) Yes (if T is Send and Sync) single Yes
MutexGuard<'a, T: 'a> No Yes (if T is Sync) single Yes
Cell<T> Yes (if T is Send No single Yes
RefCell<T> Yes (if T is Send) No single Yes

Concurrency models

Model Description
shared memory threads operate on regions of shared memory
worker pools many identical threads receive jobs from a shared job queue
actors many different job queues, one for each actor; actors communicate exclusively by exchanging messages
Runtime Description
tokio (multithreaded) thread pool with work-stealing scheduler: each processor maintains its own run queue; idle processor checks sibling processor run queues, and attempts to steal tasks from them
actix_rt single-threaded async runtime; futures are !Send
actix actor framework
actix-web constructs an application instance for each thread; application data must be constructed multiple times or shared between threads

Terminology

Shared reference: An immutable reference (&T); can be copied/cloned.

Exclusive reference: A mutable reference (&mut T); cannot be copied/cloned.

Aliasing: Having several immutable references.

Mutability: Having one mutable reference.

Data race: Two or more threads concurrently accessing a location of memory; one or more of them is a write; one or more of them is unsynchronized.

Race condition: The condition of a software system where the system's substantive behavior is dependent on the sequence or timing of other uncontrollable events.

Deadlock: Any situation in which no member of some group of entities can proceed because each waits for another member, including itself, to take action.

Heisenbug: A heisenbug is a software bug that seems to disappear or alter its behavior when one attempts to study it. For example, time-sensitive bugs such as race conditions may not occur when the program is slowed down by single-stepping source lines in the debugger.

Marker trait: Used to give the compiler certain guarantees (see std::marker).

Thread: A native OS thread.

Green threads (or virtual threads): Threads that are scheduled by a runtime library or virtual machine (VM) instead of natively by the underlying operating system (OS).

Context switch: The process of storing the state of a process or thread, so that it can be restored and resume execution at a later point.

Synchronous I/O: blocking I/O.

Asynchronous I/O: non-blocking I/O.

Future (cf. promise): A single value produced asynchronously.

Stream: A series of values produced asynchronously.

Sink: Write data asynchronously.

Task: An asynchronous green thread.

Channel: Enables communication between threads or tasks.

Mutex (mutual exclusion): Shares data between threads or tasks.

Interior mutability: A design pattern that allows mutating data even when there are immutable references to that data.

Executor: Runs asynchronous tasks.

Generator: Used internally by the compiler. Can stop (or yield) its execution and resume (poll) afterwards from its last yield point by inspecting the previously stored state in self.

Reactor: Leaf futures register event sources with the reactor.

Runtime: Bundles a reactor and an executor.

polling: Attempts to resolve the future into a final value.

io_uring: A Linux kernel system call interface for storage device asynchronous I/O operations.

CPU-bound: Refers to a condition in which the time it takes to complete a computation is determined principally by the speed of the CPU.

I/O bound: Refers to a condition in which the time it takes to complete a computation is determined principally by the period spent waiting for input/output operations to be completed. This is the opposite of a task being CPU bound.

References