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.
365pub(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    // The recursive splitter is compiled once; the leaf is `dyn`, called once
379    // per leaf region. Borrowed per-operand stride slices are built once here
380    // so the splitter and its leaves share them without owning a
381    // `Vec<Vec<isize>>` (#306 P1).
382    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
390/// The leaf callback of a threaded region.
391type 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    // Normalize before the splitter: the guard in `split_axis` uses these tile
405    // sizes, so a block that covers its whole dimension would otherwise
406    // suppress the split. The shared layer applies this for every map, zip and
407    // fused caller.
408    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        // Base case: a single slot, or a fork of this region does not pay.
432        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/// Recursive dimension-splitting parallel fold.
452///
453/// Like [`mapreduce_threaded`], but the leaf returns a partial result and each
454/// split combines the two children with `combine`. A full reduction therefore
455/// never needs a worker-count-sized output-slot vector (#306 scope addition).
456/// `f` must reduce the whole sub-region it is handed, using the supplied
457/// `for_each_inner_block_with_offsets` traversal.
458#[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    // Normalize whole-dimension blocks before splitting, matching the
478    // `mapreduce_threaded` path (#313): a block that covers its dimension would
479    // otherwise suppress the split for a small whole tensor.
480    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        // Base case: a single slot, or a fork of this region does not pay.
510        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        // Split dimension i in half and combine the two partial results.
518        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
528/// Execute the kernel on a sub-region defined by initial offsets.
529///
530/// Delegates to `for_each_inner_block_preordered` which directly calls
531/// kernel functions with the initial offsets, avoiding redundant re-ordering
532/// and per-callback `Vec` allocation.
533pub(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/// A pool of `threads` workers for unit tests.
547#[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/// Dispatch costs of the unit-test pools: 100 nanoseconds per section whatever the
557/// token, so that regions of a few thousand elements open the parallel branches
558/// the tests compare against the serial ones.
559#[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/// Run `operation` once with a serial token and once with a four-slot token of
570/// a four-worker pool, and return both results.
571///
572/// The parallel run asserts that the gate actually opens for a region of a
573/// million elements, so equivalence tests with such sizes exercise the parallel
574/// branches. Without the `parallel` feature the pool has
575/// width one and both runs are serial.
576#[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;