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;