Concurrency in depth

On this page

What you have already met
Choosing a tool
Kinds of concurrency
What can go wrong, and what Cone prevents
Work that finishes where it is begun
The pages of this part

The Guide put every core to work with two tools, actors and parallel each, and Memory showed how permissions keep threads from tangling over the same data. A real program asks more: an actor that waits on the network, a loop that fills a picture, a value several threads must change, a kernel for the GPU, a thread of your own. This part goes deeper into each, from the tools most programs use to the pieces few need. Afterwards you can choose the right tool for each piece of concurrent work, and know what the compiler guarantees about it. Here is one sum, worked out three ways:

mod three;

import stdio use *;
import collections use *;
import thread;
import actors;

fn squares(from u64, to u64) u64 {
  var sum = 0u64;
  each n in from ..< to { sum += n * n; }
  sum;
}

// A standing role: an actor keeps a running total
actor Tally {
  total u64;
  pub async do add(self, n u64) { total += n; }
  pub async do report(self) { print <- "an actor:        ", total, "\n"; }
}

fn half(top u64) u64 { squares(top / 2u64, top); }

fn main() {
  let top = 1000u64;

  // One big loop: parallel each, on every core
  let xs = new List[u64] <- parallel each n in 0u64 ..< top yield n * n;
  print <- "parallel each:   ", xs.parallel().sum(), "\n";

  // A thread of your own, joined when its half is done
  let t = thread.start(top, &half);
  let low = squares(0u64, top / 2u64);
  print <- "an OS thread:    ", low + t.join(), "\n";

  // Messages to an actor, handled one at a time
  let tally = new Tally(0u64);
  tally.add(low);
  tally.add(squares(top / 2u64, top));
  tally.report();
}

It prints:

parallel each:   332833500
an OS thread:    332833500
an actor:        332833500

The same answer three times, but not the same program. The loop split the work itself, as it ran; the thread was given its half by hand, and joined; the actor kept a total that outlives any one message. Each suits a different shape of work, and most of this part is about telling them apart.

What you have already met#

Actors (the Guide): workers with state of their own and an ongoing job, called like methods, each handling one message at a time, waiting for each other with await.
parallel each (the Guide): one loop on every core, its results gathered by the parallel builder or a reduction.
Permissions (Memory): what a reference's holder may do, and what others may do meanwhile, which is the first half of why threads cannot race on a value. Lock permissions (Memory) are the dynamic ones, for a value several threads change: a borrow takes the lock, and its last use gives it back.

This part does not repeat them. It goes on from where they stop.

Choosing a tool#

Concurrency can make a program faster in two ways: by spreading work over several cores (many hands make light work), and by keeping the cores busy with other work, rather than idle, while it waits on the world. Every tool here does one or both, and each fits a shape of work:

Parts with state and an ongoing job, such as a stock room, a connection, a cache: give each an actor. It needs no lock, since one message at a time reaches its state.
One big job of independent pieces: a parallel each, which splits the work as it runs.
Waiting on other actors, or on the world (sockets, files, timers, child processes, HTTP): an actor awaits the answer or the I/O, and its worker runs other actors meanwhile.
Thousands of identical small computations over plain numbers: a kernel on the GPU, which runs as its twin on the CPU too.
A thread of your own, for a library that blocks, a pipeline, or a scheduler you design: OS threads and channels.
The cheapest possible sharing, such as a counter every thread bumps, or a data structure of your own: atomics, the futex and locks.

Whatever the tool, share as little that changes as you can. Shared, changing data costs synchronization on every change, costs the other cores their cached copies, and is where deadlocks come from. Moving a value from one thread to the next, and sharing freely what nobody changes, cost nothing at run time (Sharing what changes).

Kinds of concurrency#

Ways of running work at once differ most in what it costs to switch from one piece of work to another. From the cheapest:

Cooperative concurrency, where the switch is written into the logic: generators are the form that exists. Co-routines beyond them are not built yet.
Actors on a pool of worker threads, which the runtime's work-stealing scheduler multiplexes (How the runtime works). Each message is handled to completion on a worker's own stack, or up to an await, where the compiler cuts the behaviour in two. An actor is not a green thread that is paused and resumed, and green threads are not built.
OS threads, switched by the operating system's scheduler, which share memory and resources: the thread package (OS threads and channels).
OS processes, switched by the operating system and isolated from each other. A program can run a child process and wait for it, from a plain thread or an actor (child processes); processes working together on one job are not built.
Distributed computing, across machines that talk over the network: not built, beyond the sockets and HTTP an actor awaits.

As always there are trade-offs: a dearer switch can be worth it for scalability, fault isolation or simpler handling of I/O.

What can go wrong, and what Cone prevents#

Concurrency done carelessly fails in three ways:

Race conditions, where a program's behaviour varies with the order or timing of independent operations. The worst, a data race, is two threads reaching the same memory at once, one of them writing. Cone refuses data races when the program is compiled, through the permissions and the rules on what may cross a thread (Race safety, which also names the few places it trusts the program). A race in the wider sense, where the outcome depends on which thread got there first, is a program's own logic, and no compiler can rule it out: the Guide's bakery could not say which customer would go short.
Deadlocks, where progress stops because operations each hold something another is waiting for. Cone does not prevent them (Lock permissions). An actor never holds a lock while it awaits: an await gives every lock back (What crosses an await).
Livelocks, where progress stops for want of a resource, though nothing is deadlocked.

Work that finishes where it is begun#

Concurrent work is easiest to reason about when it finishes inside the code that started it, as a function call does. Cone's tools go a long way towards that. A parallel each has finished every pass when control reaches the statement after it, and so has actors.parallelRange. A thread's handle is its one owner: joining it waits for the thread, and a handle that dies unjoined joins as it dies, though that is tidiness rather than a guarantee (The handle). The program itself ends only when no actor is queued or running (How the runtime works). And an actor's state is finalized exactly once, when its last handle has gone and its mailbox is empty.

The pages of this part#

Actors in depth: the four shapes of behaviour, the declaration, making an actor, an actor's life, self and selfactor, private state.
parallel each in depth: what it can walk, what its body may do, the parallel builder, reductions, filling buffers, a loop in an actor.
What may cross a thread: Sendable and Shareable: race safety, the two markers, borrows that last the whole program, sharing what changes.
await and futures in depth: what crosses an await, an await inside a statement, futures.
I/O from an actor: sockets, datagrams, files, timers, names, file metadata, child processes and HTTP, awaited; cancelling and deadlines.
The I/O loop underneath: the iocore loop driven by hand, datagrams and cancel groups on it, the I/O thread and the program's end.
How the runtime works: the workers and the scheduler, an actor's own garbage-collected region, the parallel loop underneath.
The GPU: compute kernels: kernels and their CPU twins, buffers, atomics, workgroup memory, barriers.
OS threads and channels: starting, joining and parking threads; channels and the one-shot channel.
Roll your own: atomics, the futex and locks: atomic values, the futex, Mutex, Rwlock, Condvar and Once.

Lock permissions, the checked way for threads to share a value that changes, are in Memory: Lock permissions.