skip to content

In Rust, how does `rayon::join` let a recursive quicksort sort both halves in parallel, and why does it need no `'static` or `Arc`?

level: middleimportance: should knowfreq 40%

answer

  1. potentially parallel, not always
  2. run A here, offer B
  3. returns only after both finish
  4. split_at_mut gives disjoint borrows

basics

~20 s

rayon::join runs closure A on the current worker and offers closure B for an idle worker to steal, returning both results. It blocks until both finish, so closures need only Send and may borrow disjoint halves from split_at_mut.

solid answer

~40 s

`rayon::join(a, b)` takes two `FnOnce() -> R + Send` closures and *potentially* runs them in parallel: inside the pool it executes `a` on the current thread and pushes `b` where an idle worker can steal it, running `b` itself if nobody did. Because `join` returns only after both closures complete, there is no `'static` bound, so the quicksort can `split_at_mut` the slice and hand `lo` to one closure and `hi` to the other; the borrow checker accepts two disjoint `&mut` borrows and rejects one variable captured mutably by both with E0499. Add a sequential cutoff for small slices, and use `rayon::scope` when the number of tasks is only known at run time.

code

rust · 29 lines
rust
fn partition(v: &mut [i64]) -> usize {
    let pivot = v.len() - 1;
    let mut i = 0;
    for j in 0..pivot {
        if v[j] <= v[pivot] {
            v.swap(i, j);
            i += 1;
        }
    }
    v.swap(i, pivot);
    i
}

fn quick_sort(v: &mut [i64]) {
    if v.len() <= 1_000 {
        v.sort_unstable(); // below the cutoff a task costs more than it saves
        return;
    }
    let mid = partition(v);
    let (lo, hi) = v.split_at_mut(mid);
    rayon::join(|| quick_sort(lo), || quick_sort(&mut hi[1..]));
}

fn main() {
    let mut v: Vec<i64> = (0..1_000_000).map(|i| (i * 7_919) % 1_000_003).collect();
    quick_sort(&mut v);
    assert!(v.windows(2).all(|w| w[0] <= w[1]));
    println!("sorted {} items", v.len());
}

go deeper

for a junior

Recall that rayon::join takes two closures, may run them in parallel, and returns both results as a tuple once both are done.

for a middle

Explain the execution: A on the current worker, B offered for stealing, and why the blocking return removes the 'static requirement so split_at_mut halves can be captured.

for a senior

Show the sequential cutoff, the panic rules, the deadlock warning about one closure waiting on the other, and when rayon::scope or par_sort fits better.

for a principal

Weigh hand-written fork-join against Rayon's built-in parallel algorithms; custom recursion is code to maintain and tune, so it should earn its place with measurements.

## `rayon::join`: two closures, potentially in parallel Parallel iterators cover loops over collections. **Divide and conquer** (quicksort, merge sort, tree traversals, recursive search) needs a different primitive: run two pieces of work and wait for both. Rayon's is ```rust pub fn join<A, B, RA, RB>(oper_a: A, oper_b: B) -> (RA, RB) where A: FnOnce() -> RA + Send, B: FnOnce() -> RB + Send, RA: Send, RB: Send, ``` Its documentation says it takes two closures and **potentially** runs them in parallel, returning both results as a pair. The word "potentially" is the whole design: - Called from a thread inside the pool, `join` runs closure A **on the current thread** and pushes closure B onto that worker's local queue, where an idle worker can **steal** it. - When A finishes, the thread runs B itself if nobody took it; if B was stolen, the thread looks for other work while the thief finishes. - Called from outside the pool (from `main`, say), the calling thread blocks while the two closures run in the pool. So `join` is cheap when every core is busy, roughly a queue push and a pop around two calls, and it becomes real parallelism exactly when a core is idle. That is why a recursive algorithm can call it at every level without flooding the machine with threads. How work stealing balances load in general is covered with parallel scheduling theory; what matters for Rust code is the signature above. ## Why the quicksort compiles without `'static` or `Arc` Compare the bounds with `std::thread::spawn`, which requires a `'static` closure because the thread may outlive the caller. `join` has no `'static` bound: it does not return until both closures have run, so each closure may borrow the caller's data. Each closure must be `Send` because it may move to another worker, and its result must be `Send` because it may come back from one. In the quicksort, `split_at_mut` produces two **disjoint** `&mut [i64]` slices. One closure captures `lo`, the other `hi`, and both are `Send` because `i64: Send`. The borrow checker sees two separate mutable borrows and accepts the call. Capture the *same* variable mutably in both closures and rustc rejects it with **E0499**, "cannot borrow `count` as mutable more than once at a time": the compiler proves that the two halves cannot race. ## Practical rules for recursive `join` 1. **Add a sequential cutoff.** Below a few thousand elements, the bookkeeping of a task is larger than the work; sort small slices with `sort_unstable` instead of recursing. 2. **Both closures always run.** If one panics, `join` still waits for the other and then panics with that payload; if both panic, it propagates the first closure's payload. 3. **Do not block one closure on the other.** The documentation warns that waiting on a channel fed by the sibling closure can deadlock, and that blocking I/O inside `join` hurts performance. 4. **Prefer the built-in when it exists.** For sorting, `par_sort` and `par_sort_unstable` from Rayon's slice traits already do this well. ## `rayon::scope` for a variable number of tasks `join` forks exactly two ways. When the number of tasks is decided at run time, use **`rayon::scope`**. Its closure receives a `&Scope`, and `s.spawn(...)` queues tasks whose bound is `FnOnce(&Scope<'scope>) + Send + 'scope`: they may borrow anything that outlives the scope. `scope` returns only after every spawned task, including tasks spawned by tasks, has completed, and a panic in any of them is propagated from `scope`. | Primitive | Number of tasks | May borrow locals | Returns | |---|---|---|---| | `rayon::join` | exactly two | yes | both results as a tuple | | `rayon::scope` + `s.spawn` | any, decided at run time | yes, for `'scope` | after all tasks finish | | `rayon::spawn` | one, detached | no: `FnOnce() + Send + 'static` | immediately | `rayon::scope` resembles `std::thread::scope` in letting tasks borrow, but its tasks run on Rayon's pool instead of each getting a new OS thread. ## `join` underneath parallel iterators Rayon's parallel iterators are themselves built on this primitive: their internal plumbing splits the input in halves and calls `join_context`, a variant of `join` whose closures are told whether they were stolen, until pieces are small enough to run sequentially. So reach for `join` directly when the data is not a flat collection: a tree walk, a recursive algorithm, or two unrelated computations that should overlap, such as parsing an index while decompressing a payload. For anything shaped like a loop over a slice, a parallel iterator already does the splitting for you.

  • What happens if one of the two closures passed to `rayon::join` panics?
    Both closures are always executed. `join` waits for the other closure to finish and then panics with the panicking closure's payload; if both panic, it propagates the payload from the first closure. So no borrowed data is left in use by a still-running task when the panic unwinds through the caller.
  • Why does a recursive quicksort built on `rayon::join` need a sequential cutoff?
    Each `join` pushes a job and may involve another thread stealing it. For a slice of a few elements that bookkeeping costs more than sorting it. Below a threshold (often a few thousand elements, tuned by measurement) call `sort_unstable` directly, and let `join` split only the large ranges where the parallel work outweighs the overhead.

Two cooks share a kitchen. You start on the first dish and leave the second order on the counter; if a colleague is free they pick it up, otherwise you cook it yourself after the first. Either way, you do not serve until both dishes are done.

  • rayon::join always spawns a new OS thread for each closure
  • join closures need 'static like thread::spawn closures
  • Both closures can capture the same variable mutably
  • join returns as soon as the first closure finishes
  • If closure A panics, closure B is cancelled and skipped