1use crate::cost::KernelClass;
10pub(crate) use crate::cost::{for_len, is_parallel, is_parallel_at_rate};
11use crate::inline::InlineVec;
12use crate::kernel::for_each_inner_block_preordered;
13use crate::Result;
14use core::num::NonZeroUsize;
15use std::ops::Range;
16use strided_view::ElementOpApply;
17use threadteam::Exec;
18
19type SVec<T> = InlineVec<T>;
22
23const ONE: NonZeroUsize = NonZeroUsize::MIN;
24
25pub struct SendPtr<T>(pub *mut T);
42
43impl<T> Clone for SendPtr<T> {
44 fn clone(&self) -> Self {
45 *self
46 }
47}
48
49impl<T> Copy for SendPtr<T> {}
50
51unsafe impl<T> Send for SendPtr<T> {}
52unsafe impl<T> Sync for SendPtr<T> {}
53
54impl<T> SendPtr<T> {
55 pub fn as_ptr(self) -> *mut T {
56 self.0
57 }
58
59 pub fn as_const(self) -> *const T {
60 self.0 as *const T
61 }
62}
63
64impl<T> core::fmt::Debug for SendPtr<T> {
65 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
66 f.debug_tuple("SendPtr").field(&self.0).finish()
67 }
68}
69
70fn scheduler_blocks(dims: &[usize], blocks: &[usize]) -> SVec<usize> {
79 dims.iter()
80 .zip(blocks)
81 .map(|(&dim, &block)| {
82 if dim > 1 && dim <= block.min(1024) {
83 (dim / 2).max(1)
84 } else {
85 block
86 }
87 })
88 .collect()
89}
90
91fn fork2<R: Send>(
95 exec: Exec<'_>,
96 left: impl Fn(Exec<'_>) -> R + Sync,
97 right: impl Fn(Exec<'_>) -> R + Sync,
98) -> (R, R) {
99 struct Slot<T>(core::cell::UnsafeCell<Option<T>>);
102 unsafe impl<T: Send> Sync for Slot<T> {}
105 let slots = [Slot(Default::default()), Slot(Default::default())];
106 exec.fork(2, |i, child| {
107 let value = if i == 0 { left(child) } else { right(child) };
108 unsafe { *slots[i].0.get() = Some(value) };
110 });
111 let [left, right] = slots.map(|slot| {
112 slot.0
113 .into_inner()
114 .expect("every fork job stores its result")
115 });
116 (left, right)
117}
118
119pub fn parallel_map_reduce<R, Map, Reduce>(
136 range: Range<usize>,
137 exec: Exec<'_>,
138 map: &Map,
139 reduce: &Reduce,
140) -> R
141where
142 R: Send,
143 Map: Fn(Range<usize>) -> R + Sync,
144 Reduce: Fn(R, R) -> R + Sync,
145{
146 let len = range.end - range.start;
147 let budget = exec.budget().get();
148 if budget <= 1 || len <= 1 {
149 return map(range);
150 }
151
152 let left_threads = budget.div_ceil(2);
153 let left_len = len * left_threads / budget;
154 let middle = range.start + left_len.max(1).min(len - 1);
155 let left_range = range.start..middle;
156 let right_range = middle..range.end;
157
158 let (left, right) = fork2(
159 exec,
160 |child| parallel_map_reduce(left_range.clone(), child, map, reduce),
161 |child| parallel_map_reduce(right_range.clone(), child, map, reduce),
162 );
163 reduce(left, right)
164}
165
166pub(crate) fn parallel_for_each<F>(range: Range<usize>, exec: Exec<'_>, operation: &F)
169where
170 F: Fn(Range<usize>) + Sync,
171{
172 let start = range.start;
173 #[cfg(test)]
174 let chunks = core::sync::atomic::AtomicUsize::new(0);
175 exec.for_ranges(range.end - range.start, ONE, |chunk| {
176 #[cfg(test)]
177 chunks.fetch_add(1, core::sync::atomic::Ordering::Relaxed);
178 operation(start + chunk.start..start + chunk.end)
179 });
180 #[cfg(test)]
181 DISPATCHED_CHUNKS.with(|n| n.set(n.get() + chunks.into_inner()));
182}
183
184#[cfg(test)]
188thread_local! {
189 static DISPATCHED_CHUNKS: core::cell::Cell<usize> = const { core::cell::Cell::new(0) };
190}
191
192#[cfg(test)]
195pub(crate) fn take_dispatched_chunks() -> usize {
196 DISPATCHED_CHUNKS.with(|n| n.replace(0))
197}
198
199#[cfg(test)]
203thread_local! {
204 static CONJ_PERMUTED: core::cell::Cell<usize> = const { core::cell::Cell::new(0) };
205}
206
207#[cfg(test)]
210pub(crate) fn take_conj_permuted() -> usize {
211 CONJ_PERMUTED.with(|n| n.replace(0))
212}
213
214#[cfg(test)]
217pub(crate) type TiledLeaf = (isize, isize, Vec<usize>);
218
219#[cfg(test)]
222thread_local! {
223 static TILED_LEAVES: core::cell::RefCell<Vec<TiledLeaf>> = const { core::cell::RefCell::new(Vec::new()) };
224}
225
226#[cfg(test)]
229pub(crate) fn record_tiled_leaves(leaves: Vec<TiledLeaf>) {
230 DISPATCHED_CHUNKS.with(|n| n.set(n.get() + leaves.len()));
231 TILED_LEAVES.with(|all| all.borrow_mut().extend(leaves));
232}
233
234#[cfg(test)]
237pub(crate) fn take_tiled_leaves() -> Vec<TiledLeaf> {
238 TILED_LEAVES.with(|all| all.take())
239}
240
241#[cfg(test)]
245thread_local! {
246 static TILE_BOXES: core::cell::Cell<usize> = const { core::cell::Cell::new(0) };
247}
248
249#[cfg(test)]
251pub(crate) fn record_tile_box() {
252 TILE_BOXES.with(|n| n.set(n.get() + 1));
253}
254
255#[cfg(test)]
257pub(crate) fn record_tile_boxes(count: usize) {
258 TILE_BOXES.with(|n| n.set(n.get() + count));
259}
260
261#[cfg(test)]
265thread_local! {
266 static TILED_RANGES: core::cell::RefCell<Vec<usize>> = const { core::cell::RefCell::new(Vec::new()) };
267}
268
269#[cfg(test)]
272pub(crate) fn record_tiled_ranges(per_segment: Vec<usize>) {
273 TILED_RANGES.with(|all| *all.borrow_mut() = per_segment);
274}
275
276#[cfg(all(test, feature = "parallel"))]
280pub(crate) fn take_tiled_ranges() -> Vec<usize> {
281 TILED_RANGES.with(|all| all.take())
282}
283
284#[cfg(test)]
287pub(crate) fn take_tile_boxes() -> usize {
288 TILE_BOXES.with(|n| n.replace(0))
289}
290
291pub(crate) unsafe fn copy_contiguous<T: Copy + Send + Sync>(
301 src: *const T,
302 dst: *mut T,
303 len: usize,
304 exec: Exec<'_>,
305) {
306 let exec = for_len(exec, KernelClass::Copy, len);
307 if !exec.is_serial() {
308 let src = SendPtr(src as *mut T);
309 let dst = SendPtr(dst);
310 parallel_for_each(0..len, exec, &|range| {
311 unsafe {
315 core::ptr::copy_nonoverlapping(
316 src.as_const().add(range.start),
317 dst.as_ptr().add(range.start),
318 range.len(),
319 );
320 }
321 });
322 return;
323 }
324 unsafe { core::ptr::copy_nonoverlapping(src, dst, len) };
326}
327
328pub(crate) fn fill_contiguous<T: Copy + Send + Sync>(dst: &mut [T], value: T, exec: Exec<'_>) {
331 let len = dst.len();
332 let exec = for_len(exec, KernelClass::Copy, len);
333 if !exec.is_serial() {
334 let dst = SendPtr(dst.as_mut_ptr());
335 parallel_for_each(0..len, exec, &|range| {
336 let chunk = unsafe {
339 core::slice::from_raw_parts_mut(dst.as_ptr().add(range.start), range.len())
340 };
341 chunk.fill(value);
342 });
343 return;
344 }
345 dst.fill(value);
346}
347
348pub(crate) unsafe fn fill_contiguous_uninit<T: Copy + Send + Sync>(
360 dst: *mut T,
361 len: usize,
362 value: T,
363 exec: Exec<'_>,
364) {
365 let span =
368 unsafe { core::slice::from_raw_parts_mut(dst.cast::<core::mem::MaybeUninit<T>>(), len) };
369 fill_contiguous(span, core::mem::MaybeUninit::new(value), exec);
370}
371
372pub(crate) fn copy_permuted<T: Copy + Send + Sync + 'static>(
378 dest: &mut crate::StridedViewMut<T>,
379 src: &crate::StridedView<T>,
380 exec: Exec<'_>,
381) -> crate::Result<()> {
382 strided_perm::copy_into(dest, src, exec)
383}
384
385pub(crate) fn copy_permuted_uninit<T: Copy + Send + Sync + 'static>(
392 dest: &mut crate::StridedViewMut<core::mem::MaybeUninit<T>>,
393 src: &crate::StridedView<T>,
394 exec: Exec<'_>,
395) -> crate::Result<()> {
396 strided_perm::copy_into_uninit(dest, src, exec)
397}
398
399pub(crate) fn copy_conj_permuted<T: ElementOpApply + Send + Sync + 'static>(
409 dest: &mut crate::StridedViewMut<T>,
410 src: &crate::StridedView<T>,
411 exec: Exec<'_>,
412) -> crate::Result<()> {
413 #[cfg(test)]
414 CONJ_PERMUTED.with(|n| n.set(n.get() + 1));
415 strided_perm::copy_conj_into(dest, src, exec)
416}
417
418fn split_axis(dims: &[usize], blocks: &[usize], costs: &[isize]) -> Option<usize> {
426 let (i, _) = dims.iter().zip(costs.iter()).enumerate().fold(
427 (0, 0u128),
428 |(best_i, best_v), (idx, (&d, &c))| {
429 let score = d.saturating_sub(1) as u128 * c as u128;
430 if score >= best_v {
431 (idx, score)
432 } else {
433 (best_i, best_v)
434 }
435 },
436 );
437 (costs[i] != 0 && dims[i] > blocks[i].min(1024)).then_some(i)
438}
439
440fn halves(
443 dims: &[usize],
444 offsets: &[isize],
445 strides_list: &[&[isize]],
446 i: usize,
447) -> (SVec<usize>, SVec<usize>, SVec<isize>) {
448 let di = dims[i];
449 let ndi = di / 2;
450 let mut left_dims: SVec<usize> = dims.iter().copied().collect();
451 left_dims[i] = ndi;
452 let mut right_dims: SVec<usize> = dims.iter().copied().collect();
453 right_dims[i] = di - ndi;
454 let mut right_offsets: SVec<isize> = offsets.iter().copied().collect();
455 for (k, strides) in strides_list.iter().enumerate() {
456 right_offsets[k] += ndi as isize * strides[i];
457 }
458 (left_dims, right_dims, right_offsets)
459}
460
461#[allow(clippy::too_many_arguments)]
480pub(crate) fn mapreduce_threaded<S: AsRef<[isize]>, F>(
481 dims: &[usize],
482 blocks: &[usize],
483 strides_list: &[S],
484 offsets: &[isize],
485 costs: &[isize],
486 class: KernelClass,
487 exec: Exec<'_>,
488 f: &F,
489) -> Result<()>
490where
491 F: Fn(&[usize], &[usize], &[&[isize]], &[isize]) -> Result<()> + Sync,
492{
493 mapreduce_threaded_at_rate(
498 dims,
499 blocks,
500 strides_list,
501 offsets,
502 costs,
503 class.ns_per_element(),
504 exec,
505 f,
506 )
507}
508
509#[allow(clippy::too_many_arguments)]
514pub(crate) fn mapreduce_threaded_at_rate<S: AsRef<[isize]>, F>(
515 dims: &[usize],
516 blocks: &[usize],
517 strides_list: &[S],
518 offsets: &[isize],
519 costs: &[isize],
520 ns_per_element: f64,
521 exec: Exec<'_>,
522 f: &F,
523) -> Result<()>
524where
525 F: Fn(&[usize], &[usize], &[&[isize]], &[isize]) -> Result<()> + Sync,
526{
527 let refs: SVec<&[isize]> = strided_slices(strides_list);
528 mapreduce_threaded_dyn(dims, blocks, &refs, offsets, costs, ns_per_element, exec, f)
529}
530
531fn strided_slices<S: AsRef<[isize]>>(strides_list: &[S]) -> SVec<&[isize]> {
532 strides_list.iter().map(|s| s.as_ref()).collect()
533}
534
535type LeafFn<'a> = &'a (dyn Fn(&[usize], &[usize], &[&[isize]], &[isize]) -> Result<()> + Sync);
537
538#[allow(clippy::too_many_arguments)]
540#[inline(never)]
541fn mapreduce_threaded_dyn(
542 dims: &[usize],
543 blocks: &[usize],
544 strides_list: &[&[isize]],
545 offsets: &[isize],
546 costs: &[isize],
547 ns_per_element: f64,
548 exec: Exec<'_>,
549 f: LeafFn<'_>,
550) -> Result<()> {
551 let blocks = scheduler_blocks(dims, blocks);
556 ThreadedMapReduce {
557 blocks: &blocks,
558 strides_list,
559 costs,
560 ns_per_element,
561 operation: f,
562 }
563 .run(dims, offsets, exec)
564}
565
566struct ThreadedMapReduce<'a> {
567 blocks: &'a [usize],
568 strides_list: &'a [&'a [isize]],
569 costs: &'a [isize],
570 ns_per_element: f64,
571 operation: LeafFn<'a>,
572}
573
574impl ThreadedMapReduce<'_> {
575 fn run(&self, dims: &[usize], offsets: &[isize], exec: Exec<'_>) -> Result<()> {
576 let total = crate::kernel::total_len(dims)?;
577
578 if !is_parallel_at_rate(total, self.ns_per_element, &exec) {
580 return (self.operation)(dims, self.blocks, self.strides_list, offsets);
581 }
582 let Some(i) = split_axis(dims, self.blocks, self.costs) else {
583 return (self.operation)(dims, self.blocks, self.strides_list, offsets);
584 };
585
586 let (left_dims, right_dims, right_offsets) = halves(dims, offsets, self.strides_list, i);
587 let (r1, r2) = fork2(
588 exec,
589 |child| self.run(&left_dims, offsets, child),
590 |child| self.run(&right_dims, &right_offsets, child),
591 );
592 r1?;
593 r2?;
594 Ok(())
595 }
596}
597
598#[allow(clippy::too_many_arguments)]
608pub(crate) fn mapreduce_threaded_fold<S, F, C, R>(
609 dims: &[usize],
610 blocks: &[usize],
611 strides_list: &[S],
612 offsets: &[isize],
613 costs: &[isize],
614 class: KernelClass,
615 exec: Exec<'_>,
616 f: &F,
617 combine: &C,
618) -> Result<R>
619where
620 S: AsRef<[isize]>,
621 F: Fn(&[usize], &[usize], &[&[isize]], &[isize]) -> Result<R> + Sync,
622 C: Fn(R, R) -> R + Sync,
623 R: Send,
624{
625 let refs: SVec<&[isize]> = strided_slices(strides_list);
626 let blocks = scheduler_blocks(dims, blocks);
630 FoldMapReduce {
631 blocks: &blocks,
632 strides_list: &refs,
633 costs,
634 class,
635 f,
636 combine,
637 }
638 .run(dims, offsets, exec)
639}
640
641struct FoldMapReduce<'a, F, C> {
642 blocks: &'a [usize],
643 strides_list: &'a [&'a [isize]],
644 costs: &'a [isize],
645 class: KernelClass,
646 f: &'a F,
647 combine: &'a C,
648}
649
650impl<F, C> FoldMapReduce<'_, F, C> {
651 fn run<R: Send>(&self, dims: &[usize], offsets: &[isize], exec: Exec<'_>) -> Result<R>
652 where
653 F: Fn(&[usize], &[usize], &[&[isize]], &[isize]) -> Result<R> + Sync,
654 C: Fn(R, R) -> R + Sync,
655 {
656 let total = crate::kernel::total_len(dims)?;
657
658 if !is_parallel(self.class, total, &exec) {
660 return (self.f)(dims, self.blocks, self.strides_list, offsets);
661 }
662 let Some(i) = split_axis(dims, self.blocks, self.costs) else {
663 return (self.f)(dims, self.blocks, self.strides_list, offsets);
664 };
665
666 let (left_dims, right_dims, right_offsets) = halves(dims, offsets, self.strides_list, i);
668 let (r1, r2) = fork2(
669 exec,
670 |child| self.run(&left_dims, offsets, child),
671 |child| self.run(&right_dims, &right_offsets, child),
672 );
673 Ok((self.combine)(r1?, r2?))
674 }
675}
676
677pub(crate) fn for_each_inner_block_with_offsets<S: AsRef<[isize]>, F>(
683 dims: &[usize],
684 blocks: &[usize],
685 strides_list: &[S],
686 initial_offsets: &[isize],
687 f: F,
688) -> Result<()>
689where
690 F: FnMut(&[isize], usize, &[isize]) -> Result<()>,
691{
692 for_each_inner_block_preordered(dims, blocks, strides_list, initial_offsets, f)
693}
694
695#[cfg(test)]
697pub(crate) fn test_pool(threads: usize) -> threadteam::Pool {
698 threadteam::Pool::builder()
699 .threads(threads)
700 .dispatch_costs(test_dispatch_costs())
701 .build()
702 .unwrap()
703}
704
705#[cfg(test)]
709pub(crate) fn test_dispatch_costs() -> threadteam::DispatchCosts {
710 use threadteam::{DispatchKind, WidthCosts};
711 let cheap = WidthCosts::flat(core::time::Duration::from_nanos(100));
712 threadteam::DispatchCosts::for_class(threadteam::HostClass::Generic)
713 .with(DispatchKind::Team, cheap)
714 .with(DispatchKind::InPool, cheap)
715 .with(DispatchKind::Outside, cheap)
716}
717
718#[cfg(test)]
726pub(crate) fn run_serial_and_parallel<R: Send>(operation: impl Fn(Exec<'_>) -> R + Sync) -> (R, R) {
727 let serial = operation(Exec::serial());
728 let pool = test_pool(4);
729 let exec = Exec::new(&pool, 4).unwrap();
730 assert_eq!(
731 crate::cost::parallel_width(&exec, KernelClass::Map, 1 << 20).get(),
732 exec.budget().get()
733 );
734 let parallel = operation(exec);
735 (serial, parallel)
736}
737
738#[cfg(test)]
739#[path = "threading/tests/tests.rs"]
740mod tests;