Skip to main content

strided_basic/
run_sum.rs

1//! Sorted-run reduction: destination rows that are already grouped by a
2//! destination index ([#479]).
3//!
4//! `RunSumPlan` computes
5//!
6//! ```text
7//! dest[r, ..] (=|+=) Σ_{j in ptr[r]..ptr[r+1]} src[perm[j], ..]
8//! ```
9//!
10//! for a source `[E, ..]` and a destination `[R, ..]` over the CSR runs
11//! `ptr[0..=R]` and the row permutation `perm`. It is the edge → node
12//! accumulation of a sparse message-passing loop (`out[r] += message[e]` for
13//! every edge `e` received by `r`), where `ScatterPlan`'s additive scatter
14//! would be serial and order-sensitive.
15//!
16//! # Topology and replay
17//!
18//! [`RunIndex`] owns the grouped-row topology: a stable counting sort of an
19//! unsorted destination list, or offsets a caller already has. Sorting is
20//! **topology time**: it allocates, and `RunSumPlan::compile` allocates its
21//! fused traversal, while `execute_into` / `execute_acc` allocate nothing as
22//! long as the payload fuses to at most eight axes, which is where the
23//! rank-specialized kernels take over. A payload of more than eight fused axes
24//! walks through `kernel_nd_inner_iterative`, whose cursor is a `Vec` by
25//! contract. One `RunIndex` can be replayed by several plans until the topology
26//! changes.
27//!
28//! # Determinism
29//!
30//! A run is summed by exactly one worker, in increasing `j`, and destination
31//! rows are disjoint between runs (`compile` requires an injective destination
32//! layout). The partition therefore cannot change a result: every `Exec` budget
33//! produces identical bits. No atomics, no partial sums.
34//!
35//! # Contract
36//!
37//! - `execute_into` writes the sum; a run with no rows writes zeros.
38//! - `execute_acc` adds the sum to the existing value; a run with no rows adds
39//!   nothing.
40//! - Both seed the accumulation with `T::zero()` (or the existing value) and add
41//!   the rows in order, so `execute_into` and `execute_acc` agree bit for bit on
42//!   a destination seeded with `T::zero()`.
43//! - `dest` and `src` must not overlap; this is the caller's obligation, as for
44//!   every plan taking `RawStridedRef` / `RawStridedMut`.
45//!
46//! # Not in this plan
47//!
48//! This module is the typed side only: the dtype-erased replay does not exist, and
49//! no consumer of [#479] needs one. `strided-segpoly` reads the same `RunIndex`
50//! for its scattered outputs and runs its own payload walk, so a third copy of
51//! this plan that erases `T` would add a code path nothing calls.
52//!
53//! The payload walk is not blocked or SIMD-dispatched, and a single long run is
54//! one worker's work.
55//!
56//! [#479]: https://github.com/tensor4all/strided-rs/issues/479
57
58use core::ops::{Add, Range};
59
60use num_traits::Zero;
61
62use crate::cost::{tree_width, KernelClass};
63use crate::fuse::{compress_dims, fuse_dims};
64use crate::gather_plan::GatherIndex;
65use crate::inline::{InlineVec, OperandVec};
66use crate::threading::{for_each_inner_block_with_offsets, SendPtr};
67use crate::{Exec, RawStridedMut, RawStridedRef, Result, StridedError};
68
69/// Rows grouped by destination: CSR offsets plus a stable row permutation.
70///
71/// `ptr` holds `runs + 1` offsets and `perm` is either the identity (rows are
72/// already grouped, so the plan walks `0..rows`) or as long as the row count.
73#[derive(Debug, Clone)]
74pub struct RunIndex {
75    ptr: Vec<usize>,
76    perm: Option<Vec<usize>>,
77}
78
79impl RunIndex {
80    /// Group an unsorted destination list with a stable counting sort.
81    ///
82    /// Row `e` joins run `dest[e]`, and rows keep their original order inside a
83    /// run. A destination that is already non-decreasing keeps the identity
84    /// permutation and only pays for the offsets. Allocates; call it when the
85    /// topology changes, never per execution.
86    ///
87    /// # Errors
88    ///
89    /// Returns [`StridedError::IndexOutOfRange`] when an index is negative, is
90    /// not below `num_runs`, or is present while `num_runs` is zero, and
91    /// [`StridedError::OffsetOverflow`] when the row count does not fit `usize`.
92    pub fn from_dest<I: GatherIndex>(dest: &[I], num_runs: usize) -> Result<Self> {
93        // The counting sort allocates one `usize` per run, so a run count whose
94        // byte size is not representable is `OffsetOverflow` here rather than a
95        // capacity panic in the allocation below.
96        if num_runs > isize::MAX as usize / core::mem::size_of::<usize>() {
97            return Err(StridedError::OffsetOverflow);
98        }
99        let counts = counts_of(dest, num_runs)?;
100
101        // Prefix sums become the offsets; the counts are reused as the
102        // placement cursor when a permutation is needed.
103        let mut ptr: Vec<usize> = Vec::with_capacity(num_runs + 1);
104        let mut grouped = 0usize;
105        ptr.push(0);
106        for &count in counts.iter() {
107            grouped = grouped
108                .checked_add(count)
109                .ok_or(StridedError::OffsetOverflow)?;
110            ptr.push(grouped);
111        }
112        if is_grouped(dest) {
113            return Ok(Self { ptr, perm: None });
114        }
115
116        let mut cursor = counts;
117        let mut start = 0usize;
118        for slot in cursor.iter_mut() {
119            let count = *slot;
120            *slot = start;
121            start += count;
122        }
123        let mut perm = vec![0usize; dest.len()];
124        for (row, &index) in dest.iter().enumerate() {
125            let run = run_of(index, num_runs)?;
126            let slot = cursor[run];
127            perm[slot] = row;
128            cursor[run] = slot + 1;
129        }
130        Ok(Self {
131            ptr,
132            perm: Some(perm),
133        })
134    }
135
136    /// Take rows a caller has already grouped.
137    ///
138    /// `ptr` is the CSR offset list: `runs + 1` non-decreasing entries starting
139    /// at zero, so `ptr[r]..ptr[r + 1]` is the row range of run `r` and
140    /// `ptr[last]` is the row count. Holds the `Vec` as given and allocates
141    /// nothing.
142    ///
143    /// # Errors
144    ///
145    /// Returns [`StridedError::InvalidRunIndex`] when `ptr` is empty, does not
146    /// start at zero, or steps downwards.
147    pub fn from_ptr(ptr: Vec<usize>) -> Result<Self> {
148        if ptr.first() != Some(&0) || ptr.windows(2).any(|pair| pair[0] > pair[1]) {
149            return Err(StridedError::InvalidRunIndex);
150        }
151        Ok(Self { ptr, perm: None })
152    }
153
154    /// The CSR offsets: `runs + 1` non-decreasing entries starting at zero.
155    pub fn ptr(&self) -> &[usize] {
156        &self.ptr
157    }
158
159    /// The row permutation, or `None` when the rows are already in run order.
160    pub fn perm(&self) -> Option<&[usize]> {
161        self.perm.as_deref()
162    }
163
164    fn rows(&self) -> usize {
165        self.ptr[self.ptr.len() - 1]
166    }
167
168    fn runs(&self) -> usize {
169        self.ptr.len() - 1
170    }
171}
172
173/// Count the rows of each run and reject an index outside `0..num_runs`.
174fn counts_of<I: GatherIndex>(dest: &[I], num_runs: usize) -> Result<Vec<usize>> {
175    let mut counts = vec![0usize; num_runs];
176    for &index in dest {
177        let run = run_of(index, num_runs)?;
178        counts[run] += 1;
179    }
180    Ok(counts)
181}
182
183fn run_of<I: GatherIndex>(index: I, num_runs: usize) -> Result<usize> {
184    let value = index.to_i64();
185    if value < 0 || value as u64 >= num_runs as u64 {
186        return Err(StridedError::IndexOutOfRange {
187            index: value,
188            runs: num_runs,
189        });
190    }
191    Ok(value as usize)
192}
193
194fn is_grouped<I: GatherIndex>(dest: &[I]) -> bool {
195    dest.windows(2)
196        .all(|pair| pair[0].to_i64() <= pair[1].to_i64())
197}
198
199/// `dest[r, ..] (=|+=) Σ_{j in ptr[r]..ptr[r+1]} src[perm[j], ..]`.
200///
201/// Compiled once for a source layout, a destination layout and a
202/// [`RunIndex`]'s row count; replayed with [`execute_into`](Self::execute_into)
203/// or [`execute_acc`](Self::execute_acc).
204#[derive(Debug)]
205pub struct RunSumPlan {
206    src_dims: InlineVec<usize>,
207    src_strides: InlineVec<isize>,
208    dest_dims: InlineVec<usize>,
209    dest_strides: InlineVec<isize>,
210    /// Payload traversal, fused in declaration order: `[dest, src]` strides.
211    payload_dims: InlineVec<usize>,
212    payload_strides: OperandVec<InlineVec<isize>>,
213    src_row_stride: isize,
214    dest_row_stride: isize,
215    rows: usize,
216    runs: usize,
217    payload_elems: usize,
218}
219
220impl RunSumPlan {
221    /// Compile a replay for one source layout, one destination layout and the
222    /// run count the index describes.
223    ///
224    /// The layout facts a plan can prove without the buffers are proved here;
225    /// buffer bounds, alignment and the absence of `dest`/`src` overlap are the
226    /// caller's `RawStridedRef` / `RawStridedMut` obligations. Allocates the
227    /// fused payload traversal; never called from the execute path.
228    ///
229    /// # Errors
230    ///
231    /// Returns [`StridedError::StrideLengthMismatch`] when a stride list does not
232    /// match its dimension list, [`StridedError::RankMismatch`] when the ranks
233    /// differ or there is no row axis, [`StridedError::ShapeMismatch`] when the
234    /// trailing extents differ or the row counts disagree with `runs`,
235    /// [`StridedError::OffsetOverflow`] when an element count does not fit
236    /// `usize`, and [`StridedError::NonInjectiveOutputLayout`] when the
237    /// destination layout cannot be proven injective.
238    pub fn compile(
239        src_dims: &[usize],
240        src_strides: &[isize],
241        dest_dims: &[usize],
242        dest_strides: &[isize],
243        runs: &RunIndex,
244    ) -> Result<Self> {
245        if src_dims.len() != src_strides.len() || dest_dims.len() != dest_strides.len() {
246            return Err(StridedError::StrideLengthMismatch);
247        }
248        if src_dims.len() != dest_dims.len() {
249            return Err(StridedError::RankMismatch(src_dims.len(), dest_dims.len()));
250        }
251        // The row axis is the one this plan exists for.
252        if src_dims.is_empty() {
253            return Err(StridedError::RankMismatch(0, 1));
254        }
255        if src_dims[0] != runs.rows() {
256            return Err(StridedError::ShapeMismatch(
257                vec![src_dims[0]],
258                vec![runs.rows()],
259            ));
260        }
261        if dest_dims[0] != runs.runs() {
262            return Err(StridedError::ShapeMismatch(
263                vec![dest_dims[0]],
264                vec![runs.runs()],
265            ));
266        }
267        if src_dims[1..] != dest_dims[1..] {
268            return Err(StridedError::ShapeMismatch(
269                src_dims.to_vec(),
270                dest_dims.to_vec(),
271            ));
272        }
273        crate::kernel::total_len(src_dims)?;
274        crate::kernel::total_len(dest_dims)?;
275        if !crate::layout_check::is_injective_layout(dest_dims, dest_strides) {
276            return Err(StridedError::NonInjectiveOutputLayout);
277        }
278
279        let payload_dims = &src_dims[1..];
280        let payload_strides = [&dest_strides[1..], &src_strides[1..]];
281        let fused = fuse_dims(payload_dims, &payload_strides);
282        let (fused_dims, fused_strides) = compress_dims(&fused, &payload_strides);
283        let payload_elems = crate::kernel::total_len(&fused_dims)?;
284
285        Ok(Self {
286            src_dims: src_dims.into(),
287            src_strides: src_strides.into(),
288            dest_dims: dest_dims.into(),
289            dest_strides: dest_strides.into(),
290            payload_dims: fused_dims,
291            payload_strides: fused_strides,
292            src_row_stride: src_strides[0],
293            dest_row_stride: dest_strides[0],
294            rows: runs.rows(),
295            runs: runs.runs(),
296            payload_elems,
297        })
298    }
299
300    /// Execute the overwriting form: `dest[r, ..] = Σ` over the run, zeros for a
301    /// run with no rows. Never reads the previous destination value.
302    ///
303    /// # Errors
304    ///
305    /// Returns [`StridedError::PlanLayoutMismatch`] when a view does not carry
306    /// its compiled extents and strides, and [`StridedError::ShapeMismatch`]
307    /// when `runs` describes a different row or run count than `compile` was
308    /// given.
309    pub fn execute_into<T>(
310        &self,
311        dest: &mut RawStridedMut<'_, T>,
312        src: &RawStridedRef<'_, T>,
313        runs: &RunIndex,
314        exec: Exec<'_>,
315    ) -> Result<()>
316    where
317        T: Copy + Zero + Add<Output = T> + Send + Sync,
318    {
319        self.execute(dest, src, runs, true, exec)
320    }
321
322    /// Execute the accumulating form: `dest[r, ..] += Σ` over the run, nothing
323    /// for a run with no rows.
324    ///
325    /// # Errors
326    ///
327    /// As [`execute_into`](Self::execute_into).
328    pub fn execute_acc<T>(
329        &self,
330        dest: &mut RawStridedMut<'_, T>,
331        src: &RawStridedRef<'_, T>,
332        runs: &RunIndex,
333        exec: Exec<'_>,
334    ) -> Result<()>
335    where
336        T: Copy + Zero + Add<Output = T> + Send + Sync,
337    {
338        self.execute(dest, src, runs, false, exec)
339    }
340
341    fn execute<T>(
342        &self,
343        dest: &mut RawStridedMut<'_, T>,
344        src: &RawStridedRef<'_, T>,
345        runs: &RunIndex,
346        into: bool,
347        exec: Exec<'_>,
348    ) -> Result<()>
349    where
350        T: Copy + Zero + Add<Output = T> + Send + Sync,
351    {
352        self.check_call(dest, src, runs)?;
353        if self.runs == 0 || self.payload_elems == 0 {
354            return Ok(());
355        }
356        // `_into` and `_acc` both pay the destination's writes.
357        let elements = self
358            .rows
359            .saturating_add(self.runs)
360            .saturating_mul(self.payload_elems);
361        let width = tree_width(&exec, KernelClass::Reduce, elements);
362        if self.rows == 0 {
363            // No source element is reachable, so an empty source's payload
364            // strides carry no bound (`RawStridedRef` validates the reach of the
365            // whole layout, which a zero row extent makes empty). Walking them
366            // would overflow the odometer, so the source is not walked at all:
367            // `_into` zeroes the destination rows, `_acc` adds nothing.
368            if into {
369                self.zero_destination(dest)?;
370            }
371            return Ok(());
372        }
373        let leaf = Leaf {
374            plan: self,
375            // `as_mut_ptr`/`ptr` already fold each layout's base offset in.
376            dest: SendPtr(dest.as_mut_ptr()),
377            src: SendPtr(src.ptr() as *mut T),
378            into,
379            ptr: runs.ptr(),
380            perm: runs.perm(),
381        };
382        let body = |range: Range<usize>| {
383            for run in range {
384                // SAFETY: `check_call` matched the compiled layouts,
385                // `RawStridedMut`/`RawStridedRef` validated the reach of those
386                // layouts, no extent is zero (returned above), the destination
387                // layout is injective so its rows are disjoint, and every run
388                // belongs to exactly one leaf.
389                unsafe { leaf.run(run) };
390            }
391        };
392        self.dispatch(runs.ptr(), 0..self.runs, exec.limit(width), &body);
393        Ok(())
394    }
395
396    /// `dest[r, ..] = 0` for every run, walking the destination alone.
397    ///
398    /// Only reached when the source has no rows, so the fused payload axes and
399    /// their destination strides are the whole traversal.
400    fn zero_destination<T: Copy + Zero>(&self, dest: &mut RawStridedMut<'_, T>) -> Result<()> {
401        let base = SendPtr(dest.as_mut_ptr());
402        let mut apply = |offsets: &[isize], len: usize, inner: &[isize]| -> Result<()> {
403            let dest_inner = inner.first().copied().unwrap_or(0);
404            for run in 0..self.runs {
405                let block = run as isize * self.dest_row_stride + offsets[0];
406                // SAFETY: `check_call` matched the compiled layout,
407                // `RawStridedMut` validated the reach of it, and the destination
408                // layout is injective, so this block is the run's own slots.
409                unsafe { zero_block(base.as_ptr(), block, len, dest_inner) };
410            }
411            Ok(())
412        };
413        for_each_inner_block_with_offsets(
414            &self.payload_dims,
415            &self.payload_dims,
416            &self.payload_strides[..1],
417            &[0],
418            &mut apply,
419        )
420    }
421
422    fn check_call<T>(
423        &self,
424        dest: &RawStridedMut<'_, T>,
425        src: &RawStridedRef<'_, T>,
426        runs: &RunIndex,
427    ) -> Result<()> {
428        if dest.dims() != &self.dest_dims[..]
429            || dest.strides() != &self.dest_strides[..]
430            || src.dims() != &self.src_dims[..]
431            || src.strides() != &self.src_strides[..]
432        {
433            return Err(StridedError::PlanLayoutMismatch);
434        }
435        if runs.rows() != self.rows || runs.runs() != self.runs {
436            return Err(StridedError::ShapeMismatch(
437                vec![runs.rows(), runs.runs()],
438                vec![self.rows, self.runs],
439            ));
440        }
441        Ok(())
442    }
443
444    /// Halve the run range at its row-count midpoint until the token's budget
445    /// is spent, one run per leaf at the leaves.
446    ///
447    /// Splitting only between runs is what keeps the result independent of the
448    /// budget: no run is ever assembled from two leaves.
449    fn dispatch(
450        &self,
451        ptr: &[usize],
452        runs: Range<usize>,
453        exec: Exec<'_>,
454        body: &(impl Fn(Range<usize>) + Sync),
455    ) {
456        if exec.budget().get() <= 1 || runs.len() <= 1 {
457            body(runs);
458            return;
459        }
460        let middle = row_midpoint(ptr, &runs);
461        exec.fork(2, |job, child| {
462            let half = if job == 0 {
463                runs.start..middle
464            } else {
465                middle..runs.end
466            };
467            self.dispatch(ptr, half, child, body);
468        });
469    }
470}
471
472/// The run index that halves `runs`' row count, strictly inside the range so
473/// the split always makes progress.
474fn row_midpoint(ptr: &[usize], runs: &Range<usize>) -> usize {
475    let target = ptr[runs.start] + (ptr[runs.end] - ptr[runs.start]) / 2;
476    // `ptr` is non-decreasing (both constructors enforce it), so the first run
477    // starting at or after the midpoint is the split; the clamp keeps it inside
478    // the range even when several runs share a start.
479    ptr.partition_point(|&start| start < target)
480        .clamp(runs.start + 1, runs.end - 1)
481}
482
483/// One execution's leaf data: the compiled plan, the two bases, and the shared
484/// topology.
485struct Leaf<'a, 'plan, T> {
486    plan: &'plan RunSumPlan,
487    dest: SendPtr<T>,
488    src: SendPtr<T>,
489    into: bool,
490    ptr: &'a [usize],
491    perm: Option<&'a [usize]>,
492}
493
494impl<T> Leaf<'_, '_, T>
495where
496    T: Copy + Zero + Add<Output = T>,
497{
498    /// Sum one run into its destination row.
499    ///
500    /// # Safety
501    ///
502    /// The caller proved the buffers and both layouts, no extent is zero, and
503    /// this run's destination row is not touched by another worker.
504    unsafe fn run(&self, run: usize) {
505        let plan = self.plan;
506        let start = self.ptr[run];
507        let end = self.ptr[run + 1];
508        let dest_base = run as isize * plan.dest_row_stride;
509        let mut apply = |offsets: &[isize], len: usize, inner: &[isize]| -> Result<()> {
510            let dest_block = dest_base + offsets[0];
511            let src_block = offsets[1];
512            // A rank-0 payload reaches this once with `len == 1` and no strides.
513            let dest_inner = inner.first().copied().unwrap_or(0);
514            let src_inner = inner.get(1).copied().unwrap_or(0);
515            // SAFETY: the walk visits the payload inside the validated layouts,
516            // and the run's blocks are inside this leaf's destination row.
517            unsafe {
518                if self.into {
519                    zero_block(self.dest.as_ptr(), dest_block, len, dest_inner);
520                }
521                for row in start..end {
522                    let source_row = match self.perm {
523                        Some(perm) => perm[row],
524                        None => row,
525                    };
526                    add_block(
527                        self.dest.as_ptr(),
528                        dest_block,
529                        self.src.as_const(),
530                        src_block + source_row as isize * plan.src_row_stride,
531                        len,
532                        dest_inner,
533                        src_inner,
534                    );
535                }
536            }
537            Ok(())
538        };
539        let walk = for_each_inner_block_with_offsets(
540            &plan.payload_dims,
541            &plan.payload_dims,
542            &plan.payload_strides,
543            &[0, 0],
544            &mut apply,
545        );
546        // The walk propagates the leaf callback's own result, and this leaf
547        // never fails; a failure would be a defect in the walk itself.
548        debug_assert!(walk.is_ok(), "the sorted-run leaf is infallible");
549    }
550}
551
552/// Write `T::zero()` over the block `len` runs of `dest_inner`.
553///
554/// # Safety
555///
556/// Every `dest.add(block + index * dest_inner)` for `index < len` must be a
557/// writable, `T`-aligned slot this call owns.
558unsafe fn zero_block<T: Copy + Zero>(dest: *mut T, block: isize, len: usize, dest_inner: isize) {
559    let base = dest.offset(block);
560    if dest_inner == 1 {
561        // SAFETY: a unit inner stride makes the block one contiguous run the
562        // caller proved writable.
563        let out = unsafe { core::slice::from_raw_parts_mut(base, len) };
564        for slot in out {
565            *slot = T::zero();
566        }
567        return;
568    }
569    for index in 0..len {
570        // Address arithmetic from the base, never past the final slot: the last
571        // write is at `(len - 1) * dest_inner`.
572        let slot = unsafe { base.offset(index as isize * dest_inner) };
573        // SAFETY: as above, one strided slot at a time.
574        unsafe { slot.write(T::zero()) };
575    }
576}
577
578/// `dest_block += src_block` over the block `len` runs of the inner strides.
579///
580/// # Safety
581///
582/// Both blocks must be `len` reachable, `T`-aligned slots of their own
583/// allocation; the destination slots must be initialized and exclusively owned
584/// by this call.
585unsafe fn add_block<T: Copy + Add<Output = T>>(
586    dest: *mut T,
587    dest_block: isize,
588    src: *const T,
589    src_block: isize,
590    len: usize,
591    dest_inner: isize,
592    src_inner: isize,
593) {
594    if dest_inner == 1 && src_inner == 1 {
595        // SAFETY: both unit-stride blocks are contiguous runs inside their
596        // validated layouts.
597        let out = unsafe { core::slice::from_raw_parts_mut(dest.offset(dest_block), len) };
598        let input = unsafe { core::slice::from_raw_parts(src.offset(src_block), len) };
599        for (slot, &value) in out.iter_mut().zip(input.iter()) {
600            *slot = *slot + value;
601        }
602        return;
603    }
604    for index in 0..len {
605        // Address arithmetic from the base, never past the final slot: the last
606        // element is at `(len - 1) * inner`.
607        let step = index as isize;
608        let destination = unsafe { dest.offset(dest_block + step * dest_inner) };
609        let source = unsafe { src.offset(src_block + step * src_inner) };
610        // SAFETY: as above, one strided element at a time.
611        unsafe { *destination = *destination + *source };
612    }
613}
614
615#[cfg(test)]
616#[path = "run_sum/tests/tests.rs"]
617mod tests;
618
619// Not under miri: `threading::test_pool` reads the host topology through the
620// filesystem, which miri's isolation refuses. The serial tests in `run_sum/tests`
621// are the miri surface for this module.
622#[cfg(all(test, not(miri)))]
623#[path = "run_sum/tests/parallel_tests.rs"]
624mod parallel_tests;