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};
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
18/// Stack-allocated Vec for dims/offsets in recursive threading.
19/// 8 elements covers up to 8-dimensional arrays (after fusion, typically 2-4).
20type SVec<T> = InlineVec<T>;
21
22const ONE: NonZeroUsize = NonZeroUsize::MIN;
23
24/// A raw pointer wrapper that is `Send` + `Sync`.
25///
26/// # Safety
27/// The caller must guarantee that the pointed-to data is valid for the
28/// lifetime of any parallel operation and that no data races occur
29/// (e.g., different threads write to disjoint regions).
30/// Raw address transport for scoped kernel workers, without dereference or ownership.
31/// Storage liveness, aliasing and cross-thread access must be established at use.
32///
33/// # Examples
34/// ```
35/// use strided_basic::execution::SendPtr;
36/// let mut value = 1_i32;
37/// let address = &mut value as *mut i32;
38/// assert_eq!(SendPtr(address).as_ptr(), address);
39/// ```
40pub 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
69/// Block sizes handed to the parallel splitter.
70///
71/// [`split_axis`] declines to split a dimension that fits in one cache block
72/// (`dims[i] <= blocks[i].min(1024)`), so a region whose block covers a small
73/// whole tensor (for example `1024x64` with `block == dims`) never opens even
74/// at four threads. Halving such a block lets the splitter open; the leaf
75/// merely walks two tiles instead of one. Dimensions that already exceed the
76/// guard are left unchanged so other shapes keep their tiles.
77fn 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
90/// Runs `left` and `right` as the two halves of `exec` and returns both results.
91///
92/// Each half receives a child token carrying its share of the budget.
93fn fork2<R: Send>(
94    exec: Exec<'_>,
95    left: impl Fn(Exec<'_>) -> R + Sync,
96    right: impl Fn(Exec<'_>) -> R + Sync,
97) -> (R, R) {
98    // Mutex-free result slots: a `Mutex` allocates its lock on first use on
99    // some platforms, which made every call allocate.
100    struct Slot<T>(core::cell::UnsafeCell<Option<T>>);
101    // SAFETY: job `i` is the only writer of slot `i`, and the slots are read only
102    // after `fork` has returned, which waits for every job.
103    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        // SAFETY: see `Slot`; each index is written by exactly one job.
108        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
118/// Recursive halving map-reduce over `range` within the budget of `exec`.
119///
120/// `map` runs on the leaf ranges and `reduce` combines two neighbouring
121/// results left to right, so the combination order depends only on the budget.
122/// A serial token, a budget of one or a single-element range runs `map` on the
123/// whole range on the calling thread.
124///
125/// # Examples
126///
127/// ```
128/// use strided_basic::execution::parallel_map_reduce;
129/// use strided_basic::Exec;
130///
131/// let sum = parallel_map_reduce(0..100, Exec::serial(), &|r| r.sum::<usize>(), &|a, b| a + b);
132/// assert_eq!(sum, 4950);
133/// ```
134pub 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
165/// Runs `operation` over contiguous sub-ranges of `range`, one per slot of
166/// `exec` at most.
167pub(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// Ledger high-water marks depend on scheduling; the chunk count that
184// `for_ranges` hands out does not. Thread-local on the calling thread so that
185// concurrently running tests do not see each other's chunks.
186#[cfg(test)]
187thread_local! {
188    static DISPATCHED_CHUNKS: core::cell::Cell<usize> = const { core::cell::Cell::new(0) };
189}
190
191/// The chunks every `parallel_for_each` called on this thread has run since
192/// the last call, and resets the count.
193#[cfg(test)]
194pub(crate) fn take_dispatched_chunks() -> usize {
195    DISPATCHED_CHUNKS.with(|n| n.replace(0))
196}
197
198/// Copy `len` contiguous elements, chunked across the budget of `exec` when
199/// one section pays for a copy of that size (`KernelClass::Copy`) and as one
200/// direct `copy_nonoverlapping` otherwise.
201///
202/// # Safety
203///
204/// `src..src + len` must be readable and `dst..dst + len` writable for the
205/// whole call, the two ranges must not overlap, and no other thread may
206/// access the destination range concurrently.
207pub(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            // SAFETY: `range` lies inside `0..len`, and worker ranges are
219            // disjoint, so each worker copies an exclusive destination
220            // chunk from the caller-validated source range.
221            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    // SAFETY: the caller guarantees both ranges are valid and disjoint.
232    unsafe { core::ptr::copy_nonoverlapping(src, dst, len) };
233}
234
235/// Fill a contiguous slice, chunked across the budget of `exec` when a section
236/// pays for it (`KernelClass::Copy`) and as one serial `fill` otherwise.
237pub(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            // SAFETY: `range` lies inside the exclusively borrowed slice
244            // and worker ranges are disjoint.
245            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
255/// Fill `len` contiguous destination elements that may be uninitialized.
256///
257/// [`fill_contiguous`] forms a `&mut [T]`, which is undefined behaviour over
258/// uninitialized storage (for example a fresh `bool` buffer). This sibling
259/// views the same span as `[MaybeUninit<T>]`, which has no validity invariant,
260/// and reuses the existing chunking.
261///
262/// # Safety
263///
264/// `dst..dst + len` must be writable for the whole call and no other thread
265/// may access the destination range concurrently.
266pub(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    // SAFETY: `MaybeUninit<T>` has no validity invariant, so the span is a
273    // valid `[MaybeUninit<T>]`; `fill_contiguous` writes every element.
274    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
279/// Permuting copy into a destination of any layout, split across `exec`.
280///
281/// The permutation engine decides the width itself (copy class, one section),
282/// so this is the only route: a serial token (or a copy too small to repay a
283/// section) takes its calling-thread path.
284pub(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
292/// [`copy_permuted`] into an uninitialized destination.
293///
294/// The permutation engine is entered on the source element type, so its
295/// native `f32`/`f64` paths apply: a destination reinterpreted as
296/// `MaybeUninit<T>` falls to the generic element path, measured 2.5x slower
297/// on a 4096x4096 `f64` transpose.
298pub(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
306/// Dimension to halve: `_lastargmax((dims .- 1) .* costs)`, or `None` when
307/// that dimension is not worth splitting.
308///
309/// Ties break towards the last index, matching Julia's `_lastargmax`. A
310/// dimension is not split when its cost is zero or it fits in one block
311/// (`dims[i] <= min(blocks[i], 1024)`). Costs are nonnegative, as
312/// `compute_costs` produces them, and the score is exact in `u128`.
313fn 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
328/// The two halves of `dims` split at axis `i`: left dims, right dims and the
329/// right offsets advanced by the left extent.
330fn 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/// Recursive dimension-splitting parallel execution.
350///
351/// Faithfully ports Julia's `_mapreduce_threaded!` (mapreduce.jl L195-227).
352///
353/// Parameters:
354/// - `dims`: Ordered dimensions (after fuse/order/block)
355/// - `blocks`: Block sizes per dimension
356/// - `strides_list`: Per-array strides, ordered by plan
357/// - `offsets`: Per-array byte offsets into the data
358/// - `costs`: Per-dimension splitting costs
359/// - `exec`: Placement token; its budget is the number of slots the whole
360///   region may occupy, divided between the halves at every split
361/// - `f`: Leaf function — called when we've reached a single-slot region
362///
363/// The leaf function `f` receives `(dims, blocks, strides_list, offsets)` describing
364/// the sub-region to process.
365// The whole traversal: dims, blocks, per-operand strides and offsets, the costs,
366// the class, the token and the leaf closure.
367#[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    // The recursive splitter is compiled once; the leaf is `dyn`, called once
382    // per leaf region. Borrowed per-operand stride slices are built once here
383    // so the splitter and its leaves share them without owning a
384    // `Vec<Vec<isize>>` (#306 P1).
385    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
393/// The leaf callback of a threaded region.
394type LeafFn<'a> = &'a (dyn Fn(&[usize], &[usize], &[&[isize]], &[isize]) -> Result<()> + Sync);
395
396// Borrowed-stride form of `mapreduce_threaded`, same arguments plus the leaf.
397#[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    // Normalize before the splitter: the guard in `split_axis` uses these tile
410    // sizes, so a block that covers its whole dimension would otherwise
411    // suppress the split. The shared layer applies this for every map, zip and
412    // fused caller.
413    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        // Base case: a single slot, or a fork of this region does not pay.
437        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/// Recursive dimension-splitting parallel fold.
457///
458/// Like [`mapreduce_threaded`], but the leaf returns a partial result and each
459/// split combines the two children with `combine`. A full reduction therefore
460/// never needs a worker-count-sized output-slot vector (#306 scope addition).
461/// `f` must reduce the whole sub-region it is handed, using the supplied
462/// `for_each_inner_block_with_offsets` traversal.
463// The whole traversal: dims, blocks, per-operand strides, offsets and costs, the
464// class, the token and the two closures.
465#[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    // Normalize whole-dimension blocks before splitting, matching the
485    // `mapreduce_threaded` path (#313): a block that covers its dimension would
486    // otherwise suppress the split for a small whole tensor.
487    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        // Base case: a single slot, or a fork of this region does not pay.
517        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        // Split dimension i in half and combine the two partial results.
525        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
535/// Execute the kernel on a sub-region defined by initial offsets.
536///
537/// Delegates to `for_each_inner_block_preordered` which directly calls
538/// kernel functions with the initial offsets, avoiding redundant re-ordering
539/// and per-callback `Vec` allocation.
540pub(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/// A pool of `threads` workers for unit tests.
554#[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/// Dispatch costs of the unit-test pools: 100 nanoseconds per section whatever the
564/// token, so that regions of a few thousand elements open the parallel branches
565/// the tests compare against the serial ones.
566#[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/// Run `operation` once with a serial token and once with a four-slot token of
577/// a four-worker pool, and return both results.
578///
579/// The parallel run asserts that the gate actually opens for a region of a
580/// million elements, so equivalence tests with such sizes exercise the parallel
581/// branches. Without the `parallel` feature the pool has
582/// width one and both runs are serial.
583#[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;