1pub mod fft64;
4pub mod normalize;
5pub mod ntt4x30;
6mod portable;
7pub mod tuning;
8
9pub use portable::{FFT64CIPortableRayon, FFT64PortableRayon, NTT4x30CIPortableRayon, NTT4x30PortableRayon};
10
11#[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 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
45fn 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 use std::sync::OnceLock;
64 use std::sync::atomic::{AtomicU64, AtomicUsize, Ordering};
65 use std::time::{Duration, Instant};
66
67 pub const DEFAULT_IDLE_POLLING: Duration = Duration::from_millis(1);
69
70 static WINDOW_NS: AtomicU64 = AtomicU64::new(DEFAULT_IDLE_POLLING.as_nanos() as u64);
72 static LAST_ACTIVE_NS: AtomicU64 = AtomicU64::new(0);
74 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 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 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 #[cfg(test)]
102 pub(crate) fn pollers() -> usize {
103 POLLERS.load(Ordering::Relaxed)
104 }
105
106 #[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 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 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 #[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
333pub 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
355pub fn workers(cap: usize) -> usize {
357 poulpy_hal::execution::scratch_workers::<RayonTaskExecutor>(cap)
358}
359
360pub 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
368pub trait RayonTuning {
370 const COEFF_MIN_LEN: usize;
371 const COEFF_MIN_TASK: usize;
372 const NORMALIZE_MIN_TASK: usize;
373}
374
375pub 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#[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 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 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}