Skip to main content

strided_basic/
threading.rs

1//! Parallel execution for strided operations.
2//!
3//! Faithfully ports Julia Strided.jl's `_mapreduce_threaded!` recursive
4//! dimension-splitting strategy. Every split goes through
5//! [`threadteam::Exec::fork`] or [`threadteam::Exec::for_ranges`]: the
6//! token carries the budget and the pool, so this module holds no placement
7//! state of its own.
8
9use 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
19/// Stack-allocated Vec for dims/offsets in recursive threading.
20/// 8 elements covers up to 8-dimensional arrays (after fusion, typically 2-4).
21type SVec<T> = InlineVec<T>;
22
23const ONE: NonZeroUsize = NonZeroUsize::MIN;
24
25/// A raw pointer wrapper that is `Send` + `Sync`.
26///
27/// # Safety
28/// The caller must guarantee that the pointed-to data is valid for the
29/// lifetime of any parallel operation and that no data races occur
30/// (e.g., different threads write to disjoint regions).
31/// Raw address transport for scoped kernel workers, without dereference or ownership.
32/// Storage liveness, aliasing and cross-thread access must be established at use.
33///
34/// # Examples
35/// ```
36/// use strided_basic::execution::SendPtr;
37/// let mut value = 1_i32;
38/// let address = &mut value as *mut i32;
39/// assert_eq!(SendPtr(address).as_ptr(), address);
40/// ```
41pub 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
70/// Block sizes handed to the parallel splitter.
71///
72/// [`split_axis`] declines to split a dimension that fits in one cache block
73/// (`dims[i] <= blocks[i].min(1024)`), so a region whose block covers a small
74/// whole tensor (for example `1024x64` with `block == dims`) never opens even
75/// at four threads. Halving such a block lets the splitter open; the leaf
76/// merely walks two tiles instead of one. Dimensions that already exceed the
77/// guard are left unchanged so other shapes keep their tiles.
78fn 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
91/// Runs `left` and `right` as the two halves of `exec` and returns both results.
92///
93/// Each half receives a child token carrying its share of the budget.
94fn fork2<R: Send>(
95    exec: Exec<'_>,
96    left: impl Fn(Exec<'_>) -> R + Sync,
97    right: impl Fn(Exec<'_>) -> R + Sync,
98) -> (R, R) {
99    // Mutex-free result slots: a `Mutex` allocates its lock on first use on
100    // some platforms, which made every call allocate.
101    struct Slot<T>(core::cell::UnsafeCell<Option<T>>);
102    // SAFETY: job `i` is the only writer of slot `i`, and the slots are read only
103    // after `fork` has returned, which waits for every job.
104    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        // SAFETY: see `Slot`; each index is written by exactly one job.
109        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
119/// Recursive halving map-reduce over `range` within the budget of `exec`.
120///
121/// `map` runs on the leaf ranges and `reduce` combines two neighbouring
122/// results left to right, so the combination order depends only on the budget.
123/// A serial token, a budget of one or a single-element range runs `map` on the
124/// whole range on the calling thread.
125///
126/// # Examples
127///
128/// ```
129/// use strided_basic::execution::parallel_map_reduce;
130/// use strided_basic::Exec;
131///
132/// let sum = parallel_map_reduce(0..100, Exec::serial(), &|r| r.sum::<usize>(), &|a, b| a + b);
133/// assert_eq!(sum, 4950);
134/// ```
135pub 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
166/// Runs `operation` over contiguous sub-ranges of `range`, one per slot of
167/// `exec` at most.
168pub(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// Ledger high-water marks depend on scheduling; the chunk count that
185// `for_ranges` hands out does not. Thread-local on the calling thread so that
186// concurrently running tests do not see each other's chunks.
187#[cfg(test)]
188thread_local! {
189    static DISPATCHED_CHUNKS: core::cell::Cell<usize> = const { core::cell::Cell::new(0) };
190}
191
192/// The chunks every `parallel_for_each` called on this thread has run since
193/// the last call, and resets the count.
194#[cfg(test)]
195pub(crate) fn take_dispatched_chunks() -> usize {
196    DISPATCHED_CHUNKS.with(|n| n.replace(0))
197}
198
199// The route `strided_basic::copy_conj_into` took is a decision, not an output
200// bit: two routes can write the same values. Counted per calling thread for
201// the in-crate route tests.
202#[cfg(test)]
203thread_local! {
204    static CONJ_PERMUTED: core::cell::Cell<usize> = const { core::cell::Cell::new(0) };
205}
206
207/// The conjugating permuting copies [`copy_conj_permuted`] has run on this
208/// thread since the last call, and resets the count.
209#[cfg(test)]
210pub(crate) fn take_conj_permuted() -> usize {
211    CONJ_PERMUTED.with(|n| n.replace(0))
212}
213
214/// One leaf box of a split tiled replay: the destination and source offsets
215/// of its origin, and its extents.
216#[cfg(test)]
217pub(crate) type TiledLeaf = (isize, isize, Vec<usize>);
218
219// Every leaf box of the tiled replays split on this thread, in completion
220// order.
221#[cfg(test)]
222thread_local! {
223    static TILED_LEAVES: core::cell::RefCell<Vec<TiledLeaf>> = const { core::cell::RefCell::new(Vec::new()) };
224}
225
226/// Records the leaves of one split tiled replay; they also count as
227/// dispatched chunks.
228#[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/// The leaves every split tiled replay called on this thread has recorded
235/// since the last call, and resets them.
236#[cfg(test)]
237pub(crate) fn take_tiled_leaves() -> Vec<TiledLeaf> {
238    TILED_LEAVES.with(|all| all.take())
239}
240
241// Cache-tile boxes the tiled box walks visited on this thread. The leaf
242// records above only exist when the splitter runs; this counts the walk itself,
243// so a test can see the tiled route on a serial token too.
244#[cfg(test)]
245thread_local! {
246    static TILE_BOXES: core::cell::Cell<usize> = const { core::cell::Cell::new(0) };
247}
248
249/// Records one visited cache-tile box.
250#[cfg(test)]
251pub(crate) fn record_tile_box() {
252    TILE_BOXES.with(|n| n.set(n.get() + 1));
253}
254
255/// Records `count` visited cache-tile boxes.
256#[cfg(test)]
257pub(crate) fn record_tile_boxes(count: usize) {
258    TILE_BOXES.with(|n| n.set(n.get() + count));
259}
260
261// Per segment, the dispatched ranges of the last whole-plan concatenate replay
262// on this thread that walked at least one of that segment's tiles, recorded on
263// the calling thread after the dispatch.
264#[cfg(test)]
265thread_local! {
266    static TILED_RANGES: core::cell::RefCell<Vec<usize>> = const { core::cell::RefCell::new(Vec::new()) };
267}
268
269/// Records, per segment, the dispatched ranges that walked its tiles,
270/// replacing what an earlier replay recorded.
271#[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/// The per-segment tiled ranges recorded on this thread since the last call
277/// (empty when no whole-plan replay ran), and clears them. Only the `parallel`
278/// tests read it.
279#[cfg(all(test, feature = "parallel"))]
280pub(crate) fn take_tiled_ranges() -> Vec<usize> {
281    TILED_RANGES.with(|all| all.take())
282}
283
284/// The cache-tile boxes visited on this thread since the last call, and resets
285/// the count.
286#[cfg(test)]
287pub(crate) fn take_tile_boxes() -> usize {
288    TILE_BOXES.with(|n| n.replace(0))
289}
290
291/// Copy `len` contiguous elements, chunked across the budget of `exec` when
292/// one section pays for a copy of that size (`KernelClass::Copy`) and as one
293/// direct `copy_nonoverlapping` otherwise.
294///
295/// # Safety
296///
297/// `src..src + len` must be readable and `dst..dst + len` writable for the
298/// whole call, the two ranges must not overlap, and no other thread may
299/// access the destination range concurrently.
300pub(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            // SAFETY: `range` lies inside `0..len`, and worker ranges are
312            // disjoint, so each worker copies an exclusive destination
313            // chunk from the caller-validated source range.
314            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    // SAFETY: the caller guarantees both ranges are valid and disjoint.
325    unsafe { core::ptr::copy_nonoverlapping(src, dst, len) };
326}
327
328/// Fill a contiguous slice, chunked across the budget of `exec` when a section
329/// pays for it (`KernelClass::Copy`) and as one serial `fill` otherwise.
330pub(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            // SAFETY: `range` lies inside the exclusively borrowed slice
337            // and worker ranges are disjoint.
338            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
348/// Fill `len` contiguous destination elements that may be uninitialized.
349///
350/// [`fill_contiguous`] forms a `&mut [T]`, which is undefined behaviour over
351/// uninitialized storage (for example a fresh `bool` buffer). This sibling
352/// views the same span as `[MaybeUninit<T>]`, which has no validity invariant,
353/// and reuses the existing chunking.
354///
355/// # Safety
356///
357/// `dst..dst + len` must be writable for the whole call and no other thread
358/// may access the destination range concurrently.
359pub(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    // SAFETY: `MaybeUninit<T>` has no validity invariant, so the span is a
366    // valid `[MaybeUninit<T>]`; `fill_contiguous` writes every element.
367    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
372/// Permuting copy into a destination of any layout, split across `exec`.
373///
374/// The permutation engine decides the width itself (copy class, one section),
375/// so this is the only route: a serial token (or a copy too small to repay a
376/// section) takes its calling-thread path.
377pub(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
385/// [`copy_permuted`] into an uninitialized destination.
386///
387/// The permutation engine is entered on the source element type, so its
388/// native `f32`/`f64` paths apply: a destination reinterpreted as
389/// `MaybeUninit<T>` falls to the generic element path, measured 2.5x slower
390/// on a 4096x4096 `f64` transpose.
391pub(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
399/// [`copy_permuted`] with the conjugation applied on store.
400///
401/// The permutation engine conjugates each element as it stores it (HPTT's
402/// `conjA`), so the copy takes no extra pass over memory. `strided_basic::
403/// copy_conj_into` reaches this route only where the engine is measured to beat
404/// the element map (the route predicate in `ops_view`). A complex element type
405/// never selects the engine's native `f32`/`f64` micro-kernels, so the store is
406/// its generic element store: the conjugation is the only difference from
407/// [`copy_permuted`].
408pub(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
418/// Dimension to halve: `_lastargmax((dims .- 1) .* costs)`, or `None` when
419/// that dimension is not worth splitting.
420///
421/// Ties break towards the last index, matching Julia's `_lastargmax`. A
422/// dimension is not split when its cost is zero or it fits in one block
423/// (`dims[i] <= min(blocks[i], 1024)`). Costs are nonnegative, as
424/// `compute_costs` produces them, and the score is exact in `u128`.
425fn 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
440/// The two halves of `dims` split at axis `i`: left dims, right dims and the
441/// right offsets advanced by the left extent.
442fn 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/// Recursive dimension-splitting parallel execution.
462///
463/// Faithfully ports Julia's `_mapreduce_threaded!` (mapreduce.jl L195-227).
464///
465/// Parameters:
466/// - `dims`: Ordered dimensions (after fuse/order/block)
467/// - `blocks`: Block sizes per dimension
468/// - `strides_list`: Per-array strides, ordered by plan
469/// - `offsets`: Per-array byte offsets into the data
470/// - `costs`: Per-dimension splitting costs
471/// - `exec`: Placement token; its budget is the number of slots the whole
472///   region may occupy, divided between the halves at every split
473/// - `f`: Leaf function — called when we've reached a single-slot region
474///
475/// The leaf function `f` receives `(dims, blocks, strides_list, offsets)` describing
476/// the sub-region to process.
477// The whole traversal: dims, blocks, per-operand strides and offsets, the costs,
478// the class, the token and the leaf closure.
479#[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    // The recursive splitter is compiled once; the leaf is `dyn`, called once
494    // per leaf region. Borrowed per-operand stride slices are built once here
495    // so the splitter and its leaves share them without owning a
496    // `Vec<Vec<isize>>` (#306 P1).
497    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/// [`mapreduce_threaded`] at an explicit serial rate per element instead of a
510/// class: the gates of the recursive splitter ask `exec.pays` at that rate, so a
511/// `CopyPlan` whose footprint is past its class's L2 splits at its own rate
512/// (strided-rs#364).
513#[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
535/// The leaf callback of a threaded region.
536type LeafFn<'a> = &'a (dyn Fn(&[usize], &[usize], &[&[isize]], &[isize]) -> Result<()> + Sync);
537
538// Borrowed-stride form of `mapreduce_threaded`, same arguments plus the leaf.
539#[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    // Normalize before the splitter: the guard in `split_axis` uses these tile
552    // sizes, so a block that covers its whole dimension would otherwise
553    // suppress the split. The shared layer applies this for every map, zip and
554    // fused caller.
555    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        // Base case: a single slot, or a fork of this region does not pay.
579        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/// Recursive dimension-splitting parallel fold.
599///
600/// Like [`mapreduce_threaded`], but the leaf returns a partial result and each
601/// split combines the two children with `combine`. A full reduction therefore
602/// never needs a worker-count-sized output-slot vector (#306 scope addition).
603/// `f` must reduce the whole sub-region it is handed, using the supplied
604/// `for_each_inner_block_with_offsets` traversal.
605// The whole traversal: dims, blocks, per-operand strides, offsets and costs, the
606// class, the token and the two closures.
607#[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    // Normalize whole-dimension blocks before splitting, matching the
627    // `mapreduce_threaded` path (#313): a block that covers its dimension would
628    // otherwise suppress the split for a small whole tensor.
629    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        // Base case: a single slot, or a fork of this region does not pay.
659        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        // Split dimension i in half and combine the two partial results.
667        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
677/// Execute the kernel on a sub-region defined by initial offsets.
678///
679/// Delegates to `for_each_inner_block_preordered` which directly calls
680/// kernel functions with the initial offsets, avoiding redundant re-ordering
681/// and per-callback `Vec` allocation.
682pub(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/// A pool of `threads` workers for unit tests.
696#[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/// Dispatch costs of the unit-test pools: 100 nanoseconds per section whatever the
706/// token, so that regions of a few thousand elements open the parallel branches
707/// the tests compare against the serial ones.
708#[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/// Run `operation` once with a serial token and once with a four-slot token of
719/// a four-worker pool, and return both results.
720///
721/// The parallel run asserts that the gate actually opens for a region of a
722/// million elements, so equivalence tests with such sizes exercise the parallel
723/// branches. Without the `parallel` feature the pool has
724/// width one and both runs are serial.
725#[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;