use std::alloc::{GlobalAlloc, Layout, System};
use std::fs::OpenOptions;
use std::io::Write;
use std::sync::atomic::{AtomicUsize, Ordering};
use std::time::Instant;
pub static ALLOCATIONS: AtomicUsize = AtomicUsize::new(0);
pub struct CountingAllocator;
unsafe impl GlobalAlloc for CountingAllocator {
unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
ALLOCATIONS.fetch_add(1, Ordering::Relaxed);
System.alloc(layout)
}
unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
System.dealloc(ptr, layout);
}
unsafe fn realloc(&self, ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8 {
ALLOCATIONS.fetch_add(1, Ordering::Relaxed);
System.realloc(ptr, layout, new_size)
}
}
pub const REPS: usize = 9;
pub const ATTEMPTS: usize = 3;
pub const MAD_TO_SIGMA: f64 = 1.4826;
pub const SIGMA_MULTIPLE: f64 = 3.0;
pub const PARITY_ANCHOR: f64 = 1.0;
pub const GATE_FLOOR_FRACTION: f64 = 0.15;
pub const ALLOC_ITERS: usize = 64;
#[allow(dead_code)] #[derive(Clone, Copy)]
pub enum Gate {
Parity,
Bound(f64),
ReportGated,
Report,
}
pub fn time_once(iterations: usize, body: &mut impl FnMut()) -> f64 {
let start = Instant::now();
for _ in 0..iterations {
body();
}
start.elapsed().as_secs_f64() * 1e9 / iterations as f64
}
pub fn allocations_per_op(body: &mut impl FnMut()) -> f64 {
let before = ALLOCATIONS.load(Ordering::Relaxed);
for _ in 0..ALLOC_ITERS {
body();
}
let after = ALLOCATIONS.load(Ordering::Relaxed);
(after - before) as f64 / ALLOC_ITERS as f64
}
fn parity_width(median: f64, mad: f64) -> f64 {
(MAD_TO_SIGMA * mad).max(GATE_FLOOR_FRACTION * median)
}
fn parity_bound(median: f64, mad: f64) -> f64 {
PARITY_ANCHOR + SIGMA_MULTIPLE * parity_width(median, mad)
}
fn percentile_sorted(sorted: &[f64], q: f64) -> f64 {
debug_assert!(!sorted.is_empty());
let last = sorted.len() - 1;
let rank = (q * last as f64).round() as usize;
sorted[rank.min(last)]
}
pub struct CaseResult {
id: &'static str,
description: &'static str,
a_med: f64,
a_p95: f64,
b_med: f64,
b_p95: f64,
ratio: f64,
spread: Option<f64>,
mad: f64,
a_allocs: f64,
b_allocs: f64,
gate: Gate,
tolerance: Option<f64>,
attempts_exceeded: usize,
}
impl CaseResult {
fn gate_value(&self) -> Option<f64> {
match self.gate {
Gate::Parity => self.tolerance,
Gate::Bound(bound) => Some(bound),
Gate::ReportGated | Gate::Report => None,
}
}
fn allocations_gated(&self) -> bool {
!matches!(self.gate, Gate::Report)
}
fn failed(&self) -> bool {
if self.allocations_gated() && (self.a_allocs > 0.0 || self.b_allocs > 0.0) {
return true;
}
match self.gate_value() {
Some(bound) => self.attempts_exceeded == ATTEMPTS && self.ratio > bound,
None => false,
}
}
}
struct Attempt {
ratio: f64,
mad: f64,
width: Option<f64>,
bound: Option<f64>,
exceeded: bool,
}
fn attempt_verdict(ratios: &[f64], gate: Gate) -> Attempt {
let mut sorted = ratios.to_vec();
sorted.sort_by(f64::total_cmp);
let ratio = percentile_sorted(&sorted, 0.5);
let mut deviations: Vec<f64> = sorted.iter().map(|r| (r - ratio).abs()).collect();
deviations.sort_by(f64::total_cmp);
let mad = percentile_sorted(&deviations, 0.5);
let (width, bound) = match gate {
Gate::Parity => {
let width = parity_width(ratio, mad);
(Some(width), Some(parity_bound(ratio, mad)))
}
Gate::Bound(bound) => (None, Some(bound)),
Gate::ReportGated | Gate::Report => (None, None),
};
Attempt {
ratio,
mad,
width,
bound,
exceeded: bound.is_some_and(|bound| ratio > bound),
}
}
pub fn measure_case(
id: &'static str,
description: &'static str,
iterations: usize,
gate: Gate,
mut path_a: impl FnMut(),
mut path_b: impl FnMut(),
) -> CaseResult {
path_a();
path_b();
let mut a_samples = Vec::with_capacity(REPS);
let mut b_samples = Vec::with_capacity(REPS);
let mut ratios = Vec::with_capacity(REPS);
let mut worst_ratio = -f64::INFINITY;
let mut reported = None;
let mut tolerance: Option<f64> = None;
let mut max_a_allocs: f64 = 0.0;
let mut max_b_allocs: f64 = 0.0;
let mut attempts_exceeded = 0;
for _ in 0..ATTEMPTS {
a_samples.clear();
b_samples.clear();
ratios.clear();
for _ in 0..REPS {
let a = time_once(iterations, &mut path_a);
let b = time_once(iterations, &mut path_b);
a_samples.push(a);
b_samples.push(b);
ratios.push(a / b);
}
a_samples.sort_by(f64::total_cmp);
b_samples.sort_by(f64::total_cmp);
let a_med = percentile_sorted(&a_samples, 0.5);
let a_p95 = percentile_sorted(&a_samples, 0.95);
let b_med = percentile_sorted(&b_samples, 0.5);
let b_p95 = percentile_sorted(&b_samples, 0.95);
let verdict = attempt_verdict(&ratios, gate);
let (ratio, mad) = (verdict.ratio, verdict.mad);
let (spread, bound) = (verdict.width, verdict.bound);
if verdict.exceeded {
attempts_exceeded += 1;
}
let a_allocs = allocations_per_op(&mut path_a);
let b_allocs = allocations_per_op(&mut path_b);
max_a_allocs = max_a_allocs.max(a_allocs);
max_b_allocs = max_b_allocs.max(b_allocs);
if ratio > worst_ratio {
worst_ratio = ratio;
tolerance = bound;
reported = Some((a_med, a_p95, b_med, b_p95, spread, mad));
}
}
let (a_med, a_p95, b_med, b_p95, spread, mad) = reported.expect("ATTEMPTS > 0");
CaseResult {
id,
description,
a_med,
a_p95,
b_med,
b_p95,
ratio: worst_ratio,
spread,
mad,
a_allocs: max_a_allocs,
b_allocs: max_b_allocs,
gate,
tolerance,
attempts_exceeded,
}
}
pub fn print_table(cases: &[CaseResult], title: &str) {
let mut table = String::new();
table.push_str(
"| id | case | reps | A med ns | A p95 ns | B med ns | B p95 ns | ratio | MAD | width | gate | \
A allocs/op | B allocs/op |\n",
);
table.push_str(
"|----|------|-----:|---------:|---------:|---------:|---------:|------:|------:|------:|------|\
-----------:|-----------:|\n",
);
for case in cases {
let bound = case.gate_value();
let gate = match case.gate {
Gate::Report => "report".to_string(),
Gate::ReportGated if case.failed() => "FAIL (alloc)".to_string(),
Gate::ReportGated => "report (alloc=0)".to_string(),
Gate::Parity | Gate::Bound(_) if case.a_allocs > 0.0 || case.b_allocs > 0.0 => {
"FAIL (alloc)".to_string()
}
Gate::Parity | Gate::Bound(_) if case.failed() => format!(
"FAIL (>{:.3}, {}/{} over)",
bound.unwrap_or(0.0),
case.attempts_exceeded,
ATTEMPTS
),
Gate::Parity => format!(
"bound {:.3} (parity+3w), {}/{} over",
bound.unwrap_or(0.0),
case.attempts_exceeded,
ATTEMPTS
),
Gate::Bound(bound) => {
format!(
"bound {bound}, {}/{} over",
case.attempts_exceeded, ATTEMPTS
)
}
};
table.push_str(&format!(
"| {} | {} | {} | {:.1} | {:.1} | {:.1} | {:.1} | {:.3} | {:.4} | {} | {} | {:.2} | {:.2} |\n",
case.id,
case.description,
REPS,
case.a_med,
case.a_p95,
case.b_med,
case.b_p95,
case.ratio,
case.mad,
case.spread.map_or_else(String::new, |w| format!("{w:.4}")),
gate,
case.a_allocs,
case.b_allocs,
));
}
print!("{table}");
let _ = std::io::stdout().flush();
if let Ok(path) = std::env::var("GITHUB_STEP_SUMMARY") {
if let Ok(mut file) = OpenOptions::new().create(true).append(true).open(path) {
let _ = file.write_all(format!("\n{title}\n\n").as_bytes());
let _ = file.write_all(table.as_bytes());
}
}
}
pub fn exit_if_failed(cases: &[CaseResult]) {
let failed = cases.iter().any(CaseResult::failed);
if failed && std::env::var_os("OVERHEAD_GATE").is_some() {
eprintln!("overhead smoke gate failed (see table above)");
std::process::exit(1);
}
}
#[cfg(test)]
mod tests {
use super::*;
#[allow(dead_code)]
fn case(gate: Gate, ratio: f64, exceeded: usize) -> CaseResult {
CaseResult {
id: "T",
description: "test",
a_med: 2.0,
a_p95: 2.0,
b_med: 1.0,
b_p95: 1.0,
ratio,
spread: None,
mad: 0.0,
a_allocs: 0.0,
b_allocs: 0.0,
gate,
tolerance: Some(1.1),
attempts_exceeded: exceeded,
}
}
#[test]
fn a_parity_gate_needs_every_attempt() {
assert!(case(Gate::Parity, 2.0, ATTEMPTS).failed());
assert!(!case(Gate::Parity, 2.0, ATTEMPTS - 1).failed());
}
#[test]
fn a_bound_gate_compares_the_ratio_with_the_bound() {
assert!(case(Gate::Bound(2.5), 2.6, ATTEMPTS).failed());
assert!(!case(Gate::Bound(2.5), 2.4, ATTEMPTS).failed());
assert!(!case(Gate::Bound(2.5), 2.6, ATTEMPTS - 1).failed());
}
#[test]
fn reporting_rows_only_gate_allocations_when_asked() {
assert!(!case(Gate::Report, 9.0, ATTEMPTS).failed());
let mut gated = case(Gate::ReportGated, 1.0, 0);
assert!(!gated.failed());
gated.a_allocs = 1.0 / ALLOC_ITERS as f64;
assert!(gated.failed());
gated.a_allocs = 0.0;
gated.b_allocs = 1.0 / ALLOC_ITERS as f64;
assert!(gated.failed());
}
#[test]
fn a_parity_width_is_never_zero() {
for median in [0.5f64, 0.95, 1.0, 1.504, 2.0] {
let width = parity_width(median, 0.0);
assert!(width > 0.0, "median {median} gave a zero width");
assert!((width - 0.15 * median).abs() < 1e-12, "floor not applied");
assert!(
parity_bound(median, 0.0) > PARITY_ANCHOR,
"bound not above parity for median {median}"
);
}
let wide = parity_width(1.0, 0.2);
assert!((wide - 1.4826 * 0.2).abs() < 1e-12);
assert!(wide > parity_width(1.0, 0.0));
}
#[test]
fn a_steady_doubling_fails_the_parity_gate() {
let bound = parity_bound(2.0, 0.0);
assert!(bound < 2.0, "bound {bound} would pass a steady 2x slowdown");
let mut steady = case(Gate::Parity, 2.0, ATTEMPTS);
steady.tolerance = Some(bound);
assert!(steady.failed());
let mut same = case(Gate::Parity, 1.0, 0);
same.tolerance = Some(parity_bound(1.0, 0.0));
assert!(!same.failed());
}
#[test]
fn a_bound_gate_ignores_dispersion() {
let mut noisy = case(Gate::Bound(2.5), 2.4, ATTEMPTS);
noisy.mad = 10.0;
noisy.spread = Some(15.0);
assert!(!noisy.failed());
assert_eq!(noisy.gate_value(), Some(2.5));
assert!(parity_bound(1.0, 10.0) > 2.5);
let mut parity = case(Gate::Parity, 2.4, ATTEMPTS);
parity.tolerance = Some(parity_bound(1.0, 10.0));
assert!(!parity.failed());
}
#[test]
fn a_slowdown_is_judged_by_the_production_path() {
let uniform = |value: f64| vec![value; REPS];
let steady_two = attempt_verdict(&uniform(2.0), Gate::Parity);
assert!(
steady_two.exceeded,
"steady 2x admitted: ratio {} against bound {:?}",
steady_two.ratio, steady_two.bound
);
let parity = attempt_verdict(&uniform(1.0), Gate::Parity);
assert!(!parity.exceeded);
assert_eq!(parity.width, Some(parity_width(1.0, 0.0)));
assert_eq!(parity.bound, Some(parity_bound(1.0, 0.0)));
let noisy = attempt_verdict(&[0.5, 0.9, 1.0, 1.0, 1.1, 1.4, 1.6, 1.9, 2.6], Gate::Parity);
assert!(noisy.width.unwrap_or(0.0) > parity.width.unwrap_or(0.0));
assert!(!attempt_verdict(&uniform(2.4), Gate::Bound(2.5)).exceeded);
assert!(attempt_verdict(&uniform(2.6), Gate::Bound(2.5)).exceeded);
assert!(
!attempt_verdict(
&[0.5, 3.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0],
Gate::Bound(2.5)
)
.exceeded
);
assert!(!attempt_verdict(&uniform(50.0), Gate::Report).exceeded);
}
#[test]
fn percentiles_use_nearest_rank() {
let sorted = [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0];
assert_eq!(percentile_sorted(&sorted, 0.5), 5.0);
assert_eq!(percentile_sorted(&sorted, 0.95), 9.0);
assert_eq!(percentile_sorted(&sorted, 0.0), 1.0);
assert_eq!(percentile_sorted(&sorted, 1.0), 9.0);
}
}