use crate::cost::KernelClass;
use crate::{ElementOpApply, Exec, RawStridedMut, RawStridedRef, Result};
use core::mem::MaybeUninit;
use core::num::NonZeroUsize;
use core::ops::{Add, Mul};
pub const RAW_FUSED_RANK_LIMIT: usize = 8;
#[derive(Clone, Copy, Debug)]
pub(crate) struct FusedAxis {
pub(crate) dim: usize,
pub(crate) dst: isize,
pub(crate) src: isize,
}
const EMPTY_AXIS: FusedAxis = FusedAxis {
dim: 1,
dst: 0,
src: 0,
};
#[derive(Clone, Copy, Debug)]
pub(crate) struct FusedPairLayout {
pub(crate) rank: usize,
pub(crate) dims: [usize; RAW_FUSED_RANK_LIMIT],
dst_strides: [isize; RAW_FUSED_RANK_LIMIT],
src_strides: [isize; RAW_FUSED_RANK_LIMIT],
}
impl FusedPairLayout {
fn empty() -> Self {
Self {
rank: 0,
dims: [1; RAW_FUSED_RANK_LIMIT],
dst_strides: [0; RAW_FUSED_RANK_LIMIT],
src_strides: [0; RAW_FUSED_RANK_LIMIT],
}
}
fn from_axes(axes: &[FusedAxis]) -> Self {
debug_assert!(axes.len() <= RAW_FUSED_RANK_LIMIT);
let mut layout = Self {
rank: axes.len(),
dims: [1; RAW_FUSED_RANK_LIMIT],
dst_strides: [0; RAW_FUSED_RANK_LIMIT],
src_strides: [0; RAW_FUSED_RANK_LIMIT],
};
for (slot, axis) in layout.dims[..axes.len()].iter_mut().zip(axes) {
*slot = axis.dim;
}
for (slot, axis) in layout.dst_strides[..axes.len()].iter_mut().zip(axes) {
*slot = axis.dst;
}
for (slot, axis) in layout.src_strides[..axes.len()].iter_mut().zip(axes) {
*slot = axis.src;
}
layout
}
}
#[derive(Clone, Debug)]
pub(crate) enum PairTraversal {
Inline(FusedPairLayout),
Spilled(Vec<FusedAxis>),
}
impl Default for FusedPairLayout {
fn default() -> Self {
Self::empty()
}
}
impl Default for PairTraversal {
fn default() -> Self {
Self::empty()
}
}
impl PairTraversal {
#[inline]
fn empty() -> Self {
Self::Inline(FusedPairLayout::empty())
}
#[inline]
pub(crate) fn inline(&self) -> Option<&FusedPairLayout> {
match self {
Self::Inline(layout) => Some(layout),
Self::Spilled(_) => None,
}
}
#[cfg(test)]
pub(crate) fn rank(&self) -> usize {
match self {
Self::Inline(layout) => layout.rank,
Self::Spilled(axes) => axes.len(),
}
}
}
fn fuse_axes(
scratch: &mut [FusedAxis],
dims: &[usize],
dst_strides: &[isize],
src_strides: &[isize],
) -> usize {
debug_assert!(scratch.len() >= dims.len());
let mut rank = 0usize;
for axis in 0..dims.len() {
if dims[axis] == 1 {
continue;
}
if dims[axis] == 0 {
scratch[0] = FusedAxis {
dim: 0,
dst: 0,
src: 0,
};
return 1;
}
let entry = FusedAxis {
dim: dims[axis],
dst: dst_strides[axis],
src: src_strides[axis],
};
let mut position = rank;
while position > 0 && scratch[position - 1].dst > entry.dst {
scratch[position] = scratch[position - 1];
position -= 1;
}
scratch[position] = entry;
rank += 1;
}
if rank == 0 {
scratch[0] = EMPTY_AXIS;
return 1;
}
let mut fused = 0usize;
for axis in 1..rank {
let merged = isize::try_from(scratch[fused].dim)
.ok()
.filter(|&extent| {
scratch[fused].dst.checked_mul(extent) == Some(scratch[axis].dst)
&& scratch[fused].src.checked_mul(extent) == Some(scratch[axis].src)
})
.and_then(|_| scratch[fused].dim.checked_mul(scratch[axis].dim));
if let Some(merged) = merged {
scratch[fused].dim = merged;
} else {
fused += 1;
scratch[fused] = scratch[axis];
}
}
fused + 1
}
pub(crate) fn fuse_pair_traversal(
dims: &[usize],
dst_strides: &[isize],
src_strides: &[isize],
) -> PairTraversal {
if dims.len() <= RAW_FUSED_RANK_LIMIT {
let mut scratch = [EMPTY_AXIS; RAW_FUSED_RANK_LIMIT];
let rank = fuse_axes(&mut scratch, dims, dst_strides, src_strides);
debug_assert!(rank <= RAW_FUSED_RANK_LIMIT);
return PairTraversal::Inline(FusedPairLayout::from_axes(&scratch[..rank]));
}
let mut scratch = vec![EMPTY_AXIS; dims.len()];
let rank = fuse_axes(&mut scratch, dims, dst_strides, src_strides);
scratch.truncate(rank);
if rank <= RAW_FUSED_RANK_LIMIT {
PairTraversal::Inline(FusedPairLayout::from_axes(&scratch))
} else {
PairTraversal::Spilled(scratch)
}
}
impl PairTraversal {
pub(crate) fn given(dims: &[usize], dst_strides: &[isize], src_strides: &[isize]) -> Self {
debug_assert!(dims.len() == dst_strides.len() && dims.len() == src_strides.len());
let rank = dims.len();
if rank > RAW_FUSED_RANK_LIMIT {
return Self::Spilled(
dims.iter()
.zip(dst_strides)
.zip(src_strides)
.map(|((&dim, &dst), &src)| FusedAxis { dim, dst, src })
.collect(),
);
}
let mut layout = FusedPairLayout::empty();
layout.rank = rank.max(1);
layout.dims[..rank].copy_from_slice(dims);
layout.dst_strides[..rank].copy_from_slice(dst_strides);
layout.src_strides[..rank].copy_from_slice(src_strides);
Self::Inline(layout)
}
}
pub(crate) fn fuse_pair_layout(
dims: &[usize],
dst_strides: &[isize],
src_strides: &[isize],
) -> Option<FusedPairLayout> {
match fuse_pair_traversal(dims, dst_strides, src_strides) {
PairTraversal::Inline(layout) => Some(layout),
PairTraversal::Spilled(_) => None,
}
}
#[inline]
pub(crate) fn fused_total(layout: &FusedPairLayout) -> usize {
layout.dims[..layout.rank].iter().product()
}
#[inline]
fn spilled_total(axes: &[FusedAxis]) -> usize {
axes.iter().map(|axis| axis.dim).product()
}
pub(crate) fn apply_fused_pair<D, S, Apply>(
dst: &mut RawStridedMut<'_, D>,
src: &RawStridedRef<'_, S>,
layout: &FusedPairLayout,
apply: Apply,
) where
D: Copy,
S: Copy,
Apply: Fn(&mut D, S),
{
let total = fused_total(layout);
if total == 0 {
return;
}
let src_ptr = src.data().as_ptr();
let src_base = src.offset();
let dst_base = dst.offset();
let dst_ptr = dst.data_mut().as_mut_ptr();
unsafe {
apply_fused_range(
dst_ptr, dst_base, src_ptr, src_base, layout, 0, total, &apply,
);
}
}
#[inline(never)]
pub(crate) fn apply_spilled_pair<D, S, Apply>(
dst: &mut RawStridedMut<'_, D>,
src: &RawStridedRef<'_, S>,
axes: &[FusedAxis],
apply: Apply,
) where
D: Copy,
S: Copy,
Apply: Fn(&mut D, S),
{
let total = spilled_total(axes);
if total == 0 {
return;
}
let src_ptr = src.data().as_ptr();
let src_base = src.offset();
let dst_base = dst.offset();
let dst_ptr = dst.data_mut().as_mut_ptr();
unsafe {
apply_spilled_range(dst_ptr, dst_base, src_ptr, src_base, axes, 0, total, &apply);
}
}
#[allow(clippy::too_many_arguments)]
pub(crate) unsafe fn apply_fused_range<D, S, Apply>(
dst_ptr: *mut D,
dst_base: isize,
src_ptr: *const S,
src_base: isize,
layout: &FusedPairLayout,
start: usize,
len: usize,
apply: &Apply,
) where
D: Copy,
S: Copy,
Apply: Fn(&mut D, S),
{
if len == 0 {
return;
}
let rank = layout.rank;
let inner_len = layout.dims[0];
let inner_dst = layout.dst_strides[0];
let inner_src = layout.src_strides[0];
let mut index = [0usize; RAW_FUSED_RANK_LIMIT];
let mut rest = start;
let mut dst_outer = dst_base;
let mut src_outer = src_base;
#[allow(clippy::needless_range_loop)]
for axis in 0..rank {
let dim = layout.dims[axis];
index[axis] = rest % dim;
rest /= dim;
if axis > 0 {
dst_outer += index[axis] as isize * layout.dst_strides[axis];
src_outer += index[axis] as isize * layout.src_strides[axis];
}
}
let mut inner_start = index[0];
let mut remaining = len;
loop {
let run = (inner_len - inner_start).min(remaining);
let dst_run = dst_outer + inner_start as isize * inner_dst;
let src_run = src_outer + inner_start as isize * inner_src;
unsafe {
apply_run(
dst_ptr, dst_run, inner_dst, src_ptr, src_run, inner_src, run, apply,
)
};
remaining -= run;
if remaining == 0 {
return;
}
inner_start = 0;
let mut axis = 1;
while axis < rank {
if index[axis] + 1 < layout.dims[axis] {
index[axis] += 1;
dst_outer += layout.dst_strides[axis];
src_outer += layout.src_strides[axis];
break;
}
let last = (layout.dims[axis] - 1) as isize;
dst_outer -= last * layout.dst_strides[axis];
src_outer -= last * layout.src_strides[axis];
index[axis] = 0;
axis += 1;
}
}
}
#[allow(clippy::too_many_arguments)]
#[inline(never)]
pub(crate) unsafe fn apply_spilled_range<D, S, Apply>(
dst_ptr: *mut D,
dst_base: isize,
src_ptr: *const S,
src_base: isize,
axes: &[FusedAxis],
start: usize,
len: usize,
apply: &Apply,
) where
D: Copy,
S: Copy,
Apply: Fn(&mut D, S),
{
if len == 0 {
return;
}
let rank = axes.len();
let inner_len = axes[0].dim;
let inner_dst = axes[0].dst;
let inner_src = axes[0].src;
let mut index = vec![0usize; rank];
let mut rest = start;
let mut dst_outer = dst_base;
let mut src_outer = src_base;
for axis in 0..rank {
let dim = axes[axis].dim;
index[axis] = rest % dim;
rest /= dim;
if axis > 0 {
dst_outer += index[axis] as isize * axes[axis].dst;
src_outer += index[axis] as isize * axes[axis].src;
}
}
let mut inner_start = index[0];
let mut remaining = len;
loop {
let run = (inner_len - inner_start).min(remaining);
let dst_run = dst_outer + inner_start as isize * inner_dst;
let src_run = src_outer + inner_start as isize * inner_src;
unsafe {
apply_run(
dst_ptr, dst_run, inner_dst, src_ptr, src_run, inner_src, run, apply,
)
};
remaining -= run;
if remaining == 0 {
return;
}
inner_start = 0;
let mut axis = 1;
while axis < rank {
if index[axis] + 1 < axes[axis].dim {
index[axis] += 1;
dst_outer += axes[axis].dst;
src_outer += axes[axis].src;
break;
}
let last = (axes[axis].dim - 1) as isize;
dst_outer -= last * axes[axis].dst;
src_outer -= last * axes[axis].src;
index[axis] = 0;
axis += 1;
}
}
}
#[allow(clippy::too_many_arguments)]
#[inline(always)]
unsafe fn apply_run<D, S, Apply>(
dst_ptr: *mut D,
dst_offset: isize,
dst_stride: isize,
src_ptr: *const S,
src_offset: isize,
src_stride: isize,
len: usize,
apply: &Apply,
) where
D: Copy,
S: Copy,
Apply: Fn(&mut D, S),
{
if dst_stride == 1 {
let dst_run = unsafe { core::slice::from_raw_parts_mut(dst_ptr.offset(dst_offset), len) };
if src_stride == 1 {
let src_run = unsafe { core::slice::from_raw_parts(src_ptr.offset(src_offset), len) };
for (dst, &value) in dst_run.iter_mut().zip(src_run) {
apply(dst, value);
}
return;
}
if src_stride == -1 {
let last = (len - 1) as isize;
let src_run =
unsafe { core::slice::from_raw_parts(src_ptr.offset(src_offset - last), len) };
for (dst, &value) in dst_run.iter_mut().zip(src_run.iter().rev()) {
apply(dst, value);
}
return;
}
let src_start = unsafe { src_ptr.offset(src_offset) };
for (position, dst) in dst_run.iter_mut().enumerate() {
let value = unsafe { *src_start.offset(position as isize * src_stride) };
apply(dst, value);
}
return;
}
let dst_start = unsafe { dst_ptr.offset(dst_offset) };
let src_start = unsafe { src_ptr.offset(src_offset) };
for position in 0..len {
let position = position as isize;
unsafe {
let value = *src_start.offset(position * src_stride);
apply(&mut *dst_start.offset(position * dst_stride), value);
}
}
}
fn ensure_same_dims(dst: &[usize], src: &[usize]) -> Result<()> {
if dst != src {
return Err(crate::StridedError::ShapeMismatch(
dst.to_vec(),
src.to_vec(),
));
}
crate::kernel::total_len(dst)?;
Ok(())
}
pub fn copy_scale_raw<T>(
dest: &mut RawStridedMut<'_, T>,
src: &RawStridedRef<'_, T>,
scale: T,
) -> Result<()>
where
T: Copy + Mul<T, Output = T> + ElementOpApply + Send + Sync,
{
ensure_same_dims(dest.dims(), src.dims())?;
match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
PairTraversal::Inline(layout) => {
apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
*dst = scale * value
})
}
PairTraversal::Spilled(axes) => {
apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
*dst = scale * value
})
}
}
Ok(())
}
pub fn copy_scale_conj_raw<T>(
dest: &mut RawStridedMut<'_, T>,
src: &RawStridedRef<'_, T>,
scale: T,
) -> Result<()>
where
T: Copy + Mul<T, Output = T> + ElementOpApply + Send + Sync,
{
ensure_same_dims(dest.dims(), src.dims())?;
match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
PairTraversal::Inline(layout) => {
apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
*dst = scale * value.conj()
})
}
PairTraversal::Spilled(axes) => {
apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
*dst = scale * value.conj()
})
}
}
Ok(())
}
pub fn axpy_raw<T>(
dest: &mut RawStridedMut<'_, T>,
src: &RawStridedRef<'_, T>,
alpha: T,
) -> Result<()>
where
T: Copy + Add<T, Output = T> + Mul<T, Output = T> + ElementOpApply + Send + Sync,
{
ensure_same_dims(dest.dims(), src.dims())?;
match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
PairTraversal::Inline(layout) => {
apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
*dst = *dst + alpha * value
})
}
PairTraversal::Spilled(axes) => {
apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
*dst = *dst + alpha * value
})
}
}
Ok(())
}
pub fn axpy_conj_raw<T>(
dest: &mut RawStridedMut<'_, T>,
src: &RawStridedRef<'_, T>,
alpha: T,
) -> Result<()>
where
T: Copy + Add<T, Output = T> + Mul<T, Output = T> + ElementOpApply + Send + Sync,
{
ensure_same_dims(dest.dims(), src.dims())?;
match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
PairTraversal::Inline(layout) => {
apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
*dst = *dst + alpha * value.conj()
})
}
PairTraversal::Spilled(axes) => {
apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
*dst = *dst + alpha * value.conj()
})
}
}
Ok(())
}
fn replay_given<D, S, Apply>(
dest: &mut RawStridedMut<'_, D>,
src: &RawStridedRef<'_, S>,
apply: Apply,
exec: Exec<'_>,
) -> Result<()>
where
D: Copy + Send + Sync,
S: Copy + Send + Sync,
Apply: Fn(&mut D, S) + Sync,
{
ensure_same_dims(dest.dims(), src.dims())?;
let total = crate::kernel::total_len(dest.dims())?;
if total == 0 {
return Ok(());
}
let traversal = PairTraversal::given(dest.dims(), dest.strides(), src.strides());
let mut exec = crate::cost::for_len(exec, KernelClass::Copy, total);
if !exec.is_serial()
&& !crate::layout_check::is_injective_layout_without_alloc(dest.dims(), dest.strides())
{
exec = exec.limit(NonZeroUsize::MIN);
}
unsafe { crate::copy_plan::replay_fused(dest, src, &traversal, apply, exec) };
Ok(())
}
pub fn replay_copy_raw<T>(
dest: &mut RawStridedMut<'_, T>,
src: &RawStridedRef<'_, T>,
exec: Exec<'_>,
) -> Result<()>
where
T: Copy + Send + Sync,
{
replay_given(dest, src, |dst: &mut T, value: T| *dst = value, exec)
}
pub fn replay_copy_raw_uninit<T>(
dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
src: &RawStridedRef<'_, T>,
exec: Exec<'_>,
) -> Result<()>
where
T: Copy + Send + Sync,
{
replay_given(
dest,
src,
|dst: &mut MaybeUninit<T>, value: T| {
dst.write(value);
},
exec,
)
}
pub fn replay_map_raw<D, S, F>(
dest: &mut RawStridedMut<'_, D>,
src: &RawStridedRef<'_, S>,
f: F,
exec: Exec<'_>,
) -> Result<()>
where
D: Copy + Send + Sync,
S: Copy + Send + Sync,
F: Fn(&mut D, S) + Send + Sync,
{
replay_given(dest, src, f, exec)
}
pub fn replay_map_raw_uninit<D, S, F>(
dest: &mut RawStridedMut<'_, MaybeUninit<D>>,
src: &RawStridedRef<'_, S>,
f: F,
exec: Exec<'_>,
) -> Result<()>
where
D: Copy + Send + Sync,
S: Copy + Send + Sync,
F: Fn(S) -> D + Send + Sync,
{
replay_given(
dest,
src,
move |dst: &mut MaybeUninit<D>, value: S| {
dst.write(f(value));
},
exec,
)
}
#[cfg(test)]
#[path = "raw_ops/tests/tests.rs"]
mod tests;
#[cfg(test)]
#[path = "raw_ops/tests/replay_tests.rs"]
mod replay_tests;