use crate::{domain::Aggregate, error::BenchguardError};
pub fn aggregate(samples: &[u64]) -> Result<Aggregate, BenchguardError> {
if samples.is_empty() {
return Err(BenchguardError::EmptySamples);
}
let sample_count =
u32::try_from(samples.len()).map_err(|_| BenchguardError::NumericOverflow)?;
let count = u128::try_from(samples.len()).map_err(|_| BenchguardError::NumericOverflow)?;
let sum = samples.iter().try_fold(0_u128, |sum, &sample| {
sum.checked_add(u128::from(sample))
.ok_or(BenchguardError::NumericOverflow)
})?;
let mean_u128 = sum / count;
let mean = u64::try_from(mean_u128).map_err(|_| BenchguardError::NumericOverflow)?;
let squared_scaled_deviations = samples.iter().try_fold(0_u128, |accumulator, &sample| {
let scaled_sample = u128::from(sample)
.checked_mul(count)
.ok_or(BenchguardError::NumericOverflow)?;
let deviation = scaled_sample.abs_diff(sum);
let squared_deviation = deviation
.checked_mul(deviation)
.ok_or(BenchguardError::NumericOverflow)?;
accumulator
.checked_add(squared_deviation)
.ok_or(BenchguardError::NumericOverflow)
})?;
let variance = squared_scaled_deviations / count / count / count;
let standard_deviation = integer_square_root(variance);
let mut sorted = samples.to_vec();
sorted.sort_unstable();
let middle = sorted.len() / 2;
let median = if sorted.len() % 2 == 0 {
let lower = u128::from(sorted[middle - 1]);
let upper = u128::from(sorted[middle]);
u64::try_from((lower + upper) / 2).map_err(|_| BenchguardError::NumericOverflow)?
} else {
sorted[middle]
};
Ok(Aggregate {
median,
mean,
standard_deviation,
min: sorted[0],
max: sorted[sorted.len() - 1],
p50: nearest_rank(&sorted, 50),
p95: nearest_rank(&sorted, 95),
sample_count,
})
}
pub fn coefficient_of_variation_pct(samples: &[u64]) -> Result<f64, BenchguardError> {
let moments = exact_cv_moments(samples)?;
if moments.sum.is_zero() {
return Ok(0.0);
}
Ok(moments.dispersion.to_f64().sqrt() / moments.sum.to_f64() * 100.0)
}
pub(crate) fn coefficient_of_variation_exceeds_ten_percent(
samples: &[u64],
) -> Result<bool, BenchguardError> {
let moments = exact_cv_moments(samples)?;
if moments.sum.is_zero() {
return Ok(false);
}
Ok(moments.dispersion.checked_mul(WideUint::from_u64(100))? > moments.sum_squared)
}
fn exact_cv_moments(samples: &[u64]) -> Result<ExactCvMoments, BenchguardError> {
if samples.is_empty() {
return Err(BenchguardError::EmptySamples);
}
let count = u64::try_from(samples.len()).map_err(|_| BenchguardError::NumericOverflow)?;
let mut sum = WideUint::ZERO;
let mut sum_of_squares = WideUint::ZERO;
for &sample in samples {
sum = sum.checked_add(WideUint::from_u64(sample))?;
let square = u128::from(sample) * u128::from(sample);
sum_of_squares = sum_of_squares.checked_add(WideUint::from_u128(square))?;
}
let sum_squared = sum.checked_mul(sum)?;
let dispersion = sum_of_squares
.checked_mul(WideUint::from_u64(count))?
.checked_sub(sum_squared)?;
Ok(ExactCvMoments {
sum,
sum_squared,
dispersion,
})
}
struct ExactCvMoments {
sum: WideUint,
sum_squared: WideUint,
dispersion: WideUint,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct WideUint([u64; 5]);
impl WideUint {
const ZERO: Self = Self([0; 5]);
fn from_u64(value: u64) -> Self {
Self([value, 0, 0, 0, 0])
}
fn from_u128(value: u128) -> Self {
Self([value as u64, (value >> 64) as u64, 0, 0, 0])
}
fn is_zero(self) -> bool {
self == Self::ZERO
}
fn checked_add(self, other: Self) -> Result<Self, BenchguardError> {
let mut result = [0; 5];
let mut carry = 0_u128;
for (index, output) in result.iter_mut().enumerate() {
let total = u128::from(self.0[index]) + u128::from(other.0[index]) + carry;
*output = total as u64;
carry = total >> 64;
}
if carry == 0 {
Ok(Self(result))
} else {
Err(BenchguardError::NumericOverflow)
}
}
fn checked_sub(self, other: Self) -> Result<Self, BenchguardError> {
let mut result = [0; 5];
let mut borrow = false;
for (index, output) in result.iter_mut().enumerate() {
let (difference, first_borrow) = self.0[index].overflowing_sub(other.0[index]);
let (difference, second_borrow) = difference.overflowing_sub(u64::from(borrow));
*output = difference;
borrow = first_borrow || second_borrow;
}
if borrow {
Err(BenchguardError::NumericOverflow)
} else {
Ok(Self(result))
}
}
fn checked_mul(self, other: Self) -> Result<Self, BenchguardError> {
let mut result = [0_u64; 5];
for left_index in 0..5 {
if self.0[left_index] != 0 && other.0[(5 - left_index)..].iter().any(|&limb| limb != 0)
{
return Err(BenchguardError::NumericOverflow);
}
let mut carry = 0_u128;
for right_index in 0..(5 - left_index) {
let output_index = left_index + right_index;
let total = u128::from(self.0[left_index]) * u128::from(other.0[right_index])
+ u128::from(result[output_index])
+ carry;
result[output_index] = total as u64;
carry = total >> 64;
}
if carry != 0 {
return Err(BenchguardError::NumericOverflow);
}
}
Ok(Self(result))
}
fn to_f64(self) -> f64 {
const LIMB_SCALE: f64 = 18_446_744_073_709_551_616.0;
self.0
.iter()
.rev()
.fold(0.0, |value, &limb| value * LIMB_SCALE + limb as f64)
}
}
impl Ord for WideUint {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
self.0.iter().rev().cmp(other.0.iter().rev())
}
}
impl PartialOrd for WideUint {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
fn nearest_rank(sorted: &[u64], percentile: u128) -> u64 {
let count = u128::try_from(sorted.len()).expect("slice length always fits in u128");
let rank = (percentile * count).div_ceil(100);
let index = usize::try_from(rank - 1).expect("rank is derived from the slice length");
sorted[index]
}
fn integer_square_root(value: u128) -> u64 {
let mut lower = 0_u128;
let mut upper = u128::from(u64::MAX);
while lower < upper {
let middle = lower + (upper - lower).div_ceil(2);
if middle <= value / middle {
lower = middle;
} else {
upper = middle - 1;
}
}
u64::try_from(lower).expect("square root is bounded by u64::MAX")
}
#[cfg(test)]
mod tests {
use super::*;
use crate::error::BenchguardError;
#[test]
fn aggregates_unsorted_integer_samples() {
let result = aggregate(&[30, 10, 20, 40]).unwrap();
assert_eq!(result.median, 25);
assert_eq!(result.mean, 25);
assert_eq!(result.standard_deviation, 11);
assert_eq!(result.min, 10);
assert_eq!(result.max, 40);
assert_eq!(result.p50, 20);
assert_eq!(result.p95, 40);
assert_eq!(result.sample_count, 4);
}
#[test]
fn uses_the_true_population_mean_for_non_integral_means() {
let result = aggregate(&[0, 0, 2]).unwrap();
assert_eq!(result.mean, 0);
assert_eq!(result.standard_deviation, 0);
}
#[test]
fn rejects_empty_samples() {
assert!(matches!(aggregate(&[]), Err(BenchguardError::EmptySamples)));
}
#[test]
fn coefficient_of_variation_uses_true_population_math_at_ten_percent() {
assert_eq!(coefficient_of_variation_pct(&[90, 110]).unwrap(), 10.0);
assert!(coefficient_of_variation_pct(&[89, 111]).unwrap() > 10.0);
}
#[test]
fn coefficient_of_variation_handles_zero_mean_and_empty_samples() {
assert_eq!(coefficient_of_variation_pct(&[0, 0, 0]).unwrap(), 0.0);
assert!(matches!(
coefficient_of_variation_pct(&[]),
Err(BenchguardError::EmptySamples)
));
}
#[test]
fn coefficient_of_variation_preserves_adjacent_large_integer_distinctions() {
let coefficient = coefficient_of_variation_pct(&[u64::MAX - 1, u64::MAX]).unwrap();
assert!(
coefficient > 0.0,
"adjacent integer samples became identical"
);
}
#[test]
fn wide_multiplication_rejects_discarded_high_limb_products() {
let highest_limb = WideUint([0, 0, 0, 0, 1]);
let one_limb_shift = WideUint([0, 1, 0, 0, 0]);
assert!(matches!(
highest_limb.checked_mul(one_limb_shift),
Err(BenchguardError::NumericOverflow)
));
}
}