use crate::fuse::compute_costs_into;
use crate::inline::{InlineVec, OPERAND_CAP};
use crate::{BLOCK_MEMORY_SIZE, CACHE_LINE_SIZE};
use strided_view::auxiliary::index_order_into;
type Scratch<T> = tinyvec::TinyVec<[T; OPERAND_CAP * strided_view::INLINE_RANK]>;
struct Rows<'a> {
pitch: usize,
strides: &'a [&'a [isize]],
elem_sizes: &'a [usize],
orders: &'a [usize],
}
impl Rows<'_> {
fn orders(&self, operand: usize, offset: usize) -> &[usize] {
&self.orders[operand * self.pitch + offset..(operand + 1) * self.pitch]
}
}
pub(crate) fn compute_block_sizes(
dims: &[usize],
strides_list: &[&[isize]],
elem_sizes: &[usize],
) -> InlineVec<usize> {
debug_assert_eq!(strides_list.len(), elem_sizes.len());
let Some(blocks) = reduced_block_sizes(dims, strides_list, elem_sizes) else {
return InlineVec::from(dims);
};
if declines_tiles(dims, strides_list, elem_sizes, &blocks) {
return InlineVec::from(dims);
}
blocks
}
pub(crate) fn destination_block_sizes(
dims: &[usize],
strides_list: &[&[isize]],
elem_sizes: &[usize],
dest: usize,
) -> InlineVec<usize> {
let Some(mut blocks) = reduced_block_sizes(dims, strides_list, elem_sizes) else {
return InlineVec::from(dims);
};
if declines_tiles(dims, strides_list, elem_sizes, &blocks) {
return InlineVec::from(dims);
}
fit_l1_sets(dims, strides_list, elem_sizes, dest, &mut blocks);
blocks
}
pub(crate) fn fit_l1_sets(
dims: &[usize],
strides_list: &[&[isize]],
elem_sizes: &[usize],
dest: usize,
blocks: &mut [usize],
) {
debug_assert_eq!(strides_list.len(), elem_sizes.len());
debug_assert_eq!(dims.len(), blocks.len());
#[cfg(feature = "bench-hooks")]
let budget = crate::bench_hooks::L1_SET_BUDGET.load(core::sync::atomic::Ordering::Relaxed);
#[cfg(not(feature = "bench-hooks"))]
let budget = crate::L1_LIVE_LINES_PER_SET;
if budget == 0 || strides_list.len() != 2 {
return;
}
let sets = L1Sets::new(strides_list, elem_sizes);
if sets.load(blocks, None) <= budget as u128 {
return;
}
let frozen = |axis: usize| strides_list.get(dest).is_some_and(|s| s[axis] == 0);
for axis in (0..dims.len()).rev() {
if frozen(axis) {
continue;
}
let Some(floor) = sets.floor(axis, blocks[axis]) else {
continue;
};
let current = blocks[axis];
if sets.load(blocks, Some((axis, floor))) > budget as u128 {
blocks[axis] = floor;
continue;
}
let (mut lo, mut hi) = (floor, current - 1);
while lo < hi {
let mid = lo + (hi - lo).div_ceil(2);
if sets.load(blocks, Some((axis, mid))) <= budget as u128 {
lo = mid;
} else {
hi = mid - 1;
}
}
blocks[axis] = lo;
return;
}
}
struct L1Sets<'a> {
strides_list: &'a [&'a [isize]],
elem_sizes: &'a [usize],
}
impl<'a> L1Sets<'a> {
const LINE: u128 = CACHE_LINE_SIZE as u128;
const WAY: u128 = (BLOCK_MEMORY_SIZE / crate::L1_WAYS) as u128;
fn new(strides_list: &'a [&'a [isize]], elem_sizes: &'a [usize]) -> Self {
Self {
strides_list,
elem_sizes,
}
}
fn reuse_axis(&self, k: usize) -> Option<usize> {
let elem = self.elem_sizes[k] as u128;
if elem == 0 {
return None;
}
let strides = self.strides_list[k];
let c = strides
.iter()
.position(|&s| s.unsigned_abs() as u128 * elem < Self::LINE)?;
(c > 0).then_some(c)
}
fn aliases(&self, k: usize, axis: usize) -> bool {
let s = self.strides_list[k][axis].unsigned_abs() as u128 * self.elem_sizes[k] as u128;
s != 0 && s.is_multiple_of(Self::WAY)
}
fn load(&self, blocks: &[usize], with: Option<(usize, usize)>) -> u128 {
let extent = |axis: usize| match with {
Some((a, b)) if a == axis => b,
_ => blocks[axis],
};
(0..self.strides_list.len())
.filter_map(|k| {
let c = self.reuse_axis(k)?;
Some(
(0..c)
.filter(|&axis| self.aliases(k, axis))
.fold(1u128, |load, axis| {
load.saturating_mul(extent(axis) as u128)
}),
)
})
.fold(0u128, u128::saturating_add)
}
fn floor(&self, axis: usize, block: usize) -> Option<usize> {
let counted = (0..self.strides_list.len())
.any(|k| self.reuse_axis(k).is_some_and(|c| axis < c) && self.aliases(k, axis));
(counted && block > 1).then_some(1)
}
}
pub(crate) fn reduced_block_sizes(
dims: &[usize],
strides_list: &[&[isize]],
elem_sizes: &[usize],
) -> Option<InlineVec<usize>> {
debug_assert_eq!(strides_list.len(), elem_sizes.len());
if model_exits(dims, strides_list, elem_sizes) {
return None;
}
let len = strides_list.len().checked_mul(dims.len())?;
let mut orders: Scratch<usize> = Scratch::with_capacity(len);
orders.resize(len, 0);
let mut costs: InlineVec<isize> = InlineVec::with_capacity(dims.len());
costs.resize(dims.len(), 0);
let mut blocks = InlineVec::from(dims);
reduced_block_sizes_into(
dims,
strides_list,
elem_sizes,
&mut blocks,
&mut orders,
&mut costs,
);
Some(blocks)
}
pub(crate) fn model_exits(dims: &[usize], strides_list: &[&[isize]], elem_sizes: &[usize]) -> bool {
dims.is_empty()
|| memory_region(dims, strides_list, 0, elem_sizes) <= BLOCK_MEMORY_SIZE as u128
|| strides_list
.iter()
.zip(elem_sizes)
.all(|(strides, &elem_size)| elem_size > 0 && strictly_increasing(strides))
}
pub(crate) fn reduced_block_sizes_into(
dims: &[usize],
strides_list: &[&[isize]],
elem_sizes: &[usize],
blocks: &mut [usize],
orders: &mut [usize],
costs: &mut [isize],
) {
debug_assert_eq!(strides_list.len(), elem_sizes.len());
debug_assert_eq!(blocks.len(), dims.len());
debug_assert_eq!(costs.len(), dims.len());
debug_assert_eq!(orders.len(), strides_list.len() * dims.len());
debug_assert!(!model_exits(dims, strides_list, elem_sizes));
blocks.copy_from_slice(dims);
let pitch = dims.len();
for ((strides, &elem_size), row) in strides_list
.iter()
.zip(elem_sizes)
.zip(orders.chunks_exact_mut(pitch.max(1)))
{
if elem_size == 0 {
row.fill(1);
} else {
let filled = index_order_into(strides, row);
debug_assert!(filled.is_ok());
}
}
compute_costs_into(strides_list, costs);
let rows = Rows {
pitch,
strides: strides_list,
elem_sizes,
orders,
};
compute_blocks_at(blocks, 0, costs, &rows, BLOCK_MEMORY_SIZE);
}
fn strictly_increasing(strides: &[isize]) -> bool {
strides.first().is_some_and(|&s| s != 0)
&& strides
.windows(2)
.all(|w| w[0].unsigned_abs() < w[1].unsigned_abs())
}
#[cfg(test)]
fn byte_rows(byte_strides: &[&[u128]]) -> Vec<Vec<isize>> {
byte_strides
.iter()
.map(|s| {
s.iter()
.map(|&b| isize::try_from(b).expect("test byte strides fit isize"))
.collect()
})
.collect()
}
#[cfg(test)]
fn compute_blocks(
dims: &[usize],
costs: &[isize],
byte_strides: &[&[u128]],
stride_orders: &[&[usize]],
block_size: usize,
) -> InlineVec<usize> {
let mut blocks = InlineVec::from(dims);
if dims.is_empty() {
return blocks;
}
let strides = byte_rows(byte_strides);
let strides: Vec<&[isize]> = strides.iter().map(|s| s.as_slice()).collect();
let elem_sizes = vec![1usize; strides.len()];
let flat_orders: Vec<usize> = stride_orders
.iter()
.flat_map(|s| s.iter().copied())
.collect();
let rows = Rows {
pitch: dims.len(),
strides: &strides,
elem_sizes: &elem_sizes,
orders: &flat_orders,
};
compute_blocks_at(&mut blocks, 0, costs, &rows, block_size);
blocks
}
fn compute_blocks_at(
blocks: &mut [usize],
offset: usize,
costs: &[isize],
rows: &Rows<'_>,
block_size: usize,
) {
if offset == blocks.len() {
return;
}
let block_size_bytes = block_size as u128;
let region = |blocks: &[usize]| memory_region(blocks, rows.strides, offset, rows.elem_sizes);
if region(&blocks[offset..]) <= block_size_bytes {
return;
}
let operands = rows.strides.len();
let min_order = (0..operands)
.filter_map(|k| rows.orders(k, offset).iter().min().copied())
.min()
.unwrap_or(1);
if (0..operands).all(|k| rows.orders(k, offset).first() == Some(&min_order)) {
compute_blocks_at(blocks, offset + 1, costs, rows, block_size);
return;
}
let min_stride = rows
.strides
.iter()
.zip(rows.elem_sizes)
.filter_map(|(s, &elem_size)| {
s[offset..]
.iter()
.map(|&s| s.unsigned_abs() as u128 * elem_size as u128)
.min()
})
.min()
.unwrap_or(0);
let tail = &mut blocks[offset..];
if min_stride > block_size_bytes {
tail.fill(1);
return;
}
let costs = &costs[offset..];
while region(tail) >= 2 * block_size_bytes {
let Some(i) = last_argmax_weighted(tail, costs) else {
break;
};
tail[i] = tail[i].div_ceil(2);
}
while region(tail) > block_size_bytes {
let Some(i) = last_argmax_weighted(tail, costs) else {
break;
};
tail[i] -= 1;
}
}
trait RegionInt: Copy + Ord {
const ZERO: Self;
const ONE: Self;
fn from_usize(value: usize) -> Option<Self>;
fn add(self, other: Self) -> Option<Self>;
fn mul(self, other: Self) -> Option<Self>;
fn div(self, other: Self) -> Self;
}
impl RegionInt for u64 {
const ZERO: Self = 0;
const ONE: Self = 1;
fn from_usize(value: usize) -> Option<Self> {
u64::try_from(value).ok()
}
fn add(self, other: Self) -> Option<Self> {
self.checked_add(other)
}
fn mul(self, other: Self) -> Option<Self> {
self.checked_mul(other)
}
fn div(self, other: Self) -> Self {
self / other
}
}
impl RegionInt for u128 {
const ZERO: Self = 0;
const ONE: Self = 1;
fn from_usize(value: usize) -> Option<Self> {
Some(value as u128)
}
fn add(self, other: Self) -> Option<Self> {
Some(self.saturating_add(other))
}
fn mul(self, other: Self) -> Option<Self> {
Some(self.saturating_mul(other))
}
fn div(self, other: Self) -> Self {
self / other
}
}
fn memory_region(
dims: &[usize],
strides_list: &[&[isize]],
offset: usize,
elem_sizes: &[usize],
) -> u128 {
match region_in::<u64>(dims, strides_list, offset, elem_sizes) {
Some(region) => u128::from(region),
None => region_in::<u128>(dims, strides_list, offset, elem_sizes).unwrap_or(u128::MAX),
}
}
fn region_in<T: RegionInt>(
dims: &[usize],
strides_list: &[&[isize]],
offset: usize,
elem_sizes: &[usize],
) -> Option<T> {
let mut memory_region = T::ZERO;
for (strides, &elem_size) in strides_list.iter().zip(elem_sizes) {
let region = region_of::<T>(
dims.iter().copied().zip(strides[offset..].iter().copied()),
elem_size,
)?;
memory_region = memory_region.add(region)?;
}
Some(memory_region)
}
fn region_of<T: RegionInt>(
axes: impl Iterator<Item = (usize, isize)>,
elem_size: usize,
) -> Option<T> {
let cache_line = T::from_usize(CACHE_LINE_SIZE)?;
let elem_size = T::from_usize(elem_size)?;
let mut num_contiguous_bytes = T::ZERO;
let mut num_cache_line_blocks = T::ONE;
for (d, s) in axes {
let s = T::from_usize(s.unsigned_abs())?.mul(elem_size)?;
if s < cache_line {
num_contiguous_bytes =
num_contiguous_bytes.add(T::from_usize(d.saturating_sub(1))?.mul(s)?)?;
} else {
num_cache_line_blocks = num_cache_line_blocks.mul(T::from_usize(d)?)?;
}
}
let contiguous_lines = num_contiguous_bytes.div(cache_line).add(T::ONE)?;
cache_line.mul(contiguous_lines)?.mul(num_cache_line_blocks)
}
fn axes_region<I: Iterator<Item = (usize, isize)> + Clone>(axes: I, elem_size: usize) -> u128 {
region_of::<u64>(axes.clone(), elem_size)
.map(u128::from)
.or_else(|| region_of::<u128>(axes, elem_size))
.unwrap_or(u128::MAX)
}
fn axes_increasing<I: Iterator<Item = isize>>(mut axes: I) -> bool {
let Some(first) = axes.next() else {
return true;
};
if first == 0 {
return false;
}
let mut prev = first.unsigned_abs();
axes.all(|s| {
let m = s.unsigned_abs();
let ok = m > prev;
prev = m;
ok
})
}
pub(crate) fn exits_before_metadata<I>(axes: I, dst_elem_size: usize, src_elem_size: usize) -> bool
where
I: Iterator<Item = (usize, isize, isize)> + Clone,
{
let total =
axes_region(axes.clone().map(|(d, dst, _)| (d, dst)), dst_elem_size).saturating_add(
axes_region(axes.clone().map(|(d, _, src)| (d, src)), src_elem_size),
);
if total <= BLOCK_MEMORY_SIZE as u128 {
return true;
}
dst_elem_size > 0
&& src_elem_size > 0
&& axes_increasing(axes.clone().map(|(_, dst, _)| dst))
&& axes_increasing(axes.map(|(_, _, src)| src))
}
#[cfg(test)]
fn total_memory_region(dims: &[usize], byte_strides: &[&[u128]]) -> u128 {
let strides = byte_rows(byte_strides);
let strides: Vec<&[isize]> = strides.iter().map(|s| s.as_slice()).collect();
memory_region(dims, &strides, 0, &vec![1usize; strides.len()])
}
fn last_argmax_weighted(blocks: &[usize], costs: &[isize]) -> Option<usize> {
if blocks.is_empty() {
return None;
}
let mut max_score = 0u128;
let mut max_idx = None;
for (i, (&b, &c)) in blocks.iter().zip(costs.iter()).enumerate() {
if b <= 1 {
continue;
}
let score = (b - 1) as u128 * c as u128;
if score >= max_score {
max_score = score;
max_idx = Some(i);
}
}
max_idx
}
pub(crate) fn declines_tiles(
dims: &[usize],
strides_list: &[&[isize]],
elem_sizes: &[usize],
blocks: &[usize],
) -> bool {
debug_assert_eq!(strides_list.len(), elem_sizes.len());
#[cfg(feature = "bench-hooks")]
if !crate::bench_hooks::DECLINE_TILES.load(core::sync::atomic::Ordering::Relaxed) {
return false;
}
let Some(first_cut) = (0..dims.len()).find(|&axis| blocks[axis] < dims[axis]) else {
return false;
};
first_cut > 0
&& strides_list
.iter()
.zip(elem_sizes)
.all(|(strides, &elem_size)| slabs_share_no_line(dims, strides, first_cut, elem_size))
}
fn slabs_share_no_line(dims: &[usize], strides: &[isize], prefix: usize, elem_size: usize) -> bool {
if elem_size == 0 {
return true;
}
let line = crate::CACHE_LINE_SIZE as u128;
let elem = elem_size as u128;
let byte = |axis: usize| strides[axis].unsigned_abs() as u128 * elem;
let reach = |axis: usize| ((dims[axis] - 1) as u128).checked_mul(byte(axis));
let Some(width) = (0..prefix).try_fold(elem, |width, axis| width.checked_add(reach(axis)?))
else {
return false;
};
if width % line != 0 {
return false;
}
let count = dims.len() - prefix;
let fill = |tail: &mut [(u128, usize)]| {
for (slot, axis) in tail.iter_mut().zip(prefix..dims.len()) {
*slot = (byte(axis), axis);
}
};
let separated = |tail: &mut [(u128, usize)]| tail_separated(tail, width, line, &reach);
if count <= crate::raw_ops::RAW_FUSED_RANK_LIMIT {
let mut inline = [(0u128, 0usize); crate::raw_ops::RAW_FUSED_RANK_LIMIT];
let tail = &mut inline[..count];
fill(tail);
separated(tail)
} else if count <= crate::raw_ops::MAX_MOVING_AXES {
wide_tail_separated(count, &fill, &separated)
} else {
let mut tail = vec![(0u128, 0usize); count];
fill(&mut tail);
separated(&mut tail)
}
}
#[inline(never)]
fn wide_tail_separated(
count: usize,
fill: &impl Fn(&mut [(u128, usize)]),
separated: &impl Fn(&mut [(u128, usize)]) -> bool,
) -> bool {
let mut wide = [(0u128, 0usize); crate::raw_ops::MAX_MOVING_AXES];
let tail = &mut wide[..count];
fill(tail);
separated(tail)
}
fn tail_separated(
tail: &mut [(u128, usize)],
width: u128,
line: u128,
reach: &impl Fn(usize) -> Option<u128>,
) -> bool {
tail.sort_unstable();
let mut span = width;
for &(stride, axis) in tail.iter() {
if stride % line != 0 || stride < span {
return false;
}
let Some(next) = reach(axis).and_then(|reach| span.checked_add(reach)) else {
return false;
};
span = next;
}
true
}
#[cfg(test)]
#[path = "block/tests/tests.rs"]
mod tests;