use core::ops::{Add, Range};
use num_traits::Zero;
use crate::cost::{tree_width, KernelClass};
use crate::fuse::{compress_dims, fuse_dims};
use crate::gather_plan::GatherIndex;
use crate::inline::{InlineVec, OperandVec};
use crate::threading::{for_each_inner_block_with_offsets, SendPtr};
use crate::{Exec, RawStridedMut, RawStridedRef, Result, StridedError};
#[derive(Debug, Clone)]
pub struct RunIndex {
ptr: Vec<usize>,
perm: Option<Vec<usize>>,
}
impl RunIndex {
pub fn from_dest<I: GatherIndex>(dest: &[I], num_runs: usize) -> Result<Self> {
if num_runs > isize::MAX as usize / core::mem::size_of::<usize>() {
return Err(StridedError::OffsetOverflow);
}
let counts = counts_of(dest, num_runs)?;
let mut ptr: Vec<usize> = Vec::with_capacity(num_runs + 1);
let mut grouped = 0usize;
ptr.push(0);
for &count in counts.iter() {
grouped = grouped
.checked_add(count)
.ok_or(StridedError::OffsetOverflow)?;
ptr.push(grouped);
}
if is_grouped(dest) {
return Ok(Self { ptr, perm: None });
}
let mut cursor = counts;
let mut start = 0usize;
for slot in cursor.iter_mut() {
let count = *slot;
*slot = start;
start += count;
}
let mut perm = vec![0usize; dest.len()];
for (row, &index) in dest.iter().enumerate() {
let run = run_of(index, num_runs)?;
let slot = cursor[run];
perm[slot] = row;
cursor[run] = slot + 1;
}
Ok(Self {
ptr,
perm: Some(perm),
})
}
pub fn from_ptr(ptr: Vec<usize>) -> Result<Self> {
if ptr.first() != Some(&0) || ptr.windows(2).any(|pair| pair[0] > pair[1]) {
return Err(StridedError::InvalidRunIndex);
}
Ok(Self { ptr, perm: None })
}
pub fn ptr(&self) -> &[usize] {
&self.ptr
}
pub fn perm(&self) -> Option<&[usize]> {
self.perm.as_deref()
}
fn rows(&self) -> usize {
self.ptr[self.ptr.len() - 1]
}
fn runs(&self) -> usize {
self.ptr.len() - 1
}
}
fn counts_of<I: GatherIndex>(dest: &[I], num_runs: usize) -> Result<Vec<usize>> {
let mut counts = vec![0usize; num_runs];
for &index in dest {
let run = run_of(index, num_runs)?;
counts[run] += 1;
}
Ok(counts)
}
fn run_of<I: GatherIndex>(index: I, num_runs: usize) -> Result<usize> {
let value = index.to_i64();
if value < 0 || value as u64 >= num_runs as u64 {
return Err(StridedError::IndexOutOfRange {
index: value,
runs: num_runs,
});
}
Ok(value as usize)
}
fn is_grouped<I: GatherIndex>(dest: &[I]) -> bool {
dest.windows(2)
.all(|pair| pair[0].to_i64() <= pair[1].to_i64())
}
#[derive(Debug)]
pub struct RunSumPlan {
src_dims: InlineVec<usize>,
src_strides: InlineVec<isize>,
dest_dims: InlineVec<usize>,
dest_strides: InlineVec<isize>,
payload_dims: InlineVec<usize>,
payload_strides: OperandVec<InlineVec<isize>>,
src_row_stride: isize,
dest_row_stride: isize,
rows: usize,
runs: usize,
payload_elems: usize,
}
impl RunSumPlan {
pub fn compile(
src_dims: &[usize],
src_strides: &[isize],
dest_dims: &[usize],
dest_strides: &[isize],
runs: &RunIndex,
) -> Result<Self> {
if src_dims.len() != src_strides.len() || dest_dims.len() != dest_strides.len() {
return Err(StridedError::StrideLengthMismatch);
}
if src_dims.len() != dest_dims.len() {
return Err(StridedError::RankMismatch(src_dims.len(), dest_dims.len()));
}
if src_dims.is_empty() {
return Err(StridedError::RankMismatch(0, 1));
}
if src_dims[0] != runs.rows() {
return Err(StridedError::ShapeMismatch(
vec![src_dims[0]],
vec![runs.rows()],
));
}
if dest_dims[0] != runs.runs() {
return Err(StridedError::ShapeMismatch(
vec![dest_dims[0]],
vec![runs.runs()],
));
}
if src_dims[1..] != dest_dims[1..] {
return Err(StridedError::ShapeMismatch(
src_dims.to_vec(),
dest_dims.to_vec(),
));
}
crate::kernel::total_len(src_dims)?;
crate::kernel::total_len(dest_dims)?;
if !crate::layout_check::is_injective_layout(dest_dims, dest_strides) {
return Err(StridedError::NonInjectiveOutputLayout);
}
let payload_dims = &src_dims[1..];
let payload_strides = [&dest_strides[1..], &src_strides[1..]];
let fused = fuse_dims(payload_dims, &payload_strides);
let (fused_dims, fused_strides) = compress_dims(&fused, &payload_strides);
let payload_elems = crate::kernel::total_len(&fused_dims)?;
Ok(Self {
src_dims: src_dims.into(),
src_strides: src_strides.into(),
dest_dims: dest_dims.into(),
dest_strides: dest_strides.into(),
payload_dims: fused_dims,
payload_strides: fused_strides,
src_row_stride: src_strides[0],
dest_row_stride: dest_strides[0],
rows: runs.rows(),
runs: runs.runs(),
payload_elems,
})
}
pub fn execute_into<T>(
&self,
dest: &mut RawStridedMut<'_, T>,
src: &RawStridedRef<'_, T>,
runs: &RunIndex,
exec: Exec<'_>,
) -> Result<()>
where
T: Copy + Zero + Add<Output = T> + Send + Sync,
{
self.execute(dest, src, runs, true, exec)
}
pub fn execute_acc<T>(
&self,
dest: &mut RawStridedMut<'_, T>,
src: &RawStridedRef<'_, T>,
runs: &RunIndex,
exec: Exec<'_>,
) -> Result<()>
where
T: Copy + Zero + Add<Output = T> + Send + Sync,
{
self.execute(dest, src, runs, false, exec)
}
fn execute<T>(
&self,
dest: &mut RawStridedMut<'_, T>,
src: &RawStridedRef<'_, T>,
runs: &RunIndex,
into: bool,
exec: Exec<'_>,
) -> Result<()>
where
T: Copy + Zero + Add<Output = T> + Send + Sync,
{
self.check_call(dest, src, runs)?;
if self.runs == 0 || self.payload_elems == 0 {
return Ok(());
}
let elements = self
.rows
.saturating_add(self.runs)
.saturating_mul(self.payload_elems);
let width = tree_width(&exec, KernelClass::Reduce, elements);
if self.rows == 0 {
if into {
self.zero_destination(dest)?;
}
return Ok(());
}
let leaf = Leaf {
plan: self,
dest: SendPtr(dest.as_mut_ptr()),
src: SendPtr(src.ptr() as *mut T),
into,
ptr: runs.ptr(),
perm: runs.perm(),
};
let body = |range: Range<usize>| {
for run in range {
unsafe { leaf.run(run) };
}
};
self.dispatch(runs.ptr(), 0..self.runs, exec.limit(width), &body);
Ok(())
}
fn zero_destination<T: Copy + Zero>(&self, dest: &mut RawStridedMut<'_, T>) -> Result<()> {
let base = SendPtr(dest.as_mut_ptr());
let mut apply = |offsets: &[isize], len: usize, inner: &[isize]| -> Result<()> {
let dest_inner = inner.first().copied().unwrap_or(0);
for run in 0..self.runs {
let block = run as isize * self.dest_row_stride + offsets[0];
unsafe { zero_block(base.as_ptr(), block, len, dest_inner) };
}
Ok(())
};
for_each_inner_block_with_offsets(
&self.payload_dims,
&self.payload_dims,
&self.payload_strides[..1],
&[0],
&mut apply,
)
}
fn check_call<T>(
&self,
dest: &RawStridedMut<'_, T>,
src: &RawStridedRef<'_, T>,
runs: &RunIndex,
) -> Result<()> {
if dest.dims() != &self.dest_dims[..]
|| dest.strides() != &self.dest_strides[..]
|| src.dims() != &self.src_dims[..]
|| src.strides() != &self.src_strides[..]
{
return Err(StridedError::PlanLayoutMismatch);
}
if runs.rows() != self.rows || runs.runs() != self.runs {
return Err(StridedError::ShapeMismatch(
vec![runs.rows(), runs.runs()],
vec![self.rows, self.runs],
));
}
Ok(())
}
fn dispatch(
&self,
ptr: &[usize],
runs: Range<usize>,
exec: Exec<'_>,
body: &(impl Fn(Range<usize>) + Sync),
) {
if exec.budget().get() <= 1 || runs.len() <= 1 {
body(runs);
return;
}
let middle = row_midpoint(ptr, &runs);
exec.fork(2, |job, child| {
let half = if job == 0 {
runs.start..middle
} else {
middle..runs.end
};
self.dispatch(ptr, half, child, body);
});
}
}
fn row_midpoint(ptr: &[usize], runs: &Range<usize>) -> usize {
let target = ptr[runs.start] + (ptr[runs.end] - ptr[runs.start]) / 2;
ptr.partition_point(|&start| start < target)
.clamp(runs.start + 1, runs.end - 1)
}
struct Leaf<'a, 'plan, T> {
plan: &'plan RunSumPlan,
dest: SendPtr<T>,
src: SendPtr<T>,
into: bool,
ptr: &'a [usize],
perm: Option<&'a [usize]>,
}
impl<T> Leaf<'_, '_, T>
where
T: Copy + Zero + Add<Output = T>,
{
unsafe fn run(&self, run: usize) {
let plan = self.plan;
let start = self.ptr[run];
let end = self.ptr[run + 1];
let dest_base = run as isize * plan.dest_row_stride;
let mut apply = |offsets: &[isize], len: usize, inner: &[isize]| -> Result<()> {
let dest_block = dest_base + offsets[0];
let src_block = offsets[1];
let dest_inner = inner.first().copied().unwrap_or(0);
let src_inner = inner.get(1).copied().unwrap_or(0);
unsafe {
if self.into {
zero_block(self.dest.as_ptr(), dest_block, len, dest_inner);
}
for row in start..end {
let source_row = match self.perm {
Some(perm) => perm[row],
None => row,
};
add_block(
self.dest.as_ptr(),
dest_block,
self.src.as_const(),
src_block + source_row as isize * plan.src_row_stride,
len,
dest_inner,
src_inner,
);
}
}
Ok(())
};
let walk = for_each_inner_block_with_offsets(
&plan.payload_dims,
&plan.payload_dims,
&plan.payload_strides,
&[0, 0],
&mut apply,
);
debug_assert!(walk.is_ok(), "the sorted-run leaf is infallible");
}
}
unsafe fn zero_block<T: Copy + Zero>(dest: *mut T, block: isize, len: usize, dest_inner: isize) {
let base = dest.offset(block);
if dest_inner == 1 {
let out = unsafe { core::slice::from_raw_parts_mut(base, len) };
for slot in out {
*slot = T::zero();
}
return;
}
for index in 0..len {
let slot = unsafe { base.offset(index as isize * dest_inner) };
unsafe { slot.write(T::zero()) };
}
}
unsafe fn add_block<T: Copy + Add<Output = T>>(
dest: *mut T,
dest_block: isize,
src: *const T,
src_block: isize,
len: usize,
dest_inner: isize,
src_inner: isize,
) {
if dest_inner == 1 && src_inner == 1 {
let out = unsafe { core::slice::from_raw_parts_mut(dest.offset(dest_block), len) };
let input = unsafe { core::slice::from_raw_parts(src.offset(src_block), len) };
for (slot, &value) in out.iter_mut().zip(input.iter()) {
*slot = *slot + value;
}
return;
}
for index in 0..len {
let step = index as isize;
let destination = unsafe { dest.offset(dest_block + step * dest_inner) };
let source = unsafe { src.offset(src_block + step * src_inner) };
unsafe { *destination = *destination + *source };
}
}
#[cfg(test)]
#[path = "run_sum/tests/tests.rs"]
mod tests;
#[cfg(all(test, not(miri)))]
#[path = "run_sum/tests/parallel_tests.rs"]
mod parallel_tests;