use num_complex::Complex64;
use super::tests::Sample;
use super::{RunIndex, RunSumPlan};
#[cfg(feature = "parallel")]
use crate::cost::{tree_width, KernelClass};
use crate::threading::test_pool;
use crate::{Exec, RawStridedMut, RawStridedRef};
const PAYLOAD: usize = 8;
const HUB: i32 = 400;
fn topology() -> (Vec<i32>, usize) {
let mut dest_of_row = Vec::new();
for run in 0..400usize {
let degree = 1 + (run * 37) % 97;
for _ in 0..degree {
dest_of_row.push(run as i32);
}
}
let rows = dest_of_row.len();
dest_of_row.extend(std::iter::repeat_n(HUB, rows / 2));
let runs = 401;
let shift = 1234 % dest_of_row.len();
dest_of_row.rotate_left(shift);
(dest_of_row, runs)
}
fn assert_same_bits<T: Sample>(reference: &[T], other: &[T], context: &str) {
assert_eq!(reference.len(), other.len(), "{context}: length");
for (slot, (&want, &got)) in reference.iter().zip(other.iter()).enumerate() {
assert!(
got.bits_eq(want),
"{context}: slot {slot}: {want:?} vs {got:?}"
);
}
}
fn run_with_budget<T: Sample>(budget: usize) -> Vec<T> {
let (dest_of_row, runs_count) = topology();
let rows = dest_of_row.len();
let src_dims = [rows, PAYLOAD];
let dest_dims = [runs_count, PAYLOAD];
let strides = [PAYLOAD as isize, 1];
let src: Vec<T> = (0..rows * PAYLOAD).map(T::from_index).collect();
let src_ref = RawStridedRef::new(&src, &src_dims, &strides, 0).unwrap();
let runs = RunIndex::from_dest(&dest_of_row, runs_count).unwrap();
let plan = RunSumPlan::compile(&src_dims, &strides, &dest_dims, &strides, &runs).unwrap();
assert_eq!(runs.ptr().len() - 1, runs_count);
let mut out = vec![T::zero(); runs_count * PAYLOAD];
let mut dest = RawStridedMut::new(&mut out, &dest_dims, &strides, 0).unwrap();
let pool = test_pool(budget);
let exec = Exec::new(&pool, budget).unwrap();
#[cfg(feature = "parallel")]
if budget > 1 {
let elements = rows * PAYLOAD;
assert_eq!(
tree_width(&exec, KernelClass::Reduce, elements).get(),
budget,
"the gate has to open for the split to exist"
);
}
plan.execute_into(&mut dest, &src_ref, &runs, exec).unwrap();
out
}
fn budgets_agree<T: Sample>() {
let reference = run_with_budget::<T>(1);
for budget in [2usize, 4, 8] {
let other = run_with_budget::<T>(budget);
assert_same_bits(&reference, &other, &format!("budget {budget}"));
}
}
#[test]
fn budgets_one_two_four_eight_agree_bit_for_bit() {
budgets_agree::<f64>();
budgets_agree::<f32>();
budgets_agree::<Complex64>();
}
#[test]
fn regrouping_the_hub_would_move_the_bits() {
let (dest_of_row, _) = topology();
let rows = dest_of_row.len();
let hub: Vec<usize> = (0..rows)
.filter(|&row| dest_of_row[row] == HUB)
.map(|row| row * PAYLOAD)
.collect();
assert!(hub.len() > 64, "the hub run must be long enough");
let regrouped = |sum: &dyn Fn(&[usize]) -> f64| -> (u64, u64) {
let split = hub.len() / 2;
let whole = sum(&hub);
let halves = sum(&hub[..split]) + sum(&hub[split..]);
(whole.to_bits(), halves.to_bits())
};
let in_order = |indices: &[usize]| -> f64 {
indices.iter().fold(0.0f64, |acc, &index| {
acc + <f64 as Sample>::from_index(index)
})
};
let (whole, halves) = regrouped(&in_order);
assert_ne!(
whole, halves,
"the hub's rows must not sum to the same bits when regrouped"
);
}
#[test]
fn acc_matches_into_at_every_budget_from_a_zero_seed() {
fn check<T: Sample>() {
let (dest_of_row, runs_count) = topology();
let rows = dest_of_row.len();
let src_dims = [rows, 4];
let dest_dims = [runs_count, 4];
let strides = [4isize, 1];
let src: Vec<T> = (0..rows * 4).map(T::from_index).collect();
let src_ref = RawStridedRef::new(&src, &src_dims, &strides, 0).unwrap();
let runs = RunIndex::from_dest(&dest_of_row, runs_count).unwrap();
let plan = RunSumPlan::compile(&src_dims, &strides, &dest_dims, &strides, &runs).unwrap();
for budget in [1usize, 2, 4, 8] {
let mut into = vec![T::zero(); runs_count * 4];
let pool = test_pool(budget);
let exec = Exec::new(&pool, budget).unwrap();
let mut dest = RawStridedMut::new(&mut into, &dest_dims, &strides, 0).unwrap();
plan.execute_into(&mut dest, &src_ref, &runs, exec).unwrap();
let mut acc = vec![T::zero(); runs_count * 4];
let pool = test_pool(budget);
let exec = Exec::new(&pool, budget).unwrap();
let mut dest = RawStridedMut::new(&mut acc, &dest_dims, &strides, 0).unwrap();
plan.execute_acc(&mut dest, &src_ref, &runs, exec).unwrap();
assert_same_bits(&into, &acc, &format!("budget {budget}"));
}
}
check::<f64>();
check::<f32>();
check::<Complex64>();
}