Skip to main content

linkcell/
team.rs

1//! One parallel region per search.
2//!
3//! A search is a list of stages, each a number of chunks. Every worker
4//! claims chunks of the open stage from one counter, and the worker that
5//! finishes the last chunk opens the next stage, so a stage boundary waits
6//! for the chunks in flight and for no worker that has not started. The
7//! caller is one of the workers. The others are detached jobs on the pool:
8//! one that starts after the last stage has closed finds no chunk and
9//! returns without touching the caller's data, so the call never waits for
10//! a worker the scheduler has not run yet.
11//!
12//! A worker with nothing to claim spins briefly, then yields, then sleeps
13//! on a condvar until the stage it is waiting on closes. The wait does not
14//! depend on `OMP_WAIT_POLICY` or on Rayon's idle loop: on a machine whose
15//! cpus are all busy, a sleeping worker leaves its cpu to the worker that
16//! still holds a chunk.
17
18use std::panic::{catch_unwind, resume_unwind, AssertUnwindSafe};
19use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
20use std::sync::{Arc, Condvar, Mutex};
21
22/// One stage: `chunks` calls of `run(scratch, chunk)`, any order, any worker.
23pub(crate) struct Stage<'a, S> {
24    pub chunks: usize,
25    pub run: &'a (dyn Fn(&mut S, usize) + Sync),
26}
27
28/// Starts one detached job on the pool that owns the search.
29pub(crate) type Spawn<'a> = &'a dyn Fn(Box<dyn FnOnce() + Send + 'static>);
30
31type Erased<S> = *const (dyn Fn(&mut S, usize) + Sync + 'static);
32
33struct Shared<S> {
34    run: Vec<Erased<S>>,
35    chunks: Vec<usize>,
36    next: Vec<AtomicUsize>,
37    done: Vec<AtomicUsize>,
38    phase: AtomicUsize,
39    sleepers: AtomicUsize,
40    failed: AtomicBool,
41    failure: Mutex<Option<Box<dyn std::any::Any + Send>>>,
42    lock: Mutex<()>,
43    wake: Condvar,
44}
45
46// SAFETY: `run` points at the caller's `Sync` closures. A worker calls one
47// only after it has claimed a chunk of an open stage, and the caller does
48// not return before every claimed chunk is done (see `work`).
49unsafe impl<S> Send for Shared<S> {}
50unsafe impl<S> Sync for Shared<S> {}
51
52/// Spins on the stage counter before yielding. About 20 microseconds of
53/// `pause`, the length of a short stage tail on an idle machine.
54const SPINS: u32 = 1 << 9;
55/// Yields before sleeping.
56const YIELDS: u32 = 16;
57
58impl<S> Shared<S> {
59    fn wait_past(&self, stage: usize) {
60        for _ in 0..SPINS {
61            if self.phase.load(Ordering::Acquire) > stage {
62                return;
63            }
64            std::hint::spin_loop();
65        }
66        for _ in 0..YIELDS {
67            if self.phase.load(Ordering::Acquire) > stage {
68                return;
69            }
70            std::thread::yield_now();
71        }
72        let mut guard = self.lock.lock().unwrap_or_else(|err| err.into_inner());
73        self.sleepers.fetch_add(1, Ordering::SeqCst);
74        while self.phase.load(Ordering::SeqCst) <= stage {
75            guard = self.wake.wait(guard).unwrap_or_else(|err| err.into_inner());
76        }
77        self.sleepers.fetch_sub(1, Ordering::SeqCst);
78    }
79
80    fn open(&self, stage: usize) {
81        self.phase.store(stage, Ordering::SeqCst);
82        if self.sleepers.load(Ordering::SeqCst) > 0 {
83            drop(self.lock.lock().unwrap_or_else(|err| err.into_inner()));
84            self.wake.notify_all();
85        }
86    }
87}
88
89/// Claim and run chunks until the last stage has closed.
90fn work<S: Default>(shared: &Shared<S>) {
91    let stages = shared.chunks.len();
92    let mut scratch: Option<S> = None;
93    loop {
94        let p = shared.phase.load(Ordering::Acquire);
95        if p >= stages {
96            return;
97        }
98        let c = shared.next[p].fetch_add(1, Ordering::Relaxed);
99        if c >= shared.chunks[p] {
100            shared.wait_past(p);
101            continue;
102        }
103        if !shared.failed.load(Ordering::Relaxed) {
104            let s = scratch.get_or_insert_with(S::default);
105            // SAFETY: chunk `c` of open stage `p` is claimed and not done,
106            // so the caller is still inside `run` and the closure is live.
107            let f = unsafe { &*shared.run[p] };
108            if let Err(err) = catch_unwind(AssertUnwindSafe(|| f(s, c))) {
109                shared.failed.store(true, Ordering::Relaxed);
110                let mut slot = shared.failure.lock().unwrap_or_else(|e| e.into_inner());
111                slot.get_or_insert(err);
112            }
113        }
114        if shared.done[p].fetch_add(1, Ordering::AcqRel) + 1 == shared.chunks[p] {
115            shared.open(p + 1);
116        }
117    }
118}
119
120/// Run `stages` in order on `width` workers, the caller one of them.
121/// Every chunk of a stage finishes before any chunk of the next starts.
122/// No more workers start than the largest stage has chunks; one worker,
123/// or no pool, runs everything on the caller.
124pub(crate) fn run<S: Default + 'static>(
125    width: usize,
126    spawn: Option<Spawn<'_>>,
127    stages: &[Stage<'_, S>],
128) {
129    let most = stages.iter().map(|s| s.chunks).max().unwrap_or(0);
130    let width = width.min(most);
131    let spawn = match spawn {
132        Some(spawn) if width > 1 => spawn,
133        _ => {
134            let mut scratch = S::default();
135            for stage in stages {
136                for c in 0..stage.chunks {
137                    (stage.run)(&mut scratch, c);
138                }
139            }
140            return;
141        }
142    };
143    // A stage with no chunks would never be closed by a worker.
144    let chunks: Vec<usize> = stages.iter().map(|s| s.chunks.max(1)).collect();
145    let empty = |_: &mut S, _: usize| {};
146    let run = stages
147        .iter()
148        .map(|s| {
149            let f: &(dyn Fn(&mut S, usize) + Sync) = if s.chunks == 0 { &empty } else { s.run };
150            // SAFETY: lifetime erased; see `Shared`.
151            unsafe {
152                std::mem::transmute::<*const (dyn Fn(&mut S, usize) + Sync + '_), Erased<S>>(f)
153            }
154        })
155        .collect();
156    let shared = Arc::new(Shared {
157        run,
158        next: chunks.iter().map(|_| AtomicUsize::new(0)).collect(),
159        done: chunks.iter().map(|_| AtomicUsize::new(0)).collect(),
160        chunks,
161        phase: AtomicUsize::new(0),
162        sleepers: AtomicUsize::new(0),
163        failed: AtomicBool::new(false),
164        failure: Mutex::new(None),
165        lock: Mutex::new(()),
166        wake: Condvar::new(),
167    });
168    for _ in 1..width {
169        let mine = Arc::clone(&shared);
170        spawn(Box::new(move || work(&mine)));
171    }
172    work(&shared);
173    let failure = shared
174        .failure
175        .lock()
176        .unwrap_or_else(|e| e.into_inner())
177        .take();
178    if let Some(err) = failure {
179        resume_unwind(err);
180    }
181}
182
183type ErasedSpawn = *const (dyn Fn(Box<dyn FnOnce() + Send + 'static>) + 'static);
184
185thread_local! {
186    static INSTALLED: std::cell::Cell<Option<(usize, ErasedSpawn)>> =
187        const { std::cell::Cell::new(None) };
188}
189
190/// Searches `body` starts on this thread use `width` workers started by
191/// `spawn`, until `body` returns.
192#[cfg_attr(not(all(feature = "capi", feature = "parallel")), allow(dead_code))]
193pub(crate) fn install<R>(width: usize, spawn: Spawn<'_>, body: impl FnOnce() -> R) -> R {
194    struct Restore(Option<(usize, ErasedSpawn)>);
195    impl Drop for Restore {
196        fn drop(&mut self) {
197            INSTALLED.with(|slot| slot.set(self.0));
198        }
199    }
200    // SAFETY: lifetime erased; the slot is restored before `spawn` dies.
201    let erased = unsafe {
202        std::mem::transmute::<*const (dyn Fn(Box<dyn FnOnce() + Send + 'static>) + '_), ErasedSpawn>(
203            spawn,
204        )
205    };
206    let _restore = Restore(INSTALLED.with(|slot| slot.replace(Some((width, erased)))));
207    body()
208}
209
210/// Whether a caller on this thread chose the workers with [`install`].
211#[cfg(linkcell_openmp)]
212pub(crate) fn installed() -> bool {
213    INSTALLED.with(|slot| slot.get()).is_some()
214}
215
216/// Workers and pool for a search on this thread: the ones [`install`]
217/// set, or else the current Rayon pool.
218pub(crate) fn with_current<R>(body: impl FnOnce(usize, Option<Spawn<'_>>) -> R) -> R {
219    if let Some((width, spawn)) = INSTALLED.with(|slot| slot.get()) {
220        // SAFETY: `install` is still running on this thread.
221        let spawn: Spawn<'_> = unsafe { &*spawn };
222        return body(width, Some(spawn));
223    }
224    #[cfg(feature = "parallel")]
225    {
226        let spawn = |job: Box<dyn FnOnce() + Send + 'static>| rayon::spawn(job);
227        body(rayon::current_num_threads(), Some(&spawn))
228    }
229    #[cfg(not(feature = "parallel"))]
230    {
231        body(1, None)
232    }
233}