sparse_ir_sve/parallel.rs
1//! Parallel execution on the rayon thread pool.
2//!
3//! The threaded work of this crate (the SVE) goes through the functions
4//! here. Without the `parallel` feature (the default; never enabled by the
5//! C API of sparse-ir), and inside [`sequential`], it runs on the calling
6//! thread. (The SVDs of the fitters of sparse-ir go through tenferro's
7//! `CpuBackend`, which has a pool of its own, outside these functions; see
8//! #344.)
9//! With the feature it runs on the current rayon pool (the global one unless
10//! the caller runs inside `ThreadPool::install`), whose size
11//! (`RAYON_NUM_THREADS`) therefore bounds the number of threads the library
12//! uses.
13//!
14//! Every job handed out here runs under the FPU state of the thread that
15//! hands it out (`crate::fpu_check::FpuContext`), so the threaded paths
16//! compute exactly what the serial ones would. They are used only where each
17//! value is computed by the same operations whatever the threading, so the
18//! results do not depend on the number of threads.
19//!
20//! Each parallel region states its estimated work in `f64` operations and
21//! runs on the calling thread below the one threshold [`PARALLEL_MIN_WORK`]
22//! (or with a single thread).
23//!
24//! Internal to the sparse-ir crates; not part of the public API.
25
26use std::cell::Cell;
27
28thread_local! {
29 /// Whether the calling thread is inside [`sequential`]
30 static SEQUENTIAL: Cell<bool> = const { Cell::new(false) };
31}
32
33/// Run `f` with all the parallel regions it reaches on the calling thread,
34/// even with the `parallel` feature (as the C API does for every call)
35pub fn sequential<R>(f: impl FnOnce() -> R) -> R {
36 /// Restores the previous state, also when `f` panics
37 struct Restore(bool);
38 impl Drop for Restore {
39 fn drop(&mut self) {
40 SEQUENTIAL.with(|s| s.set(self.0));
41 }
42 }
43 let _restore = Restore(SEQUENTIAL.with(|s| s.replace(true)));
44 f()
45}
46
47/// Number of threads the parallel regions may use: that of the current
48/// rayon pool, or 1 without the `parallel` feature or inside [`sequential`]
49pub fn n_threads() -> usize {
50 if SEQUENTIAL.with(Cell::get) {
51 return 1;
52 }
53 #[cfg(feature = "parallel")]
54 {
55 rayon::current_num_threads()
56 }
57 #[cfg(not(feature = "parallel"))]
58 {
59 1
60 }
61}
62
63/// Parallel regions with less work than this, in `f64` operations, run on the
64/// calling thread (dispatching to the pool would cost more than it saves).
65/// On an M1 Pro, `compute_sve` was fastest at about this threshold both in
66/// `f64` (ε ≥ 10⁻⁸) and, counting a double-double operation as 16 `f64`
67/// ones, in double-double.
68pub const PARALLEL_MIN_WORK: usize = 1 << 19;
69
70/// Whether a region of `work` `f64` operations goes to the pool
71fn on_pool(work: usize) -> bool {
72 n_threads() > 1 && work >= PARALLEL_MIN_WORK
73}
74
75/// [`for_each_chunk`] splits its work into this many chunks per thread, so
76/// that idle threads take over the chunks of slower ones (on a CPU with
77/// performance and efficiency cores, the latter would otherwise hold up the
78/// whole region). On an M1 Pro, this made the double-double `compute_sve`
79/// 10–15 % faster on 8 threads than one chunk per thread.
80const CHUNKS_PER_THREAD: usize = 4;
81
82/// Run `jobs` on the rayon pool and wait for all of them. Pool threads do not
83/// have the caller's FPU state, so every job runs under it. Without the
84/// `parallel` feature, or with a single thread, the jobs run in order on the
85/// calling thread.
86pub fn run_on_pool<'a, F: FnOnce() + Send + 'a>(jobs: impl IntoIterator<Item = F>) {
87 #[cfg(feature = "parallel")]
88 if n_threads() > 1 {
89 // Collected first: the scope closure must be `Send`, the iterator need not be.
90 let jobs: Vec<F> = jobs.into_iter().collect();
91 let fpu = crate::fpu_check::FpuContext::current();
92 rayon::scope(|scope| {
93 for job in jobs {
94 scope.spawn(move |_| fpu.run(job));
95 }
96 });
97 return;
98 }
99 for job in jobs {
100 job();
101 }
102}
103
104/// Run `f(start, chunk)` over contiguous chunks of `out`, where `start` is the
105/// index of `chunk[0]` in `out`; on the thread pool when `work` (in `f64`
106/// operations) is large. Each element must depend only on its own
107/// index, so the result does not depend on the chunking.
108pub fn for_each_chunk<T: Send>(out: &mut [T], work: usize, f: impl Fn(usize, &mut [T]) + Sync) {
109 if out.len() <= 1 || !on_pool(work) {
110 f(0, out);
111 return;
112 }
113 let chunk_len = out
114 .len()
115 .div_ceil(n_threads().min(out.len()) * CHUNKS_PER_THREAD);
116 let f = &f;
117 run_on_pool(
118 out.chunks_mut(chunk_len)
119 .enumerate()
120 .map(|(c, chunk)| move || f(c * chunk_len, chunk)),
121 );
122}
123
124/// `[f(0), ..., f(n - 1)]`, one pool job per item when `work` (in `f64`
125/// operations, for all items) is large
126///
127/// A single large item goes to the pool too: the parallel regions inside it
128/// then start from a pool thread, which is cheaper than from outside the
129/// pool (on an M1 Pro, 3 % of a double-double SVE of a single block).
130pub fn map_on_pool<R: Send>(n: usize, work: usize, f: impl Fn(usize) -> R + Sync) -> Vec<R> {
131 if !on_pool(work) {
132 return (0..n).map(f).collect();
133 }
134 let mut slots: Vec<Option<R>> = (0..n).map(|_| None).collect();
135 let f = &f;
136 run_on_pool(
137 slots
138 .iter_mut()
139 .enumerate()
140 .map(|(i, slot)| move || *slot = Some(f(i))),
141 );
142 slots
143 .into_iter()
144 .map(|r| r.expect("every job has run"))
145 .collect()
146}
147
148#[cfg(test)]
149mod tests {
150 use super::*;
151
152 /// `for_each_chunk` hands each chunk its offset in the whole slice, so
153 /// the pool result equals the one computed on the calling thread.
154 #[test]
155 fn for_each_chunk_matches_serial() {
156 let fill = |work| {
157 let mut out = vec![0.0f64; 10_000];
158 for_each_chunk(&mut out, work, |start, chunk| {
159 for (i, x) in chunk.iter_mut().enumerate() {
160 *x = ((start + i) as f64 * 0.37).sin();
161 }
162 });
163 out
164 };
165 assert_eq!(fill(usize::MAX), fill(0));
166 assert_eq!(fill(0)[9_999], (9_999.0f64 * 0.37).sin());
167 }
168
169 #[test]
170 fn map_on_pool_keeps_the_order() {
171 assert_eq!(
172 map_on_pool(100, usize::MAX, |i| i * i),
173 (0..100).map(|i| i * i).collect::<Vec<_>>()
174 );
175 assert!(map_on_pool(0, usize::MAX, |i| i).is_empty());
176 assert_eq!(map_on_pool(3, 0, |i| i), vec![0, 1, 2]);
177 }
178
179 /// A single large item runs on a pool thread, a small one on the caller's
180 /// (a test thread, outside the pool).
181 #[cfg(feature = "parallel")]
182 #[test]
183 fn map_on_pool_sends_a_single_large_item_to_the_pool() {
184 let thread_index = |work| map_on_pool(1, work, |_| rayon::current_thread_index())[0];
185 assert_eq!(thread_index(0), None);
186 if n_threads() > 1 {
187 assert!(thread_index(usize::MAX).is_some());
188 }
189 }
190
191 /// Inside `ThreadPool::install`, the library uses that pool's threads.
192 #[cfg(feature = "parallel")]
193 #[test]
194 fn uses_the_installed_pool() {
195 let pool = rayon::ThreadPoolBuilder::new()
196 .num_threads(1)
197 .build()
198 .unwrap();
199 pool.install(|| {
200 assert_eq!(n_threads(), 1);
201 let ids = map_on_pool(8, usize::MAX, |_| std::thread::current().id());
202 assert!(ids.iter().all(|id| *id == ids[0]));
203 });
204 }
205
206 /// Inside `sequential` everything runs on the calling thread, also with
207 /// the `parallel` feature and a large pool, and also in nested calls; the
208 /// state is restored afterwards, also after a panic.
209 #[test]
210 fn sequential_runs_on_the_calling_thread() {
211 let caller = std::thread::current().id();
212 let on_caller = || {
213 map_on_pool(16, usize::MAX, |_| std::thread::current().id())
214 .iter()
215 .all(|id| *id == caller)
216 };
217 sequential(|| {
218 assert_eq!(n_threads(), 1);
219 assert!(on_caller());
220 sequential(|| assert!(on_caller()));
221 assert_eq!(n_threads(), 1);
222 });
223 let panicked = std::panic::catch_unwind(|| sequential(|| panic!("in sequential")));
224 assert!(panicked.is_err());
225 assert!(!SEQUENTIAL.with(Cell::get));
226 #[cfg(not(feature = "parallel"))]
227 assert_eq!(n_threads(), 1);
228 }
229}