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
349pub(crate) fn mapreduce_threaded<S: AsRef<[isize]>, F>(
366 dims: &[usize],
367 blocks: &[usize],
368 strides_list: &[S],
369 offsets: &[isize],
370 costs: &[isize],
371 class: KernelClass,
372 exec: Exec<'_>,
373 f: &F,
374) -> Result<()>
375where
376 F: Fn(&[usize], &[usize], &[&[isize]], &[isize]) -> Result<()> + Sync,
377{
378 let refs: SVec<&[isize]> = strided_slices(strides_list);
383 mapreduce_threaded_dyn(dims, blocks, &refs, offsets, costs, class, exec, f)
384}
385
386fn strided_slices<S: AsRef<[isize]>>(strides_list: &[S]) -> SVec<&[isize]> {
387 strides_list.iter().map(|s| s.as_ref()).collect()
388}
389
390type LeafFn<'a> = &'a (dyn Fn(&[usize], &[usize], &[&[isize]], &[isize]) -> Result<()> + Sync);
392
393#[inline(never)]
394fn mapreduce_threaded_dyn(
395 dims: &[usize],
396 blocks: &[usize],
397 strides_list: &[&[isize]],
398 offsets: &[isize],
399 costs: &[isize],
400 class: KernelClass,
401 exec: Exec<'_>,
402 f: LeafFn<'_>,
403) -> Result<()> {
404 let blocks = scheduler_blocks(dims, blocks);
409 ThreadedMapReduce {
410 blocks: &blocks,
411 strides_list,
412 costs,
413 class,
414 operation: f,
415 }
416 .run(dims, offsets, exec)
417}
418
419struct ThreadedMapReduce<'a> {
420 blocks: &'a [usize],
421 strides_list: &'a [&'a [isize]],
422 costs: &'a [isize],
423 class: KernelClass,
424 operation: LeafFn<'a>,
425}
426
427impl ThreadedMapReduce<'_> {
428 fn run(&self, dims: &[usize], offsets: &[isize], exec: Exec<'_>) -> Result<()> {
429 let total = crate::kernel::total_len(dims)?;
430
431 if !is_parallel(self.class, total, &exec) {
433 return (self.operation)(dims, self.blocks, self.strides_list, offsets);
434 }
435 let Some(i) = split_axis(dims, self.blocks, self.costs) else {
436 return (self.operation)(dims, self.blocks, self.strides_list, offsets);
437 };
438
439 let (left_dims, right_dims, right_offsets) = halves(dims, offsets, self.strides_list, i);
440 let (r1, r2) = fork2(
441 exec,
442 |child| self.run(&left_dims, offsets, child),
443 |child| self.run(&right_dims, &right_offsets, child),
444 );
445 r1?;
446 r2?;
447 Ok(())
448 }
449}
450
451#[allow(clippy::too_many_arguments)]
459pub(crate) fn mapreduce_threaded_fold<S, F, C, R>(
460 dims: &[usize],
461 blocks: &[usize],
462 strides_list: &[S],
463 offsets: &[isize],
464 costs: &[isize],
465 class: KernelClass,
466 exec: Exec<'_>,
467 f: &F,
468 combine: &C,
469) -> Result<R>
470where
471 S: AsRef<[isize]>,
472 F: Fn(&[usize], &[usize], &[&[isize]], &[isize]) -> Result<R> + Sync,
473 C: Fn(R, R) -> R + Sync,
474 R: Send,
475{
476 let refs: SVec<&[isize]> = strided_slices(strides_list);
477 let blocks = scheduler_blocks(dims, blocks);
481 FoldMapReduce {
482 blocks: &blocks,
483 strides_list: &refs,
484 costs,
485 class,
486 f,
487 combine,
488 }
489 .run(dims, offsets, exec)
490}
491
492struct FoldMapReduce<'a, F, C> {
493 blocks: &'a [usize],
494 strides_list: &'a [&'a [isize]],
495 costs: &'a [isize],
496 class: KernelClass,
497 f: &'a F,
498 combine: &'a C,
499}
500
501impl<F, C> FoldMapReduce<'_, F, C> {
502 fn run<R: Send>(&self, dims: &[usize], offsets: &[isize], exec: Exec<'_>) -> Result<R>
503 where
504 F: Fn(&[usize], &[usize], &[&[isize]], &[isize]) -> Result<R> + Sync,
505 C: Fn(R, R) -> R + Sync,
506 {
507 let total = crate::kernel::total_len(dims)?;
508
509 if !is_parallel(self.class, total, &exec) {
511 return (self.f)(dims, self.blocks, self.strides_list, offsets);
512 }
513 let Some(i) = split_axis(dims, self.blocks, self.costs) else {
514 return (self.f)(dims, self.blocks, self.strides_list, offsets);
515 };
516
517 let (left_dims, right_dims, right_offsets) = halves(dims, offsets, self.strides_list, i);
519 let (r1, r2) = fork2(
520 exec,
521 |child| self.run(&left_dims, offsets, child),
522 |child| self.run(&right_dims, &right_offsets, child),
523 );
524 Ok((self.combine)(r1?, r2?))
525 }
526}
527
528pub(crate) fn for_each_inner_block_with_offsets<S: AsRef<[isize]>, F>(
534 dims: &[usize],
535 blocks: &[usize],
536 strides_list: &[S],
537 initial_offsets: &[isize],
538 f: F,
539) -> Result<()>
540where
541 F: FnMut(&[isize], usize, &[isize]) -> Result<()>,
542{
543 for_each_inner_block_preordered(dims, blocks, strides_list, initial_offsets, f)
544}
545
546#[cfg(test)]
548pub(crate) fn test_pool(threads: usize) -> threadteam::Pool {
549 threadteam::Pool::builder()
550 .threads(threads)
551 .dispatch_costs(test_dispatch_costs())
552 .build()
553 .unwrap()
554}
555
556#[cfg(test)]
560pub(crate) fn test_dispatch_costs() -> threadteam::DispatchCosts {
561 use threadteam::{DispatchKind, WidthCosts};
562 let cheap = WidthCosts::flat(core::time::Duration::from_nanos(100));
563 threadteam::DispatchCosts::for_class(threadteam::HostClass::Generic)
564 .with(DispatchKind::Team, cheap)
565 .with(DispatchKind::InPool, cheap)
566 .with(DispatchKind::Outside, cheap)
567}
568
569#[cfg(test)]
577pub(crate) fn run_serial_and_parallel<R: Send>(operation: impl Fn(Exec<'_>) -> R + Sync) -> (R, R) {
578 let serial = operation(Exec::serial());
579 let pool = test_pool(4);
580 let exec = Exec::new(&pool, 4).unwrap();
581 assert_eq!(
582 crate::cost::parallel_width(&exec, KernelClass::Map, 1 << 20).get(),
583 exec.budget().get()
584 );
585 let parallel = operation(exec);
586 (serial, parallel)
587}
588
589#[cfg(test)]
590#[path = "threading/tests/tests.rs"]
591mod tests;