1use crate::cost::KernelClass;
10pub(crate) use crate::cost::{for_len, is_parallel};
11use crate::inline::InlineVec;
12use crate::kernel::for_each_inner_block_preordered;
13use crate::Result;
14use core::num::NonZeroUsize;
15use std::ops::Range;
16use threadteam::Exec;
17
18type SVec<T> = InlineVec<T>;
21
22const ONE: NonZeroUsize = NonZeroUsize::MIN;
23
24pub struct SendPtr<T>(pub *mut T);
41
42impl<T> Clone for SendPtr<T> {
43 fn clone(&self) -> Self {
44 *self
45 }
46}
47
48impl<T> Copy for SendPtr<T> {}
49
50unsafe impl<T> Send for SendPtr<T> {}
51unsafe impl<T> Sync for SendPtr<T> {}
52
53impl<T> SendPtr<T> {
54 pub fn as_ptr(self) -> *mut T {
55 self.0
56 }
57
58 pub fn as_const(self) -> *const T {
59 self.0 as *const T
60 }
61}
62
63impl<T> core::fmt::Debug for SendPtr<T> {
64 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
65 f.debug_tuple("SendPtr").field(&self.0).finish()
66 }
67}
68
69fn scheduler_blocks(dims: &[usize], blocks: &[usize]) -> SVec<usize> {
78 dims.iter()
79 .zip(blocks)
80 .map(|(&dim, &block)| {
81 if dim > 1 && dim <= block.min(1024) {
82 (dim / 2).max(1)
83 } else {
84 block
85 }
86 })
87 .collect()
88}
89
90fn fork2<R: Send>(
94 exec: Exec<'_>,
95 left: impl Fn(Exec<'_>) -> R + Sync,
96 right: impl Fn(Exec<'_>) -> R + Sync,
97) -> (R, R) {
98 struct Slot<T>(core::cell::UnsafeCell<Option<T>>);
101 unsafe impl<T: Send> Sync for Slot<T> {}
104 let slots = [Slot(Default::default()), Slot(Default::default())];
105 exec.fork(2, |i, child| {
106 let value = if i == 0 { left(child) } else { right(child) };
107 unsafe { *slots[i].0.get() = Some(value) };
109 });
110 let [left, right] = slots.map(|slot| {
111 slot.0
112 .into_inner()
113 .expect("every fork job stores its result")
114 });
115 (left, right)
116}
117
118pub fn parallel_map_reduce<R, Map, Reduce>(
135 range: Range<usize>,
136 exec: Exec<'_>,
137 map: &Map,
138 reduce: &Reduce,
139) -> R
140where
141 R: Send,
142 Map: Fn(Range<usize>) -> R + Sync,
143 Reduce: Fn(R, R) -> R + Sync,
144{
145 let len = range.end - range.start;
146 let budget = exec.budget().get();
147 if budget <= 1 || len <= 1 {
148 return map(range);
149 }
150
151 let left_threads = budget.div_ceil(2);
152 let left_len = len * left_threads / budget;
153 let middle = range.start + left_len.max(1).min(len - 1);
154 let left_range = range.start..middle;
155 let right_range = middle..range.end;
156
157 let (left, right) = fork2(
158 exec,
159 |child| parallel_map_reduce(left_range.clone(), child, map, reduce),
160 |child| parallel_map_reduce(right_range.clone(), child, map, reduce),
161 );
162 reduce(left, right)
163}
164
165pub(crate) fn parallel_for_each<F>(range: Range<usize>, exec: Exec<'_>, operation: &F)
168where
169 F: Fn(Range<usize>) + Sync,
170{
171 let start = range.start;
172 #[cfg(test)]
173 let chunks = core::sync::atomic::AtomicUsize::new(0);
174 exec.for_ranges(range.end - range.start, ONE, |chunk| {
175 #[cfg(test)]
176 chunks.fetch_add(1, core::sync::atomic::Ordering::Relaxed);
177 operation(start + chunk.start..start + chunk.end)
178 });
179 #[cfg(test)]
180 DISPATCHED_CHUNKS.with(|n| n.set(n.get() + chunks.into_inner()));
181}
182
183#[cfg(test)]
187thread_local! {
188 static DISPATCHED_CHUNKS: core::cell::Cell<usize> = const { core::cell::Cell::new(0) };
189}
190
191#[cfg(test)]
194pub(crate) fn take_dispatched_chunks() -> usize {
195 DISPATCHED_CHUNKS.with(|n| n.replace(0))
196}
197
198pub(crate) unsafe fn copy_contiguous<T: Copy + Send + Sync>(
208 src: *const T,
209 dst: *mut T,
210 len: usize,
211 exec: Exec<'_>,
212) {
213 let exec = for_len(exec, KernelClass::Copy, len);
214 if !exec.is_serial() {
215 let src = SendPtr(src as *mut T);
216 let dst = SendPtr(dst);
217 parallel_for_each(0..len, exec, &|range| {
218 unsafe {
222 core::ptr::copy_nonoverlapping(
223 src.as_const().add(range.start),
224 dst.as_ptr().add(range.start),
225 range.len(),
226 );
227 }
228 });
229 return;
230 }
231 unsafe { core::ptr::copy_nonoverlapping(src, dst, len) };
233}
234
235pub(crate) fn fill_contiguous<T: Copy + Send + Sync>(dst: &mut [T], value: T, exec: Exec<'_>) {
238 let len = dst.len();
239 let exec = for_len(exec, KernelClass::Copy, len);
240 if !exec.is_serial() {
241 let dst = SendPtr(dst.as_mut_ptr());
242 parallel_for_each(0..len, exec, &|range| {
243 let chunk = unsafe {
246 core::slice::from_raw_parts_mut(dst.as_ptr().add(range.start), range.len())
247 };
248 chunk.fill(value);
249 });
250 return;
251 }
252 dst.fill(value);
253}
254
255pub(crate) unsafe fn fill_contiguous_uninit<T: Copy + Send + Sync>(
267 dst: *mut T,
268 len: usize,
269 value: T,
270 exec: Exec<'_>,
271) {
272 let span =
275 unsafe { core::slice::from_raw_parts_mut(dst.cast::<core::mem::MaybeUninit<T>>(), len) };
276 fill_contiguous(span, core::mem::MaybeUninit::new(value), exec);
277}
278
279pub(crate) fn copy_permuted<T: Copy + Send + Sync + 'static>(
285 dest: &mut crate::StridedViewMut<T>,
286 src: &crate::StridedView<T>,
287 exec: Exec<'_>,
288) -> crate::Result<()> {
289 strided_perm::copy_into(dest, src, exec)
290}
291
292pub(crate) fn copy_permuted_uninit<T: Copy + Send + Sync + 'static>(
299 dest: &mut crate::StridedViewMut<core::mem::MaybeUninit<T>>,
300 src: &crate::StridedView<T>,
301 exec: Exec<'_>,
302) -> crate::Result<()> {
303 strided_perm::copy_into_uninit(dest, src, exec)
304}
305
306fn split_axis(dims: &[usize], blocks: &[usize], costs: &[isize]) -> Option<usize> {
314 let (i, _) = dims.iter().zip(costs.iter()).enumerate().fold(
315 (0, 0u128),
316 |(best_i, best_v), (idx, (&d, &c))| {
317 let score = d.saturating_sub(1) as u128 * c as u128;
318 if score >= best_v {
319 (idx, score)
320 } else {
321 (best_i, best_v)
322 }
323 },
324 );
325 (costs[i] != 0 && dims[i] > blocks[i].min(1024)).then_some(i)
326}
327
328fn halves(
331 dims: &[usize],
332 offsets: &[isize],
333 strides_list: &[&[isize]],
334 i: usize,
335) -> (SVec<usize>, SVec<usize>, SVec<isize>) {
336 let di = dims[i];
337 let ndi = di / 2;
338 let mut left_dims: SVec<usize> = dims.iter().copied().collect();
339 left_dims[i] = ndi;
340 let mut right_dims: SVec<usize> = dims.iter().copied().collect();
341 right_dims[i] = di - ndi;
342 let mut right_offsets: SVec<isize> = offsets.iter().copied().collect();
343 for (k, strides) in strides_list.iter().enumerate() {
344 right_offsets[k] += ndi as isize * strides[i];
345 }
346 (left_dims, right_dims, right_offsets)
347}
348
349#[allow(clippy::too_many_arguments)]
368pub(crate) fn mapreduce_threaded<S: AsRef<[isize]>, F>(
369 dims: &[usize],
370 blocks: &[usize],
371 strides_list: &[S],
372 offsets: &[isize],
373 costs: &[isize],
374 class: KernelClass,
375 exec: Exec<'_>,
376 f: &F,
377) -> Result<()>
378where
379 F: Fn(&[usize], &[usize], &[&[isize]], &[isize]) -> Result<()> + Sync,
380{
381 let refs: SVec<&[isize]> = strided_slices(strides_list);
386 mapreduce_threaded_dyn(dims, blocks, &refs, offsets, costs, class, exec, f)
387}
388
389fn strided_slices<S: AsRef<[isize]>>(strides_list: &[S]) -> SVec<&[isize]> {
390 strides_list.iter().map(|s| s.as_ref()).collect()
391}
392
393type LeafFn<'a> = &'a (dyn Fn(&[usize], &[usize], &[&[isize]], &[isize]) -> Result<()> + Sync);
395
396#[allow(clippy::too_many_arguments)]
398#[inline(never)]
399fn mapreduce_threaded_dyn(
400 dims: &[usize],
401 blocks: &[usize],
402 strides_list: &[&[isize]],
403 offsets: &[isize],
404 costs: &[isize],
405 class: KernelClass,
406 exec: Exec<'_>,
407 f: LeafFn<'_>,
408) -> Result<()> {
409 let blocks = scheduler_blocks(dims, blocks);
414 ThreadedMapReduce {
415 blocks: &blocks,
416 strides_list,
417 costs,
418 class,
419 operation: f,
420 }
421 .run(dims, offsets, exec)
422}
423
424struct ThreadedMapReduce<'a> {
425 blocks: &'a [usize],
426 strides_list: &'a [&'a [isize]],
427 costs: &'a [isize],
428 class: KernelClass,
429 operation: LeafFn<'a>,
430}
431
432impl ThreadedMapReduce<'_> {
433 fn run(&self, dims: &[usize], offsets: &[isize], exec: Exec<'_>) -> Result<()> {
434 let total = crate::kernel::total_len(dims)?;
435
436 if !is_parallel(self.class, total, &exec) {
438 return (self.operation)(dims, self.blocks, self.strides_list, offsets);
439 }
440 let Some(i) = split_axis(dims, self.blocks, self.costs) else {
441 return (self.operation)(dims, self.blocks, self.strides_list, offsets);
442 };
443
444 let (left_dims, right_dims, right_offsets) = halves(dims, offsets, self.strides_list, i);
445 let (r1, r2) = fork2(
446 exec,
447 |child| self.run(&left_dims, offsets, child),
448 |child| self.run(&right_dims, &right_offsets, child),
449 );
450 r1?;
451 r2?;
452 Ok(())
453 }
454}
455
456#[allow(clippy::too_many_arguments)]
466pub(crate) fn mapreduce_threaded_fold<S, F, C, R>(
467 dims: &[usize],
468 blocks: &[usize],
469 strides_list: &[S],
470 offsets: &[isize],
471 costs: &[isize],
472 class: KernelClass,
473 exec: Exec<'_>,
474 f: &F,
475 combine: &C,
476) -> Result<R>
477where
478 S: AsRef<[isize]>,
479 F: Fn(&[usize], &[usize], &[&[isize]], &[isize]) -> Result<R> + Sync,
480 C: Fn(R, R) -> R + Sync,
481 R: Send,
482{
483 let refs: SVec<&[isize]> = strided_slices(strides_list);
484 let blocks = scheduler_blocks(dims, blocks);
488 FoldMapReduce {
489 blocks: &blocks,
490 strides_list: &refs,
491 costs,
492 class,
493 f,
494 combine,
495 }
496 .run(dims, offsets, exec)
497}
498
499struct FoldMapReduce<'a, F, C> {
500 blocks: &'a [usize],
501 strides_list: &'a [&'a [isize]],
502 costs: &'a [isize],
503 class: KernelClass,
504 f: &'a F,
505 combine: &'a C,
506}
507
508impl<F, C> FoldMapReduce<'_, F, C> {
509 fn run<R: Send>(&self, dims: &[usize], offsets: &[isize], exec: Exec<'_>) -> Result<R>
510 where
511 F: Fn(&[usize], &[usize], &[&[isize]], &[isize]) -> Result<R> + Sync,
512 C: Fn(R, R) -> R + Sync,
513 {
514 let total = crate::kernel::total_len(dims)?;
515
516 if !is_parallel(self.class, total, &exec) {
518 return (self.f)(dims, self.blocks, self.strides_list, offsets);
519 }
520 let Some(i) = split_axis(dims, self.blocks, self.costs) else {
521 return (self.f)(dims, self.blocks, self.strides_list, offsets);
522 };
523
524 let (left_dims, right_dims, right_offsets) = halves(dims, offsets, self.strides_list, i);
526 let (r1, r2) = fork2(
527 exec,
528 |child| self.run(&left_dims, offsets, child),
529 |child| self.run(&right_dims, &right_offsets, child),
530 );
531 Ok((self.combine)(r1?, r2?))
532 }
533}
534
535pub(crate) fn for_each_inner_block_with_offsets<S: AsRef<[isize]>, F>(
541 dims: &[usize],
542 blocks: &[usize],
543 strides_list: &[S],
544 initial_offsets: &[isize],
545 f: F,
546) -> Result<()>
547where
548 F: FnMut(&[isize], usize, &[isize]) -> Result<()>,
549{
550 for_each_inner_block_preordered(dims, blocks, strides_list, initial_offsets, f)
551}
552
553#[cfg(test)]
555pub(crate) fn test_pool(threads: usize) -> threadteam::Pool {
556 threadteam::Pool::builder()
557 .threads(threads)
558 .dispatch_costs(test_dispatch_costs())
559 .build()
560 .unwrap()
561}
562
563#[cfg(test)]
567pub(crate) fn test_dispatch_costs() -> threadteam::DispatchCosts {
568 use threadteam::{DispatchKind, WidthCosts};
569 let cheap = WidthCosts::flat(core::time::Duration::from_nanos(100));
570 threadteam::DispatchCosts::for_class(threadteam::HostClass::Generic)
571 .with(DispatchKind::Team, cheap)
572 .with(DispatchKind::InPool, cheap)
573 .with(DispatchKind::Outside, cheap)
574}
575
576#[cfg(test)]
584pub(crate) fn run_serial_and_parallel<R: Send>(operation: impl Fn(Exec<'_>) -> R + Sync) -> (R, R) {
585 let serial = operation(Exec::serial());
586 let pool = test_pool(4);
587 let exec = Exec::new(&pool, 4).unwrap();
588 assert_eq!(
589 crate::cost::parallel_width(&exec, KernelClass::Map, 1 << 20).get(),
590 exec.budget().get()
591 );
592 let parallel = operation(exec);
593 (serial, parallel)
594}
595
596#[cfg(test)]
597#[path = "threading/tests/tests.rs"]
598mod tests;