use super::KernelScalar;
use super::simd::dist::{try_fill_ard_column, try_fill_cross_chunk, try_fill_lower_col};
use crate::error::GprError;
use faer::reborrow::ReborrowMut;
use faer::{ColMut, Mat, MatMut, MatRef};
use rayon::prelude::*;
use std::borrow::Cow;
use std::convert::Infallible;
use std::fmt;
use std::marker::PhantomData;
use wide::f64x4;
pub(crate) fn worker_count() -> usize {
rayon::current_num_threads().max(1)
}
pub(crate) fn col_chunk(n: usize, idx: usize, n_chunks: usize) -> (usize, usize) {
let chunk_size = n / n_chunks;
let rem = n % n_chunks;
let start = |i: usize| {
if i < rem {
i * (chunk_size + 1)
} else {
rem + i * chunk_size
}
};
let begin = start(idx);
(begin, start(idx + 1) - begin)
}
fn lower_area(n: usize, c: usize) -> u128 {
let (n, c) = (n as u128, c as u128);
c * n - c * c.saturating_sub(1) / 2
}
pub(crate) fn lower_block_start(n: usize, idx: usize, n_blocks: usize) -> usize {
let n_blocks = n_blocks.max(1);
if idx >= n_blocks {
return n;
}
let target = idx as u128 * lower_area(n, n);
let (mut lo, mut hi) = (0, n);
while lo < hi {
let mid = lo + (hi - lo) / 2;
if lower_area(n, mid) * n_blocks as u128 >= target {
hi = mid;
} else {
lo = mid + 1;
}
}
let k = n_blocks as u128;
if lo > 0 && target - lower_area(n, lo - 1) * k < lower_area(n, lo) * k - target {
lo - 1
} else {
lo
}
}
pub(crate) fn par_lower_blocks<T, E, F>(out: MatMut<'_, T>, n_blocks: usize, f: &F) -> Result<(), E>
where
T: Send,
E: Send,
F: Fn(usize, MatMut<'_, T>) -> Result<(), E> + Sync,
{
let n = out.ncols();
let n_blocks = n_blocks.max(1);
split_lower_blocks(out, n, (0, n_blocks), n_blocks, f)
}
fn split_lower_blocks<T, E, F>(
block: MatMut<'_, T>,
n: usize,
(lo, hi): (usize, usize),
n_blocks: usize,
f: &F,
) -> Result<(), E>
where
T: Send,
E: Send,
F: Fn(usize, MatMut<'_, T>) -> Result<(), E> + Sync,
{
let start = lower_block_start(n, lo, n_blocks);
if hi - lo <= 1 {
return f(start, block);
}
let mid = lo + (hi - lo) / 2;
let (left, right) = block.split_at_col_mut(lower_block_start(n, mid, n_blocks) - start);
let (a, b) = rayon::join(
|| split_lower_blocks(left, n, (lo, mid), n_blocks, f),
|| split_lower_blocks(right, n, (mid, hi), n_blocks, f),
);
a.and(b)
}
pub(crate) fn par_lower_cols<T, E, F>(out: MatMut<'_, T>, f: &F) -> Result<(), E>
where
T: Send,
E: Send,
F: Fn(usize, ColMut<'_, T>) -> Result<(), E> + Sync,
{
par_lower_cols_in(out, worker_count(), f)
}
pub(crate) fn par_lower_cols_in<T, E, F>(
out: MatMut<'_, T>,
n_blocks: usize,
f: &F,
) -> Result<(), E>
where
T: Send,
E: Send,
F: Fn(usize, ColMut<'_, T>) -> Result<(), E> + Sync,
{
let n = out.nrows();
par_lower_blocks(out, n_blocks, &|start, mut part: MatMut<'_, T>| {
for local in 0..part.ncols() {
let col = start + local;
f(col, part.rb_mut().col_mut(local).subrows_mut(col, n - col))?;
}
Ok(())
})
}
pub(crate) fn for_each_lower_col<T, F>(out: MatMut<'_, T>, f: &F)
where
T: Send,
F: Fn(usize, ColMut<'_, T>) + Sync,
{
let done: Result<(), Infallible> = par_lower_cols(out, &|col, rows| {
f(col, rows);
Ok(())
});
match done {
Ok(()) => {}
Err(never) => match never {},
}
}
pub(crate) fn lower_fold_infallible<R, F, J>(n: usize, f: &F, join: &J) -> R
where
R: Send,
F: Fn(usize, usize) -> R + Sync,
J: Fn(R, R) -> R + Sync,
{
let folded: Result<R, Infallible> = par_lower_fold(n, &|start, end| Ok(f(start, end)), join);
match folded {
Ok(value) => value,
Err(never) => match never {},
}
}
#[inline(always)]
pub(crate) fn lower_col<T>(m: MatRef<'_, T>, col: usize) -> Option<&[T]> {
m.col(col).try_as_col_major().map(|c| &c.as_slice()[col..])
}
const COL_CHUNK: usize = 16;
pub(crate) fn par_lower_fold<R, E, F, J>(n: usize, f: &F, join: &J) -> Result<R, E>
where
R: Send,
E: Send,
F: Fn(usize, usize) -> Result<R, E> + Sync,
J: Fn(R, R) -> R + Sync,
{
if n == 0 {
return f(0, 0);
}
let mut acc: Option<R> = None;
let mut start = 0;
while start < n {
let len = COL_CHUNK.min(n - start);
let mut slots: [Option<R>; COL_CHUNK] = std::array::from_fn(|_| None);
fill_col_sums(&mut slots[..len], start, f)?;
for (i, slot) in slots[..len].iter_mut().enumerate() {
let part = match slot.take() {
Some(part) => part,
None => {
debug_assert!(false, "par_lower_fold wrote every column");
f(start + i, start + i + 1)?
}
};
acc = Some(match acc {
None => part,
Some(prev) => join(prev, part),
});
}
start += len;
}
match acc {
Some(acc) => Ok(acc),
None => f(0, 0),
}
}
fn fill_col_sums<R, E, F>(slots: &mut [Option<R>], col0: usize, f: &F) -> Result<(), E>
where
R: Send,
E: Send,
F: Fn(usize, usize) -> Result<R, E> + Sync,
{
let n = slots.len();
if n == 0 {
return Ok(());
}
if n == 1 {
slots[0] = Some(f(col0, col0 + 1)?);
return Ok(());
}
let mid = n / 2;
let (left, right) = slots.split_at_mut(mid);
let (a, b) = if rayon::current_num_threads() > 1 {
rayon::join(
|| fill_col_sums(left, col0, f),
|| fill_col_sums(right, col0 + mid, f),
)
} else {
let a = fill_col_sums(left, col0, f);
let b = fill_col_sums(right, col0 + mid, f);
(a, b)
};
a.and(b)
}
fn partition_count(thread_scratch: &[Mat<f64>]) -> usize {
if thread_scratch.is_empty() {
worker_count()
} else {
thread_scratch.len()
}
.max(1)
}
pub(crate) fn fill_squared_euclidean(
x: MatRef<'_, f64>,
mut dist: MatMut<'_, f64>,
thread_scratch: &mut [Mat<f64>],
) {
let n = x.nrows();
if n == 0 {
return;
}
let n_parts = partition_count(thread_scratch);
let done: Result<(), Infallible> = par_lower_cols_in(dist.rb_mut(), n_parts, &|col, rows| {
fill_lower_col(x, col, rows);
Ok(())
});
match done {
Ok(()) => {}
Err(never) => match never {},
}
copy_lower_to_upper(dist);
}
pub(crate) fn packed_len(n: usize) -> Result<usize, GprError> {
n.checked_add(1)
.and_then(|n1| n.checked_mul(n1))
.map(|cells| cells / 2)
.ok_or(GprError::SizeOverflow)
}
fn pack_dense<T: Copy, U>(tables: &[Vec<T>], n: usize, f: impl Fn(T) -> U) -> Vec<U> {
let len = packed_len(n)
.ok()
.and_then(|tri| tri.checked_mul(tables.len()))
.unwrap_or(0);
let mut out = Vec::with_capacity(len);
for table in tables {
for col in 0..n {
out.extend(table[col * n + col..(col + 1) * n].iter().map(|&v| f(v)));
}
}
out
}
#[inline]
fn packed_col_offset(n: usize, col: usize) -> usize {
col * (2 * n - col + 1) / 2
}
#[derive(Clone, Debug)]
pub(crate) struct ArdSqDiffBuf<T> {
data: ArdStore<T>,
n: usize,
d: usize,
}
#[derive(Debug)]
enum ArdStore<T> {
Packed(Vec<T>),
Dense(Vec<Vec<T>>),
Rows(Vec<Vec<T>>),
}
pub(crate) fn packed_run(n: usize, dim: usize, col: usize) -> std::ops::Range<usize> {
let start = dim * (n * (n + 1) / 2) + packed_col_offset(n, col);
start..start + (n - col)
}
impl<T: Clone> Clone for ArdStore<T> {
fn clone(&self) -> Self {
match self {
Self::Packed(data) => Self::Packed(data.clone()),
Self::Dense(tables) => Self::Dense(tables.clone()),
Self::Rows(rows) => Self::Rows(
rows.iter()
.map(|dim| {
let mut copy = Vec::with_capacity(dim.capacity());
copy.extend_from_slice(dim);
copy
})
.collect(),
),
}
}
}
#[inline]
fn row_offset(i: usize) -> usize {
i * (i + 1) / 2
}
const ROW_RUN_TILE: usize = 16;
pub(crate) fn walk_row_runs(n: usize, mut f: impl FnMut(usize, usize, usize)) {
let mut j0 = 0;
while j0 < n {
let j1 = (j0 + ROW_RUN_TILE).min(n);
for i in j0..n {
let base = row_offset(i);
for j in j0..j1.min(i + 1) {
f(i, base + j, j);
}
}
j0 = j1;
}
}
impl<T: KernelScalar> ArdSqDiffBuf<T> {
pub(crate) fn new(x: MatRef<'_, T>) -> Result<Self, GprError> {
let n = x.nrows();
let d = x.ncols();
let len = packed_len(n)?
.checked_mul(d)
.ok_or(GprError::SizeOverflow)?;
let mut data = vec![T::from_f64(0.0); len];
T::write_ard(x, &mut data);
Ok(Self::from_packed(data, n, d))
}
#[cfg(test)]
pub(crate) fn from_pairs(
n: usize,
d: usize,
pair: impl Fn(usize, usize, usize) -> T,
) -> Result<Self, GprError> {
let len = packed_len(n)?
.checked_mul(d)
.ok_or(GprError::SizeOverflow)?;
let mut data = Vec::with_capacity(len);
for k in 0..d {
for col in 0..n {
for row in col..n {
data.push(pair(k, row, col));
}
}
}
Ok(Self::from_packed(data, n, d))
}
pub(crate) fn from_dense<'b>(
n: usize,
d: usize,
block: impl Fn(usize) -> &'b [f64],
) -> Result<Self, GprError> {
let len = packed_len(n)?
.checked_mul(d)
.ok_or(GprError::SizeOverflow)?;
let mut data = Vec::with_capacity(len);
for k in 0..d {
let block = block(k);
for col in 0..n {
data.extend(
block[col * n + col..(col + 1) * n]
.iter()
.map(|&v| T::from_f64(v)),
);
}
}
Ok(Self::from_packed(data, n, d))
}
pub(crate) fn from_packed(data: Vec<T>, n: usize, d: usize) -> Self {
debug_assert_eq!(
Some(data.len()),
packed_len(n).ok().and_then(|l| l.checked_mul(d))
);
Self {
data: ArdStore::Packed(data),
n,
d,
}
}
pub(crate) fn packed(&self) -> Cow<'_, [T]>
where
T: Copy,
{
let n = self.n;
match &self.data {
ArdStore::Packed(data) => Cow::Borrowed(data),
ArdStore::Dense(tables) => Cow::Owned(pack_dense(tables, n, |v| v)),
ArdStore::Rows(rows) => {
let mut out = Vec::with_capacity(self.stored_capacity_hint());
for dim in rows {
for col in 0..n {
out.extend((col..n).map(|row| dim[row * (row + 1) / 2 + col]));
}
}
Cow::Owned(out)
}
}
}
fn stored_capacity_hint(&self) -> usize {
packed_len(self.n)
.ok()
.and_then(|tri| tri.checked_mul(self.d))
.unwrap_or(0)
}
pub(crate) fn from_tables(tables: Vec<Vec<T>>, n: usize) -> Self {
debug_assert!(tables.iter().all(|t| Some(t.len()) == n.checked_mul(n)));
Self {
d: tables.len(),
data: ArdStore::Dense(tables),
n,
}
}
pub(crate) fn map<U>(&self, f: impl Fn(T) -> U) -> ArdSqDiffBuf<U>
where
T: Copy,
{
let data = match &self.data {
ArdStore::Packed(data) => ArdStore::Packed(data.iter().map(|&v| f(v)).collect()),
ArdStore::Rows(rows) => ArdStore::Rows(
rows.iter()
.map(|dim| dim.iter().map(|&v| f(v)).collect())
.collect(),
),
ArdStore::Dense(tables) => ArdStore::Packed(pack_dense(tables, self.n, f)),
};
ArdSqDiffBuf {
data,
n: self.n,
d: self.d,
}
}
pub(crate) fn reserve_point(&mut self) -> Result<(), GprError> {
self.lay_out_rows()?;
let n = self.n;
if let ArdStore::Rows(rows) = &mut self.data {
let more = n.checked_add(1).ok_or(GprError::SizeOverflow)?;
for dim in rows {
dim.try_reserve(more).map_err(|_| GprError::SizeOverflow)?;
}
}
Ok(())
}
pub(crate) fn ready_to_change(&mut self) -> Result<(), GprError> {
self.lay_out_rows()
}
fn lay_out_rows(&mut self) -> Result<(), GprError> {
if matches!(self.data, ArdStore::Rows(_)) {
return Ok(());
}
let n = self.n;
let len = packed_len(n)?;
let view = self.view();
let Runs::Lower(lower) = view.runs() else {
return Ok(());
};
let mut rows = Vec::with_capacity(self.d);
for dim in 0..self.d {
let mut out = Vec::new();
out.try_reserve_exact(packed_len(n + 1)?)
.map_err(|_| GprError::SizeOverflow)?;
out.resize(len, T::from_f64(0.0));
walk_row_runs(n, |i, at, j| out[at] = lower.column(dim, j)[i - j]);
rows.push(out);
}
self.data = ArdStore::Rows(rows);
Ok(())
}
pub(crate) fn can_push(&self) -> bool {
let n = self.n;
matches!(&self.data, ArdStore::Rows(rows)
if rows.iter().all(|dim| dim.capacity() - dim.len() > n))
}
pub(crate) fn can_remove(&self) -> bool {
matches!(self.data, ArdStore::Rows(_))
}
pub(crate) fn push_point<'c>(&mut self, column: impl Fn(usize) -> &'c [T])
where
T: 'c,
{
debug_assert!(self.can_push(), "push_point before reserve_point");
let n = self.n;
let ArdStore::Rows(rows) = &mut self.data else {
return;
};
for (dim, buffer) in rows.iter_mut().enumerate() {
buffer.extend_from_slice(&column(dim)[..n]);
buffer.push(T::from_f64(0.0));
}
self.n = n + 1;
}
pub(crate) fn remove_point(&mut self, index: usize) {
let n = self.n;
debug_assert!(index < n, "remove_point past the points");
debug_assert!(self.can_remove(), "remove_point before ready_to_change");
let ArdStore::Rows(rows) = &mut self.data else {
return;
};
let compact = |buffer: &mut Vec<T>| {
let mut write = row_offset(index);
for i in index + 1..n {
let start = row_offset(i);
buffer.copy_within(start..start + index, write);
write += index;
buffer.copy_within(start + index + 1..start + i + 1, write);
write += i - index;
}
buffer.truncate(write);
};
if rows.len() > 1 && rayon::current_thread_index().is_some() {
rows.par_iter_mut().for_each(compact);
} else {
rows.iter_mut().for_each(compact);
}
self.n = n - 1;
}
#[cfg(test)]
pub(crate) fn shape(&self) -> (usize, usize) {
(self.n, self.d)
}
#[cfg(test)]
pub(crate) fn stored_len(&self) -> usize {
match &self.data {
ArdStore::Packed(data) => data.len(),
ArdStore::Dense(tables) | ArdStore::Rows(tables) => tables.iter().map(Vec::len).sum(),
}
}
#[cfg(test)]
pub(crate) fn is_dense(&self) -> bool {
matches!(self.data, ArdStore::Dense(_))
}
#[cfg(test)]
pub(crate) fn poison(&mut self, value: T) {
match &mut self.data {
ArdStore::Packed(data) => data.fill(value),
ArdStore::Dense(tables) | ArdStore::Rows(tables) => {
tables.iter_mut().for_each(|t| t.fill(value));
}
}
}
pub(crate) fn view(&self) -> ArdSqDiff<'_, T> {
let data = match &self.data {
ArdStore::Packed(data) => {
StoreRef::Packed(data, data.len().checked_div(self.d).unwrap_or(0))
}
ArdStore::Dense(tables) => StoreRef::Dense(tables),
ArdStore::Rows(rows) => StoreRef::Rows(rows),
};
ArdSqDiff {
data,
n: self.n,
d: self.d,
}
}
}
#[derive(Clone, Copy, Debug)]
pub struct ArdSqDiff<'a, T> {
data: StoreRef<'a, T>,
n: usize,
d: usize,
}
#[derive(Clone, Copy, Debug)]
enum StoreRef<'a, T> {
Packed(&'a [T], usize),
Dense(&'a [Vec<T>]),
Flat(&'a [T]),
Rows(&'a [Vec<T>]),
}
#[derive(Clone, Copy, Debug)]
pub(crate) enum PairAt<'a, T> {
Strided {
data: &'a [T],
stride: usize,
at: usize,
},
Tables { tables: &'a [Vec<T>], at: usize },
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct LowerRuns<'a, T> {
data: ColumnRef<'a, T>,
n: usize,
}
#[derive(Clone, Copy, Debug)]
enum ColumnRef<'a, T> {
Packed(&'a [T], usize),
Dense(&'a [Vec<T>]),
Flat(&'a [T]),
}
#[derive(Clone, Copy, Debug)]
pub(crate) enum Runs<'a, T> {
Lower(LowerRuns<'a, T>),
Rows(RowRuns<'a, T>),
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct RowRuns<'a, T> {
rows: &'a [Vec<T>],
n: usize,
}
impl<'a, T> LowerRuns<'a, T> {
#[inline]
pub(crate) fn column(&self, dim: usize, col: usize) -> &'a [T] {
let n = self.n;
match self.data {
ColumnRef::Packed(data, block) => {
let start = dim * block + packed_col_offset(n, col);
&data[start..start + (n - col)]
}
ColumnRef::Dense(tables) => &tables[dim][col * n + col..(col + 1) * n],
ColumnRef::Flat(data) => {
&data[dim * n * n + col * n + col..dim * n * n + (col + 1) * n]
}
}
}
#[inline]
pub(crate) fn packed_block(&self, dim: usize) -> Option<&'a [T]> {
match self.data {
ColumnRef::Packed(data, block) => Some(&data[dim * block..(dim + 1) * block]),
ColumnRef::Dense(_) | ColumnRef::Flat(_) => None,
}
}
}
impl<'a, T> RowRuns<'a, T> {
pub(crate) fn n(&self) -> usize {
self.n
}
#[inline]
pub(crate) fn buffer(&self, dim: usize) -> &'a [T] {
&self.rows[dim][..row_offset(self.n)]
}
#[inline]
pub(crate) fn row(&self, dim: usize, i: usize) -> &'a [T] {
let start = row_offset(i);
&self.rows[dim][start..start + i + 1]
}
}
impl<'a, T: KernelScalar> ArdSqDiff<'a, T> {
pub(crate) fn flat(data: &'a [T], n: usize) -> Self {
let d = data.len().checked_div(n * n).unwrap_or(0);
Self {
data: StoreRef::Flat(data),
n,
d,
}
}
pub(crate) fn n(&self) -> usize {
self.n
}
pub(crate) fn d(&self) -> usize {
self.d
}
#[inline]
pub(crate) fn runs(&self) -> Runs<'a, T> {
let n = self.n;
match self.data {
StoreRef::Packed(data, block) => Runs::Lower(LowerRuns {
data: ColumnRef::Packed(data, block),
n,
}),
StoreRef::Dense(tables) => Runs::Lower(LowerRuns {
data: ColumnRef::Dense(tables),
n,
}),
StoreRef::Flat(data) => Runs::Lower(LowerRuns {
data: ColumnRef::Flat(data),
n,
}),
StoreRef::Rows(rows) => Runs::Rows(RowRuns { rows, n }),
}
}
#[inline]
pub(crate) fn lower(&self) -> Option<LowerRuns<'a, T>> {
match self.runs() {
Runs::Lower(lower) => Some(lower),
Runs::Rows(_) => None,
}
}
#[inline]
pub(crate) fn rows(&self) -> Option<RowRuns<'a, T>> {
match self.runs() {
Runs::Rows(rows) => Some(rows),
Runs::Lower(_) => None,
}
}
#[inline(always)]
pub(crate) fn pair(&self, row: usize, col: usize) -> PairAt<'a, T> {
let (row, col) = if row >= col { (row, col) } else { (col, row) };
let n = self.n;
match self.data {
StoreRef::Packed(data, block) => PairAt::Strided {
data,
stride: block,
at: packed_col_offset(n, col) + row - col,
},
StoreRef::Flat(data) => PairAt::Strided {
data,
stride: n * n,
at: col * n + row,
},
StoreRef::Dense(tables) => PairAt::Tables {
tables,
at: col * n + row,
},
StoreRef::Rows(rows) => PairAt::Tables {
tables: rows,
at: row_offset(row) + col,
},
}
}
#[inline]
pub(crate) fn get(&self, dim: usize, row: usize, col: usize) -> T {
let (row, col) = if row >= col { (row, col) } else { (col, row) };
let n = self.n;
match self.data {
StoreRef::Packed(data, block) => {
data[dim * block + packed_col_offset(n, col) + row - col]
}
StoreRef::Rows(rows) => rows[dim][row_offset(row) + col],
StoreRef::Dense(tables) => tables[dim][col * n + row],
StoreRef::Flat(data) => data[dim * n * n + col * n + row],
}
}
pub(crate) fn position(&self, dim: usize, bad: impl Fn(T) -> bool) -> Option<(usize, usize)> {
match self.runs() {
Runs::Rows(rows) => (0..self.n).find_map(|i| {
rows.row(dim, i)
.iter()
.position(|&v| bad(v))
.map(|j| (i, j))
}),
Runs::Lower(lower) => (0..self.n).find_map(|j| {
lower
.column(dim, j)
.iter()
.position(|&v| bad(v))
.map(|k| (j + k, j))
}),
}
}
pub(crate) fn as_f64(self) -> Option<ArdSqDiff<'a, f64>> {
let data = match self.data {
StoreRef::Packed(data, block) => StoreRef::Packed(T::as_f64_slice(data)?, block),
StoreRef::Dense(tables) => StoreRef::Dense(T::as_f64_vecs(tables)?),
StoreRef::Flat(data) => StoreRef::Flat(T::as_f64_slice(data)?),
StoreRef::Rows(rows) => StoreRef::Rows(T::as_f64_vecs(rows)?),
};
Some(ArdSqDiff {
data,
n: self.n,
d: self.d,
})
}
}
pub trait BlockState: Copy + fmt::Debug + Send + Sync + 'static + sealed::Sealed {
const CHECKED: bool;
}
#[derive(Clone, Copy, Debug)]
pub enum Checked {}
#[derive(Clone, Copy, Debug)]
pub enum Unchecked {}
mod sealed {
pub trait Sealed {}
impl Sealed for super::Checked {}
impl Sealed for super::Unchecked {}
}
impl BlockState for Checked {
const CHECKED: bool = true;
}
impl BlockState for Unchecked {
const CHECKED: bool = false;
}
#[derive(Clone, Copy, Debug)]
pub struct ArdBlocks<'a, T, S = Checked> {
blocks: BlockList<'a, T>,
rows: usize,
cols: usize,
col0: usize,
ld: usize,
slot: Option<usize>,
state: PhantomData<S>,
}
#[derive(Clone, Copy, Debug)]
pub(crate) enum BlockList<'a, T> {
Slices(&'a [&'a [T]]),
Vecs(&'a [Vec<T>]),
Packed(&'a [T], usize, usize),
Repeat(&'a [T], usize),
Triangles(ArdSqDiff<'a, T>),
}
impl<'a, T: KernelScalar, S: BlockState> ArdBlocks<'a, T, S> {
pub(crate) fn new(blocks: BlockList<'a, T>, rows: usize, cols: usize, col0: usize) -> Self {
Self::strided(blocks, rows, cols, col0, rows)
}
pub(crate) fn strided(
blocks: BlockList<'a, T>,
rows: usize,
cols: usize,
col0: usize,
ld: usize,
) -> Self {
Self {
blocks,
rows,
cols,
col0,
ld,
slot: None,
state: PhantomData,
}
}
pub(crate) fn of_slot(self, place: usize) -> Self {
Self {
slot: Some(place),
..self
}
}
pub(crate) fn locate(&self, err: GprError) -> GprError {
match self.slot {
Some(place) => err.in_slot(place),
None => err,
}
}
pub(crate) fn subcols(self, start: usize, len: usize) -> Self {
Self {
cols: len,
col0: self.col0 + start,
..self
}
}
pub(crate) fn d(&self) -> usize {
match self.blocks {
BlockList::Slices(blocks) => blocks.len(),
BlockList::Vecs(blocks) => blocks.len(),
BlockList::Packed(_, _, dims) | BlockList::Repeat(_, dims) => dims,
BlockList::Triangles(cache) => cache.d(),
}
}
pub(crate) fn rows(&self) -> usize {
self.rows
}
pub(crate) fn cols(&self) -> usize {
self.cols
}
fn raw_block(&self, dim: usize) -> &'a [T] {
match self.blocks {
BlockList::Slices(blocks) => blocks[dim],
BlockList::Vecs(blocks) => &blocks[dim],
BlockList::Packed(all, len, _) => &all[dim * len..(dim + 1) * len],
BlockList::Repeat(block, _) => block,
BlockList::Triangles(_) => &[],
}
}
fn raw_get(&self, dim: usize, row: usize, col: usize) -> T {
match self.blocks {
BlockList::Triangles(cache) => cache.get(dim, row, col + self.col0),
_ => self.raw_block(dim)[row + (col + self.col0) * self.ld],
}
}
#[inline]
pub(crate) fn read(&self, dim: usize, row: usize, col: usize) -> Result<T, GprError> {
let v = self.raw_get(dim, row, col);
if S::CHECKED || super::sources::valid(v.to_f64()) {
Ok(v)
} else {
let err = super::sources::invalid_value(v.to_f64(), row, col + self.col0);
Err(self.locate(err.in_dim(dim)))
}
}
pub(crate) fn column(&self, dim: usize, col: usize) -> Result<Option<&'a [f64]>, GprError> {
let Some(run) = self.f64_column(dim, col) else {
return Ok(None);
};
if !S::CHECKED && !super::simd::all_valid_distances(run) {
let err = super::sources::first_invalid_from(run, self.rows, self.col0 + col);
return Err(self.locate(err.in_dim(dim)));
}
Ok(Some(run))
}
pub(crate) fn dense_f64(&self) -> bool {
let end = match self.cols {
0 => 0,
cols => (self.col0 + cols - 1) * self.ld + self.rows,
};
!matches!(self.blocks, BlockList::Triangles(_))
&& T::as_f64_slice(&[]).is_some()
&& (0..self.d()).all(|dim| self.raw_block(dim).len() >= end)
}
fn f64_column(&self, dim: usize, col: usize) -> Option<&'a [f64]> {
if matches!(self.blocks, BlockList::Triangles(_)) {
return None;
}
let start = (self.col0 + col) * self.ld;
T::as_f64_slice(self.raw_block(dim).get(start..start + self.rows)?)
}
pub(crate) fn gates(&self) -> Option<Gates<'a, S>> {
let d = self.d();
if d > GATE_DIMS || !self.dense_f64() {
return None;
}
let mut blocks: [&'a [f64]; GATE_DIMS] = [&[]; GATE_DIMS];
for (dim, block) in blocks.iter_mut().enumerate().take(d) {
*block = T::as_f64_slice(self.raw_block(dim))?;
}
Some(Gates {
blocks,
d,
rows: self.rows,
col0: self.col0,
ld: self.ld,
state: PhantomData,
})
}
}
impl<'a, T: KernelScalar> ArdBlocks<'a, T, Checked> {
pub(crate) fn block(&self, dim: usize) -> &'a [T] {
self.raw_block(dim)
}
}
#[derive(Clone, Copy)]
pub(crate) struct Gates<'a, S> {
blocks: [&'a [f64]; GATE_DIMS],
d: usize,
rows: usize,
col0: usize,
ld: usize,
state: PhantomData<S>,
}
impl<'a, S: BlockState> Gates<'a, S> {
#[inline]
pub(crate) fn gate(&self, col: usize) -> Gate<'a, S> {
let start = (self.col0 + col) * self.ld;
let mut runs: [&'a [f64]; GATE_DIMS] = [&[]; GATE_DIMS];
for (run, block) in runs.iter_mut().zip(&self.blocks[..self.d]) {
*run = &block[start..start + self.rows];
}
Gate {
runs,
d: self.d,
nonfinite: f64x4::ZERO,
least: f64x4::ZERO,
rows: self.rows,
col: self.col0 + col,
state: PhantomData,
}
}
}
pub(crate) const GATE_DIMS: usize = 16;
#[must_use = "a gate's sums are valid only once its verdict is Ok"]
pub(crate) struct Gate<'a, S> {
runs: [&'a [f64]; GATE_DIMS],
d: usize,
nonfinite: f64x4,
least: f64x4,
rows: usize,
col: usize,
state: PhantomData<S>,
}
impl<S: BlockState> Gate<'_, S> {
#[inline(always)]
pub(crate) fn weighted4(&mut self, w: &[f64], i: usize) -> f64x4 {
let mut r2 = f64x4::ZERO;
for (run, &wd) in self.runs[..self.d].iter().zip(w) {
let v = super::simd::load4(run, i);
if !S::CHECKED {
self.nonfinite += v * f64x4::ZERO;
self.least = self.least.fast_min(v);
}
r2 += v * f64x4::splat(wd);
}
r2
}
#[inline(always)]
pub(crate) fn weighted1(&mut self, w: &[f64], i: usize) -> f64 {
let mut r2 = 0.0;
for (run, &wd) in self.runs[..self.d].iter().zip(w) {
let v = run[i];
if !S::CHECKED {
self.nonfinite += f64x4::splat(v * 0.0);
self.least = self.least.fast_min(f64x4::splat(v));
}
r2 += v * wd;
}
r2
}
pub(crate) fn verdict(self) -> Result<(), GprError> {
if S::CHECKED {
return Ok(());
}
let valid =
self.nonfinite.reduce_add() == 0.0 && self.least.to_array().iter().all(|&l| l >= 0.0);
if valid {
return Ok(());
}
for (dim, run) in self.runs[..self.d].iter().enumerate() {
if !super::simd::all_valid_distances(run) {
let err = super::sources::first_invalid_from(run, self.rows, self.col);
return Err(err.in_dim(dim));
}
}
Err(super::sources::unlocated())
}
}
pub(crate) fn fill_ard_squared_diff(x: MatRef<'_, f64>, cache: &mut [f64]) {
let n = x.nrows();
let d = x.ncols();
if n == 0 || d == 0 {
return;
}
debug_assert_eq!(cache.len(), d * n * (n + 1) / 2);
let mut columns: Vec<(usize, usize, &mut [f64])> = Vec::with_capacity(n * d);
let mut rest = cache;
for dim in 0..d {
for col in 0..n {
let (head, tail) = rest.split_at_mut(n - col);
columns.push((dim, col, head));
rest = tail;
}
}
columns.into_par_iter().for_each(|(dim, col, dest)| {
if !try_fill_ard_column(x, dim, col, dest) {
for (offset, slot) in dest.iter_mut().enumerate() {
let diff = x[(col + offset, dim)] - x[(col, dim)];
*slot = diff * diff;
}
}
});
}
pub(crate) fn require_ard_sq_diff_shape<T: KernelScalar>(
cache: ArdSqDiff<'_, T>,
n: usize,
d: usize,
) -> Result<(), GprError> {
if cache.n() == n && cache.d() == d {
Ok(())
} else {
Err(GprError::ShapeMismatch {
reason: format!(
"ARD cache holds {} points in {} dimensions, expected {n} in {d}",
cache.n(),
cache.d()
),
})
}
}
pub(crate) fn fill_squared_euclidean_cross(
x_train: MatRef<'_, f64>,
x_test: MatRef<'_, f64>,
mut dist: MatMut<'_, f64>,
thread_scratch: &mut [Mat<f64>],
) {
let m = x_test.nrows();
if x_train.nrows() == 0 || m == 0 {
return;
}
if m == 1 {
fill_cross_chunk(x_train, x_test, dist.rb_mut(), 0);
return;
}
let n_parts = partition_count(thread_scratch);
dist.rb_mut()
.par_col_partition_mut(n_parts)
.enumerate()
.for_each(|(chunk_idx, part)| {
let (start, _) = col_chunk(m, chunk_idx, n_parts);
fill_cross_chunk(x_train, x_test, part, start);
});
}
fn fill_lower_col(x: MatRef<'_, f64>, col: usize, mut rows: ColMut<'_, f64>) {
if let Some(dest) = rows.rb_mut().try_as_col_major_mut()
&& try_fill_lower_col(x, col, dest.as_slice_mut())
{
return;
}
for (i, row) in (col..x.nrows()).enumerate() {
let mut sum = 0.0;
for dim in 0..x.ncols() {
let diff = x[(row, dim)] - x[(col, dim)];
sum += diff * diff;
}
rows[i] = sum;
}
}
fn fill_cross_chunk(
x_train: MatRef<'_, f64>,
x_test: MatRef<'_, f64>,
mut dist_chunk: MatMut<'_, f64>,
start: usize,
) {
if try_fill_cross_chunk(x_train, x_test, dist_chunk.rb_mut(), start) {
return;
}
for local in 0..dist_chunk.ncols() {
let col = start + local;
for row in 0..x_train.nrows() {
let mut sum = 0.0;
for dim in 0..x_train.ncols() {
let diff = x_train[(row, dim)] - x_test[(col, dim)];
sum += diff * diff;
}
dist_chunk[(row, local)] = sum;
}
}
}
fn copy_lower_to_upper(mut dist: MatMut<'_, f64>) {
let n = dist.nrows();
for col in 1..n {
for row in 0..col {
dist[(row, col)] = dist[(col, row)];
}
}
}
pub(crate) fn fill_squared_scalar(x: MatRef<'_, f32>, mut dist: MatMut<'_, f32>) {
let n = x.nrows();
let d = x.ncols();
for col in 0..n {
for row in 0..n {
let mut sum = 0.0f32;
for dim in 0..d {
let diff = x[(row, dim)] - x[(col, dim)];
sum += diff * diff;
}
dist[(row, col)] = sum;
}
}
}
pub(crate) fn fill_cross_scalar(
x_train: MatRef<'_, f32>,
x_test: MatRef<'_, f32>,
mut dist: MatMut<'_, f32>,
) {
let n = x_train.nrows();
let m = x_test.nrows();
let d = x_train.ncols();
for col in 0..m {
for row in 0..n {
let mut sum = 0.0f32;
for dim in 0..d {
let diff = x_train[(row, dim)] - x_test[(col, dim)];
sum += diff * diff;
}
dist[(row, col)] = sum;
}
}
}
pub(crate) fn fill_ard_scalar(x: MatRef<'_, f32>, cache: &mut [f32]) {
let n = x.nrows();
let mut slots = cache.iter_mut();
for dim in 0..x.ncols() {
for col in 0..n {
for row in col..n {
let diff = x[(row, dim)] - x[(col, dim)];
if let Some(slot) = slots.next() {
*slot = diff * diff;
}
}
}
}
}
#[cfg(test)]
mod tests {
use super::{
ArdSqDiffBuf, col_chunk, fill_squared_euclidean, fill_squared_euclidean_cross,
par_lower_fold, worker_count,
};
use faer::Mat;
fn sequential_sq(x: faer::MatRef<'_, f64>) -> Mat<f64> {
let n = x.nrows();
let d = x.ncols();
let mut dist = Mat::zeros(n, n);
for col in 0..n {
for row in col..n {
let mut sum = 0.0;
for dim in 0..d {
let diff = x[(row, dim)] - x[(col, dim)];
sum += diff * diff;
}
dist[(row, col)] = sum;
dist[(col, row)] = sum;
}
}
dist
}
#[test]
fn col_chunks_cover_n() {
for n in [1, 2, 5, 7, 256] {
for chunks in [1, 2, 3, 4, 8, worker_count()] {
let chunks = chunks.max(1);
let mut covered = 0;
for idx in 0..chunks {
let (_start, len) = col_chunk(n, idx, chunks);
covered += len;
}
assert_eq!(covered, n, "n={n} chunks={chunks}");
}
}
}
#[test]
fn lower_blocks_cover_every_column_once_with_balanced_area() {
for n in [0, 1, 2, 3, 7, 64, 550, 1001] {
for blocks in [1, 2, 3, 4, 8, 16, 37] {
let starts: Vec<usize> = (0..=blocks)
.map(|i| super::lower_block_start(n, i, blocks))
.collect();
assert_eq!(starts[0], 0);
assert_eq!(starts[blocks], n);
assert!(
starts.windows(2).all(|w| w[0] <= w[1]),
"n={n} blocks={blocks}"
);
let areas: Vec<u128> = starts
.windows(2)
.map(|w| super::lower_area(n, w[1]) - super::lower_area(n, w[0]))
.collect();
let (k, total) = (blocks as u128, super::lower_area(n, n));
for area in &areas {
assert!(
(area * k).abs_diff(total) <= n as u128 * k,
"n={n} blocks={blocks} areas={areas:?}"
);
}
}
}
}
#[test]
fn par_lower_blocks_hands_every_column_to_one_block() {
for n in [1, 5, 9, 130] {
for blocks in [1, 3, 4, 16] {
let mut out = Mat::<f64>::zeros(n, n);
super::par_lower_blocks(out.as_mut(), blocks, &|start,
mut part: faer::MatMut<
'_,
f64,
>| {
for local in 0..part.ncols() {
for row in start + local..n {
part[(row, local)] += (start + local) as f64 + 1.0;
}
}
Ok::<(), std::convert::Infallible>(())
})
.expect("infallible");
for col in 0..n {
for row in 0..n {
let want = if row >= col { col as f64 + 1.0 } else { 0.0 };
assert_eq!(out[(row, col)].to_bits(), want.to_bits());
}
}
}
}
}
#[test]
fn par_lower_fold_matches_a_serial_column_sum() {
fn term(col: usize) -> f64 {
if col.is_multiple_of(2) {
1.0e16
} else {
-1.0e16 + col as f64
}
}
for n in [0, 1, 2, 15, 16, 17, 64, 256] {
let got = par_lower_fold(
n,
&|start, end| {
let mut sum = 0.0;
for col in start..end {
sum += term(col);
}
Ok::<f64, std::convert::Infallible>(sum)
},
&|a, b| a + b,
)
.expect("infallible");
let mut expect = 0.0;
for col in 0..n {
expect += term(col);
}
assert_eq!(got.to_bits(), expect.to_bits(), "n={n}");
}
}
#[test]
fn col_chunk_five_by_four_covers_remainder() {
assert_eq!(col_chunk(5, 0, 4), (0, 2));
assert_eq!(col_chunk(5, 1, 4), (2, 1));
assert_eq!(col_chunk(5, 2, 4), (3, 1));
assert_eq!(col_chunk(5, 3, 4), (4, 1));
let covered: usize = (0..4).map(|idx| col_chunk(5, idx, 4).1).sum();
assert_eq!(covered, 5);
}
#[test]
fn fill_when_more_chunks_than_columns_matches_sequential() {
let x = Mat::from_fn(5, 3, |r, c| (r as f64) * 0.1 + (c as f64) * 0.3);
let expected = sequential_sq(x.as_ref());
let mut dist = Mat::zeros(5, 5);
let mut scratches = vec![Mat::<f64>::zeros(0, 0); 8];
fill_squared_euclidean(x.as_ref(), dist.as_mut(), &mut scratches);
for col in 0..5 {
for row in 0..5 {
assert!((dist[(row, col)] - expected[(row, col)]).abs() <= 1e-15);
}
}
}
#[test]
fn parallel_fill_matches_sequential() {
let x = Mat::from_fn(5, 3, |r, c| (r as f64) * 0.1 + (c as f64) * 0.3);
let expected = sequential_sq(x.as_ref());
let mut dist = Mat::zeros(5, 5);
let mut scratches = vec![Mat::<f64>::zeros(0, 0); worker_count()];
fill_squared_euclidean(x.as_ref(), dist.as_mut(), &mut scratches);
for col in 0..5 {
for row in 0..5 {
assert!((dist[(row, col)] - expected[(row, col)]).abs() <= 1e-15);
}
}
}
#[test]
fn parallel_cross_matches_sequential() {
let x = Mat::from_fn(4, 2, |r, c| r as f64 + c as f64);
let xs = Mat::from_fn(3, 2, |r, c| (r as f64) * 0.5 + c as f64);
let mut expected = Mat::zeros(4, 3);
for col in 0..3 {
for row in 0..4 {
let mut sum = 0.0;
for dim in 0..2 {
let diff = x[(row, dim)] - xs[(col, dim)];
sum += diff * diff;
}
expected[(row, col)] = sum;
}
}
let mut dist = Mat::zeros(4, 3);
fill_squared_euclidean_cross(x.as_ref(), xs.as_ref(), dist.as_mut(), &mut []);
for col in 0..3 {
for row in 0..4 {
assert!((dist[(row, col)] - expected[(row, col)]).abs() <= 1e-15);
}
}
}
#[test]
fn ard_fill_matches_per_dim_squared_diff() {
let x = Mat::from_fn(5, 3, |r, c| {
(r as f64) * 0.1 + (c as f64) * 0.3 + (r * c) as f64
});
let n = 5;
let d = 3;
let cache = ArdSqDiffBuf::new(x.as_ref()).expect("size");
let view = cache.view();
assert_eq!((view.n(), view.d()), (n, d));
assert_eq!(cache.stored_len(), d * n * (n + 1) / 2);
for dim in 0..d {
for col in 0..n {
assert_eq!(view.lower().expect("lower").column(dim, col).len(), n - col);
for row in 0..n {
let diff = x[(row, dim)] - x[(col, dim)];
assert!((view.get(dim, row, col) - diff * diff).abs() <= 1e-15);
}
}
}
let x32 = Mat::from_fn(5, 3, |r, c| x[(r, c)] as f32);
let cache32 = ArdSqDiffBuf::new(x32.as_ref()).expect("size");
for dim in 0..d {
for col in 0..n {
for row in 0..n {
let diff = x32[(row, dim)] - x32[(col, dim)];
assert!((cache32.view().get(dim, row, col) - diff * diff).abs() <= 1e-6);
}
}
}
}
fn pool_pair(k: usize, a: usize, b: usize) -> f64 {
let at = |p: usize| (p as f64 * (0.41 + 0.17 * k as f64)).sin() * (1.0 + k as f64);
let diff = at(a) - at(b);
diff * diff
}
fn assert_holds(cache: &ArdSqDiffBuf<f64>, live: &[usize], d: usize) {
let view = cache.view();
assert_eq!((view.n(), view.d()), (live.len(), d));
for k in 0..d {
for (i, &a) in live.iter().enumerate() {
for (j, &b) in live.iter().enumerate() {
assert_eq!(
view.get(k, i, j).to_bits(),
pool_pair(k, a, b).to_bits(),
"{k} ({i}, {j})"
);
}
}
}
}
#[test]
fn row_runs_grow_and_shrink_in_place() {
let d = 3;
let start: Vec<usize> = (0..5).collect();
let packed = ArdSqDiffBuf::<f64>::from_pairs(5, d, pool_pair).expect("cache");
let tables: Vec<Vec<f64>> = (0..d)
.map(|k| (0..25).map(|at| pool_pair(k, at % 5, at / 5)).collect())
.collect();
let dense = ArdSqDiffBuf::<f64>::from_tables(tables, 5);
for mut cache in [packed, dense] {
let mut live = start.clone();
assert_holds(&cache, &live, d);
let mut next = 5;
for step in 0..12 {
if step % 3 == 2 {
let index = [0, live.len() / 2, live.len() - 1][step % 9 / 3];
cache.ready_to_change().expect("rows");
assert!(cache.can_remove());
cache.remove_point(index);
live.remove(index);
} else {
cache.reserve_point().expect("room");
let columns: Vec<Vec<f64>> = (0..d)
.map(|k| live.iter().map(|&a| pool_pair(k, a, next)).collect())
.collect();
assert!(cache.can_push());
cache.push_point(|k| &columns[k]);
live.push(next);
next += 1;
}
assert!(cache.view().rows().is_some());
assert_holds(&cache, &live, d);
}
}
}
#[test]
fn row_runs_report_their_room_and_clone_it() {
let mut cache = ArdSqDiffBuf::<f64>::from_pairs(4, 2, pool_pair).expect("cache");
assert!(!cache.can_push());
assert!(!cache.can_remove());
cache.reserve_point().expect("room");
assert!(cache.can_push() && cache.can_remove());
let mut copy = cache.clone();
let columns: Vec<Vec<f64>> = (0..2)
.map(|k| (0..4).map(|a| pool_pair(k, a, 4)).collect())
.collect();
assert!(copy.can_push(), "the clone has room");
copy.push_point(|k| &columns[k]);
assert_holds(©, &[0, 1, 2, 3, 4], 2);
assert_holds(&cache, &[0, 1, 2, 3], 2);
let cast = copy.map(|v| v as f32);
assert!(cast.view().rows().is_some());
assert_eq!(
cast.view().get(1, 4, 2).to_bits(),
(pool_pair(1, 4, 2) as f32).to_bits()
);
assert_eq!(
copy.view()
.position(1, |v| v.to_bits() == pool_pair(1, 4, 2).to_bits()),
Some((4, 2))
);
}
}