Skip to main content

poulpy_cpu_rayon/
lib.rs

1//! Rayon-scheduled task executor and backend wrappers shared by the CPU backend crates.
2
3pub mod fft64;
4pub mod normalize;
5pub mod ntt4x30;
6mod portable;
7pub mod tuning;
8
9pub use portable::{FFT64CIPortableRayon, FFT64PortableRayon, NTT4x30CIPortableRayon, NTT4x30PortableRayon};
10
11/// Re-exports for the crate's macros. Not a stable API.
12#[doc(hidden)]
13pub mod __private {
14    pub use ::bytemuck;
15    pub use ::poulpy_cpu_portable;
16    pub use ::poulpy_hal;
17    pub use ::rayon;
18}
19
20use std::cell::Cell;
21
22use poulpy_hal::execution::TaskExecutor;
23
24thread_local! {
25    static TASK_DEPTH: Cell<usize> = const { Cell::new(0) };
26    /// Threads the current task may still fan out to. Zero outside any region: the whole pool.
27    static TASK_BUDGET: Cell<usize> = const { Cell::new(0) };
28}
29
30struct TaskGuard(usize, usize);
31
32impl TaskGuard {
33    fn enter(depth: usize, budget: usize) -> Self {
34        Self(TASK_DEPTH.replace(depth), TASK_BUDGET.replace(budget.max(1)))
35    }
36}
37
38impl Drop for TaskGuard {
39    fn drop(&mut self) {
40        TASK_DEPTH.set(self.0);
41        TASK_BUDGET.set(self.1);
42    }
43}
44
45/// Threads the calling task may fan out to.
46fn task_budget() -> usize {
47    match TASK_BUDGET.get() {
48        0 => ::rayon::current_num_threads().max(1),
49        budget => budget,
50    }
51}
52
53mod idle {
54    //! Idle polling: workers keep looking for work for a short window after the last parallel region.
55    //!
56    //! A homomorphic circuit opens thousands of short parallel regions.
57    //! Rayon puts an idle worker to sleep after a few failed steals, and waking it costs tens of microseconds,
58    //! so each region starts on a few threads and reaches the whole pool late or not at all.
59    //! While the window is open, every worker runs a job that calls `rayon::yield_now` in a loop:
60    //! it executes whatever work appears and never reaches the sleep path.
61    //! The job returns once no region was opened and no work was found for the length of the window.
62
63    use std::sync::OnceLock;
64    use std::sync::atomic::{AtomicU64, AtomicUsize, Ordering};
65    use std::time::{Duration, Instant};
66
67    /// Idle polling window used unless [`set_idle_polling`] changes it.
68    pub const DEFAULT_IDLE_POLLING: Duration = Duration::from_millis(1);
69
70    /// Window in nanoseconds, zero when polling is off.
71    static WINDOW_NS: AtomicU64 = AtomicU64::new(DEFAULT_IDLE_POLLING.as_nanos() as u64);
72    /// Time of the last region opened or of the last work a poller found.
73    static LAST_ACTIVE_NS: AtomicU64 = AtomicU64::new(0);
74    /// Polling jobs that have not returned yet.
75    static POLLERS: AtomicUsize = AtomicUsize::new(0);
76
77    fn now_ns() -> u64 {
78        static START: OnceLock<Instant> = OnceLock::new();
79        START.get_or_init(Instant::now).elapsed().as_nanos() as u64
80    }
81
82    /// Sets how long idle workers keep polling for work after the last parallel region, or turns polling off.
83    ///
84    /// Polling trades processor time for latency: every worker of the pool stays busy for up to `window`
85    /// after each burst of parallel work. Turn it off, or shorten the window, where idle processor time matters
86    /// more than the duration of a computation. The setting is global and takes effect at the next region.
87    pub fn set_idle_polling(window: Option<Duration>) {
88        let ns = window.map_or(0, |w| (w.as_nanos().min(u64::MAX as u128) as u64).max(1));
89        WINDOW_NS.store(ns, Ordering::Relaxed);
90    }
91
92    /// The idle polling window, or `None` when polling is off.
93    pub fn idle_polling() -> Option<Duration> {
94        match WINDOW_NS.load(Ordering::Relaxed) {
95            0 => None,
96            ns => Some(Duration::from_nanos(ns)),
97        }
98    }
99
100    /// Polling jobs currently running.
101    #[cfg(test)]
102    pub(crate) fn pollers() -> usize {
103        POLLERS.load(Ordering::Relaxed)
104    }
105
106    /// Records that a top-level region opens, and starts the polling jobs of the current pool if none runs.
107    #[inline]
108    pub(crate) fn region_opened() {
109        let window = WINDOW_NS.load(Ordering::Relaxed);
110        let workers = ::rayon::current_num_threads();
111        if window == 0 || workers < 2 {
112            return;
113        }
114        LAST_ACTIVE_NS.store(now_ns(), Ordering::Relaxed);
115        if POLLERS.load(Ordering::Relaxed) != 0
116            || POLLERS
117                .compare_exchange(0, workers, Ordering::AcqRel, Ordering::Relaxed)
118                .is_err()
119        {
120            return;
121        }
122        ::rayon::spawn_broadcast(move |_| {
123            let mut idle_rounds = 0u32;
124            loop {
125                if ::rayon::yield_now() == Some(::rayon::Yield::Executed) {
126                    LAST_ACTIVE_NS.store(now_ns(), Ordering::Relaxed);
127                    idle_rounds = 0;
128                    continue;
129                }
130                idle_rounds += 1;
131                // The clock is read once every 64 empty rounds.
132                if idle_rounds.is_multiple_of(64) && now_ns().saturating_sub(LAST_ACTIVE_NS.load(Ordering::Relaxed)) > window {
133                    break;
134                }
135                std::hint::spin_loop();
136            }
137            POLLERS.fetch_sub(1, Ordering::AcqRel);
138        });
139    }
140}
141
142pub use idle::{DEFAULT_IDLE_POLLING, idle_polling, set_idle_polling};
143
144#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
145pub struct RayonTaskExecutor;
146
147impl RayonTaskExecutor {
148    /// Whether a region opened here should run on the calling thread.
149    ///
150    /// One level of nesting is always split, which evens out tasks of unequal cost.
151    /// Deeper levels are split while the enclosing regions leave threads unused:
152    /// four tasks spawned through two joins still have most of the pool to share.
153    pub fn should_serialize_inner() -> bool {
154        TASK_DEPTH.get() > 1 && task_budget() <= 1
155    }
156}
157
158impl TaskExecutor for RayonTaskExecutor {
159    const IS_PARALLEL: bool = true;
160
161    fn is_parallel() -> bool {
162        ::rayon::current_num_threads() > 1
163    }
164
165    fn max_parallelism() -> usize {
166        ::rayon::current_num_threads().max(1)
167    }
168
169    fn join<A, B, RA, RB>(left: A, right: B) -> (RA, RB)
170    where
171        A: FnOnce() -> RA + Send,
172        B: FnOnce() -> RB + Send,
173        RA: Send,
174        RB: Send,
175    {
176        let depth = TASK_DEPTH.get() + 1;
177        if depth == 1 {
178            idle::region_opened();
179        }
180        let budget = task_budget();
181        ::rayon::join(
182            || {
183                let _guard = TaskGuard::enter(depth, budget.div_ceil(2));
184                left()
185            },
186            || {
187                let _guard = TaskGuard::enter(depth, budget / 2);
188                right()
189            },
190        )
191    }
192
193    fn for_each<F>(count: usize, task: F)
194    where
195        F: Fn(usize) + Send + Sync,
196    {
197        use ::rayon::prelude::*;
198        if count == 0 {
199            return;
200        }
201        let min_len = count.div_ceil(::rayon::current_num_threads().max(1));
202        let depth = TASK_DEPTH.get() + 1;
203        if depth == 1 {
204            idle::region_opened();
205        }
206        let budget = task_budget().div_ceil(count.min(::rayon::current_num_threads().max(1)));
207        (0..count).into_par_iter().with_min_len(min_len).for_each(|index| {
208            let _guard = TaskGuard::enter(depth, budget);
209            task(index);
210        });
211    }
212
213    fn for_each_chunked<T, F>(count: usize, scratch: &mut [T], per_worker: usize, task: F)
214    where
215        T: Send,
216        F: Fn(&mut [T], usize) + Send + Sync,
217    {
218        use ::rayon::prelude::*;
219        assert!(
220            scratch.len() >= per_worker,
221            "worker scratch: {} < per_worker {per_worker}",
222            scratch.len()
223        );
224        if count == 0 {
225            return;
226        }
227        let workers = scratch
228            .len()
229            .checked_div(per_worker)
230            .unwrap_or(1)
231            .min(count)
232            .min(::rayon::current_num_threads())
233            .max(1);
234        if workers == 1 {
235            let worker = &mut scratch[..per_worker];
236            for index in 0..count {
237                task(worker, index);
238            }
239            return;
240        }
241        let span = count.div_ceil(workers);
242        let budget = task_budget().div_ceil(workers);
243        let depth = TASK_DEPTH.get() + 1;
244        if depth == 1 {
245            idle::region_opened();
246        }
247        scratch[..workers * per_worker]
248            .par_chunks_mut(per_worker)
249            .enumerate()
250            .for_each(|(worker, buffer)| {
251                let _guard = TaskGuard::enter(depth, budget);
252                let start = worker * span;
253                for index in start..(start + span).min(count) {
254                    task(buffer, index);
255                }
256            });
257    }
258}
259
260#[cfg(test)]
261mod idle_tests {
262    use std::sync::atomic::{AtomicUsize, Ordering};
263    use std::time::{Duration, Instant};
264
265    use poulpy_hal::execution::TaskExecutor;
266
267    use super::{RayonTaskExecutor, idle};
268
269    /// Polling jobs run regions correctly while they are alive, and all return once the pool is quiet.
270    #[test]
271    fn pollers_execute_work_and_stop() {
272        assert_eq!(super::idle_polling(), Some(super::DEFAULT_IDLE_POLLING));
273        let pool = ::rayon::ThreadPoolBuilder::new().num_threads(4).build().unwrap();
274        pool.install(|| {
275            for _ in 0..50 {
276                let sum = AtomicUsize::new(0);
277                <RayonTaskExecutor as TaskExecutor>::for_each(64, |index| {
278                    sum.fetch_add(index, Ordering::Relaxed);
279                });
280                assert_eq!(sum.load(Ordering::Relaxed), 64 * 63 / 2);
281            }
282        });
283        let deadline = Instant::now() + Duration::from_secs(10);
284        while idle::pollers() != 0 {
285            assert!(Instant::now() < deadline, "polling jobs did not stop");
286            std::thread::sleep(Duration::from_millis(1));
287        }
288    }
289}
290
291#[cfg(test)]
292mod tests {
293    use std::sync::{Arc, Barrier};
294
295    use poulpy_hal::execution::TaskExecutor;
296
297    use super::RayonTaskExecutor;
298
299    #[test]
300    fn join_uses_the_active_rayon_pool() {
301        let pool = ::rayon::ThreadPoolBuilder::new().num_threads(2).build().unwrap();
302        let barrier = Arc::new(Barrier::new(2));
303        pool.install(|| {
304            assert!(!RayonTaskExecutor::should_serialize_inner());
305            let left = Arc::clone(&barrier);
306            let right = Arc::clone(&barrier);
307            <RayonTaskExecutor as TaskExecutor>::join(
308                || {
309                    assert!(!RayonTaskExecutor::should_serialize_inner());
310                    left.wait();
311                },
312                || {
313                    assert!(!RayonTaskExecutor::should_serialize_inner());
314                    right.wait();
315                },
316            );
317            assert!(!RayonTaskExecutor::should_serialize_inner());
318            assert_eq!(<RayonTaskExecutor as TaskExecutor>::max_parallelism(), 2);
319
320            <RayonTaskExecutor as TaskExecutor>::join(
321                || {
322                    <RayonTaskExecutor as TaskExecutor>::join(
323                        || assert!(RayonTaskExecutor::should_serialize_inner()),
324                        || assert!(RayonTaskExecutor::should_serialize_inner()),
325                    );
326                },
327                || {},
328            );
329        });
330    }
331}
332
333/// Takes a `len`-element typed slice from the arena.
334pub fn take_scratch<'a, BE, T>(
335    arena: poulpy_hal::layouts::ScratchArena<'a, BE>,
336    len: usize,
337) -> (&'a mut [T], poulpy_hal::layouts::ScratchArena<'a, BE>)
338where
339    BE: poulpy_hal::layouts::Backend + 'a,
340    BE::BufMut<'a>: poulpy_hal::api::HostBufMut<'a>,
341    T: bytemuck::Pod,
342{
343    use poulpy_hal::api::HostBufMut;
344    assert!(BE::SCRATCH_ALIGN.is_multiple_of(std::mem::align_of::<T>()));
345    let byte_len = len
346        .checked_mul(std::mem::size_of::<T>())
347        .expect("typed scratch byte size overflows usize");
348    let (buf, arena) = arena.take_region(byte_len);
349    let bytes: &'a mut [u8] = buf.into_bytes();
350    assert!((bytes.as_mut_ptr() as usize).is_multiple_of(std::mem::align_of::<T>()));
351    let slice = unsafe { std::slice::from_raw_parts_mut(bytes.as_mut_ptr() as *mut T, len) };
352    (slice, arena)
353}
354
355/// Worker slices to size scratch for, capped by the kernel's own bound.
356pub fn workers(cap: usize) -> usize {
357    poulpy_hal::execution::scratch_workers::<RayonTaskExecutor>(cap)
358}
359
360/// Same as [`workers`], bounded by the scratch bytes actually available.
361pub fn workers_within(cap: usize, per_worker: usize, available: usize) -> usize {
362    poulpy_hal::execution::scratch_workers_within::<RayonTaskExecutor>(cap, per_worker, available)
363}
364
365#[doc(hidden)]
366pub use poulpy_cpu_portable::kernels::SendPtr;
367
368/// Backend-local thresholds for Rayon scheduling.
369pub trait RayonTuning {
370    const COEFF_MIN_LEN: usize;
371    const COEFF_MIN_TASK: usize;
372    const NORMALIZE_MIN_TASK: usize;
373}
374
375/// Chunk length for coefficient-wise parallel kernels, or `None` when the slice
376/// is too short to repay scheduling.
377pub fn parallel_chunk_len<B: RayonTuning>(len: usize) -> Option<usize> {
378    if len < B::COEFF_MIN_LEN || ::rayon::current_num_threads() < 2 {
379        return None;
380    }
381    let tasks = ::rayon::current_num_threads().min(len / B::COEFF_MIN_TASK).max(1);
382    Some(len.div_ceil(tasks).next_multiple_of(64))
383}
384
385/// Whether a per-limb task split is worth scheduling.
386#[inline]
387pub fn parallel_limb_tasks(count: usize) -> bool {
388    count > 1 && ::rayon::current_num_threads() > 1
389}
390
391#[cfg(test)]
392mod chunked_tests {
393    use std::collections::BTreeMap;
394    use std::sync::Mutex;
395
396    use poulpy_hal::execution::{TaskExecutor, scratch_workers};
397
398    use super::RayonTaskExecutor;
399
400    /// Records, per worker slice, the indices that ran on it.
401    fn run(threads: usize, count: usize, workers: usize, per_worker: usize) -> BTreeMap<usize, Vec<usize>> {
402        let word = size_of::<usize>();
403        let pool = ::rayon::ThreadPoolBuilder::new().num_threads(threads).build().unwrap();
404        let mut scratch = vec![0usize; workers * per_worker];
405        let base = scratch.as_ptr() as usize;
406        let seen: Mutex<BTreeMap<usize, Vec<usize>>> = Mutex::new(BTreeMap::new());
407        pool.install(|| {
408            RayonTaskExecutor::for_each_chunked(count, &mut scratch, per_worker, |worker, index| {
409                assert_eq!(worker.len(), per_worker);
410                worker[0] = index;
411                // A racing worker would observe a different value here.
412                std::hint::black_box(&worker);
413                assert_eq!(worker[0], index);
414                let offset = worker.as_ptr() as usize - base;
415                assert_eq!(offset % (per_worker * word), 0);
416                seen.lock().unwrap().entry(offset).or_default().push(index);
417            });
418        });
419        seen.into_inner().unwrap()
420    }
421
422    const PER_WORKER: usize = 8;
423
424    #[test]
425    fn every_index_runs_once_on_a_disjoint_worker_slice() {
426        let seen = run(4, 100, 4, PER_WORKER);
427        let mut indices: Vec<usize> = seen.values().flatten().copied().collect();
428        indices.sort_unstable();
429        assert_eq!(indices, (0..100).collect::<Vec<_>>());
430        assert!(seen.len() > 1, "expected several worker slices, got {}", seen.len());
431        let offsets: Vec<usize> = seen.keys().copied().collect();
432        let stride = PER_WORKER * size_of::<usize>();
433        for pair in offsets.windows(2) {
434            assert!(pair[1] - pair[0] >= stride, "worker slices overlap");
435        }
436    }
437
438    #[test]
439    fn a_single_thread_pool_uses_one_worker_slice() {
440        assert_eq!(run(1, 32, 4, 8).len(), 1);
441    }
442
443    #[test]
444    fn worker_count_never_exceeds_the_scratch_it_was_given() {
445        assert_eq!(run(8, 32, 2, 8).len(), 2);
446        assert_eq!(run(8, 3, 8, 8).len(), 3);
447    }
448
449    #[test]
450    fn zero_tasks_run_nothing() {
451        assert!(run(4, 0, 4, 8).is_empty());
452    }
453
454    #[test]
455    #[should_panic(expected = "worker scratch")]
456    fn undersized_scratch_is_rejected() {
457        let mut scratch = [0usize; 4];
458        RayonTaskExecutor::for_each_chunked(1, &mut scratch, 8, |_, _| {});
459    }
460
461    #[test]
462    fn scratch_sizing_is_the_callers_cap_and_pool_independent() {
463        assert_eq!(scratch_workers::<RayonTaskExecutor>(4), 4);
464        assert_eq!(scratch_workers::<RayonTaskExecutor>(0), 1);
465        let pool = ::rayon::ThreadPoolBuilder::new().num_threads(1).build().unwrap();
466        pool.install(|| assert_eq!(scratch_workers::<RayonTaskExecutor>(8), 8));
467    }
468}