krabka_parse_benches/
budget.rs

1//! The budget evaluator: judge a [`PerformanceRecord`] against the
2//! [`Contract`] it was measured under.
3//!
4//! The statistics are the criterion lane's. Each side's centre is its median
5//! over the interleaved rounds, its spread is its relative median absolute
6//! deviation, and the allowed change is the larger of the materiality floor
7//! and a multiple of the larger spread -- [`calibrated_tolerance`], the same
8//! function [`compare_summaries`](crate::compare_summaries) uses.
9
10use {
11    crate::{
12        calibrated_tolerance,
13        contract::{Budget, BudgetError, Contract, Direction, Metric, Mode, contract_digest},
14        median,
15        num::to_f64,
16        record::{Measurement, PerformanceRecord, Side, Subject, Trial, TrialOutcome},
17        relative_mad,
18    },
19    serde::{Deserialize, Serialize},
20    std::collections::{BTreeMap, BTreeSet},
21};
22
23/// How one budgeted metric of one cell came out.
24#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
25#[serde(rename_all = "snake_case")]
26pub enum Status {
27    /// The median did not get worse by more than the materiality floor.
28    WithinBudget,
29    /// The median got better by more than the allowed change.
30    Improved,
31    /// The median got worse by more than the materiality floor, but not by
32    /// more than the spread allows: the change cannot be told from noise.
33    NoisyNotMaterial,
34    /// The median got worse by more than both the floor and the spread allow.
35    MaterialRegression,
36    /// A side's spread exceeded the variance budget, so no verdict is possible.
37    ExcessVariance,
38    /// The metric is recorded for this cell, not budgeted.
39    NotBudgeted,
40}
41
42/// The numbers behind one metric's [`Status`].
43#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
44pub struct MetricVerdict {
45    /// The reference median.
46    pub reference_median: f64,
47    /// The candidate median.
48    pub candidate_median: f64,
49    /// How much worse the candidate median is, as a ratio of the reference
50    /// median. Negative means better, whichever way the metric points.
51    pub worse_change: f64,
52    /// The reference side's relative median absolute deviation.
53    pub reference_spread: f64,
54    /// The candidate side's relative median absolute deviation.
55    pub candidate_spread: f64,
56    /// The change the budget allows, as a ratio; zero when not budgeted.
57    pub allowed_change: f64,
58    /// The outcome.
59    pub status: Status,
60}
61
62/// Why a comparison was rejected.
63#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
64#[serde(tag = "kind", rename_all = "snake_case")]
65pub enum Rejection {
66    /// A trial failed, or its counts show a lost, duplicated or failed record.
67    CorrectnessFailure {
68        /// The cell.
69        cell: String,
70        /// The round.
71        round: usize,
72        /// The side.
73        side: Side,
74        /// What went wrong.
75        reason: String,
76    },
77    /// The contract expects a trial that the record does not hold.
78    MissingTrial {
79        /// The cell.
80        cell: String,
81        /// The round.
82        round: usize,
83        /// The side.
84        side: Side,
85    },
86    /// The same side ran first in two consecutive rounds of a cell.
87    NotInterleaved {
88        /// The cell.
89        cell: String,
90        /// The later of the two rounds.
91        round: usize,
92    },
93    /// A budgeted metric regressed beyond its budget, in a gating mode.
94    MaterialRegression {
95        /// The cell.
96        cell: String,
97        /// The metric.
98        metric: Metric,
99        /// The candidate's relative worsening.
100        worse_change: f64,
101        /// The change the budget allowed.
102        allowed_change: f64,
103    },
104    /// A budgeted metric's spread exceeded its variance budget.
105    ExcessVariance {
106        /// The cell.
107        cell: String,
108        /// The metric.
109        metric: Metric,
110        /// The larger side's relative spread.
111        spread: f64,
112        /// The variance budget, as a ratio.
113        max_spread: f64,
114    },
115}
116
117/// The machine-readable verdict over one record.
118#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
119pub struct BudgetVerdict {
120    /// The contract's name.
121    pub contract_name: String,
122    /// The contract's digest.
123    pub contract_sha256: String,
124    /// The comparison mode.
125    pub mode: Mode,
126    /// Whether this mode's material regressions reject.
127    pub gate_performance: bool,
128    /// The reference side.
129    pub reference: Subject,
130    /// The candidate side.
131    pub candidate: Subject,
132    /// Per cell, per metric. A cell with a rejected trial has no entry.
133    pub cells: BTreeMap<String, BTreeMap<Metric, MetricVerdict>>,
134    /// Everything that rejects the comparison.
135    pub rejections: Vec<Rejection>,
136    /// True only when there is no rejection.
137    pub passed: bool,
138}
139
140/// The value of `metric` in one completed trial.
141#[must_use]
142pub fn metric_value(metric: Metric, measurement: &Measurement) -> f64 {
143    match metric {
144        Metric::RecordsPerSecond => measurement.records_per_second,
145        Metric::LatencyMsP50 => measurement.latency_ms_p50,
146        Metric::LatencyMsP95 => measurement.latency_ms_p95,
147        Metric::LatencyMsP99 => measurement.latency_ms_p99,
148        Metric::CpuMicrosPerRecord => {
149            measurement.cpu_seconds * 1.0e6 / to_f64(measurement.consumed.max(1))
150        }
151        Metric::PeakRssMib => to_f64(measurement.peak_rss_bytes) / 1_048_576.0,
152    }
153}
154
155/// Why a trial is not a correct run of `records` records, if it is not.
156#[must_use]
157pub fn correctness_failure(outcome: &TrialOutcome, records: u64) -> Option<String> {
158    match outcome {
159        TrialOutcome::Failed { reason } => Some(reason.clone()),
160        TrialOutcome::Completed(measurement) => {
161            let Measurement {
162                sent,
163                consumed,
164                duplicates,
165                errors,
166                ..
167            } = measurement;
168            (*sent != records || *consumed != records || *duplicates != 0 || *errors != 0).then(
169                || {
170                    format!(
171                        "expected {records} records; sent={sent} consumed={consumed} \
172                         duplicates={duplicates} errors={errors}"
173                    )
174                },
175            )
176        }
177    }
178}
179
180/// Classify one metric from both sides' values, which must be non-empty.
181///
182/// `budget` is `None` for a metric the cell records but does not budget.
183#[must_use]
184pub fn judge(
185    metric: Metric,
186    reference: &[f64],
187    candidate: &[f64],
188    budget: Option<&Budget>,
189) -> MetricVerdict {
190    let reference_median = median(reference.to_vec());
191    let candidate_median = median(candidate.to_vec());
192    let reference_spread = spread(reference, reference_median);
193    let candidate_spread = spread(candidate, candidate_median);
194    let worse_change = if reference_median == 0.0 {
195        0.0
196    } else {
197        let change = (candidate_median - reference_median) / reference_median;
198        match metric.direction() {
199            Direction::LowerIsBetter => change,
200            Direction::HigherIsBetter => -change,
201        }
202    };
203    let (allowed_change, status) = budget.map_or((0.0, Status::NotBudgeted), |budget| {
204        let materiality = budget.materiality_percent / 100.0;
205        let allowed = calibrated_tolerance(
206            materiality,
207            budget.spread_multiplier,
208            reference_spread,
209            candidate_spread,
210        );
211        let status = if reference_spread.max(candidate_spread) > budget.max_spread_percent / 100.0 {
212            Status::ExcessVariance
213        } else if worse_change > allowed {
214            Status::MaterialRegression
215        } else if worse_change > materiality {
216            Status::NoisyNotMaterial
217        } else if -worse_change > allowed {
218            Status::Improved
219        } else {
220            Status::WithinBudget
221        };
222        (allowed, status)
223    });
224    MetricVerdict {
225        reference_median,
226        candidate_median,
227        worse_change,
228        reference_spread,
229        candidate_spread,
230        allowed_change,
231        status,
232    }
233}
234
235/// Relative MAD, with an all-zero side (a latency below the workload's
236/// resolution, say) counting as no spread rather than a division by zero.
237fn spread(values: &[f64], center: f64) -> f64 {
238    if center == 0.0 {
239        0.0
240    } else {
241        relative_mad(values, center).abs()
242    }
243}
244
245/// Judge `record` against `contract`, whose bytes are `contract_bytes`.
246///
247/// Structural problems -- another contract, a trial for an unknown cell or
248/// round, a trial recorded twice -- are errors: the record cannot be judged at
249/// all. Everything else is a [`Rejection`] in the verdict. A correctness
250/// failure, a missing trial, broken interleaving or excess variance rejects in
251/// every mode; a material regression rejects where the mode's policy gates
252/// performance.
253///
254/// # Errors
255///
256/// Returns [`BudgetError`] when the record does not belong to this contract or
257/// is structurally invalid.
258pub fn evaluate(
259    contract: &Contract,
260    contract_bytes: &[u8],
261    record: &PerformanceRecord,
262) -> Result<BudgetVerdict, BudgetError> {
263    let digest = contract_digest(contract_bytes);
264    if record.contract_name != contract.name || record.contract_sha256 != digest {
265        return Err(BudgetError::ContractMismatch {
266            recorded: format!("{} ({})", record.contract_name, record.contract_sha256),
267            supplied: format!("{} ({digest})", contract.name),
268        });
269    }
270    let mut trials: BTreeMap<(&str, usize, Side), &Trial> = BTreeMap::new();
271    let mut orders = BTreeSet::new();
272    for trial in &record.trials {
273        if contract.cell(&trial.cell).is_none() {
274            return Err(BudgetError::InvalidRecord(format!(
275                "trial for unknown cell {}",
276                trial.cell
277            )));
278        }
279        if trial.round == 0 || trial.round > contract.rounds {
280            return Err(BudgetError::InvalidRecord(format!(
281                "trial for cell {} has round {} outside 1..={}",
282                trial.cell, trial.round, contract.rounds
283            )));
284        }
285        if !orders.insert(trial.order) {
286            return Err(BudgetError::InvalidRecord(format!(
287                "two trials share position {}",
288                trial.order
289            )));
290        }
291        if trials
292            .insert((trial.cell.as_str(), trial.round, trial.side), trial)
293            .is_some()
294        {
295            return Err(BudgetError::InvalidRecord(format!(
296                "cell {} round {} {} appears twice",
297                trial.cell,
298                trial.round,
299                trial.side.name()
300            )));
301        }
302    }
303
304    let gate_performance = contract
305        .modes
306        .get(&record.mode)
307        .ok_or_else(|| {
308            BudgetError::InvalidRecord(format!(
309                "mode {} is not in the contract",
310                record.mode.name()
311            ))
312        })?
313        .gate_performance;
314    let mut rejections = Vec::new();
315    let mut cells = BTreeMap::new();
316    for cell in &contract.cells {
317        let mut sound = true;
318        let mut values: BTreeMap<Side, Vec<&Measurement>> = BTreeMap::new();
319        for round in 1..=contract.rounds {
320            for side in Side::BOTH {
321                let Some(trial) = trials.get(&(cell.id.as_str(), round, side)) else {
322                    sound = false;
323                    rejections.push(Rejection::MissingTrial {
324                        cell: cell.id.clone(),
325                        round,
326                        side,
327                    });
328                    continue;
329                };
330                if let Some(reason) = correctness_failure(&trial.outcome, cell.records) {
331                    sound = false;
332                    rejections.push(Rejection::CorrectnessFailure {
333                        cell: cell.id.clone(),
334                        round,
335                        side,
336                        reason,
337                    });
338                } else if let TrialOutcome::Completed(measurement) = &trial.outcome {
339                    values.entry(side).or_default().push(measurement);
340                }
341            }
342        }
343        let first_side = |round: usize| -> Option<Side> {
344            let reference = trials.get(&(cell.id.as_str(), round, Side::Reference))?;
345            let candidate = trials.get(&(cell.id.as_str(), round, Side::Candidate))?;
346            Some(if reference.order < candidate.order {
347                Side::Reference
348            } else {
349                Side::Candidate
350            })
351        };
352        for round in 2..=contract.rounds {
353            if let (Some(previous), Some(current)) = (first_side(round - 1), first_side(round))
354                && previous == current
355            {
356                sound = false;
357                rejections.push(Rejection::NotInterleaved {
358                    cell: cell.id.clone(),
359                    round,
360                });
361            }
362        }
363        if !sound {
364            continue;
365        }
366        let mut metrics = BTreeMap::new();
367        for metric in Metric::ALL {
368            let side_values = |side: Side| -> Vec<f64> {
369                values
370                    .get(&side)
371                    .into_iter()
372                    .flatten()
373                    .map(|measurement| metric_value(metric, measurement))
374                    .collect()
375            };
376            let budget = contract
377                .budgets
378                .get(&metric)
379                .filter(|_| cell.budgeted.contains(&metric));
380            let verdict = judge(
381                metric,
382                &side_values(Side::Reference),
383                &side_values(Side::Candidate),
384                budget,
385            );
386            match verdict.status {
387                Status::ExcessVariance => rejections.push(Rejection::ExcessVariance {
388                    cell: cell.id.clone(),
389                    metric,
390                    spread: verdict.reference_spread.max(verdict.candidate_spread),
391                    max_spread: budget.map_or(0.0, |budget| budget.max_spread_percent / 100.0),
392                }),
393                Status::MaterialRegression if gate_performance => {
394                    rejections.push(Rejection::MaterialRegression {
395                        cell: cell.id.clone(),
396                        metric,
397                        worse_change: verdict.worse_change,
398                        allowed_change: verdict.allowed_change,
399                    });
400                }
401                _ => {}
402            }
403            metrics.insert(metric, verdict);
404        }
405        cells.insert(cell.id.clone(), metrics);
406    }
407    Ok(BudgetVerdict {
408        contract_name: contract.name.clone(),
409        contract_sha256: digest,
410        mode: record.mode,
411        gate_performance,
412        reference: record.reference.clone(),
413        candidate: record.candidate.clone(),
414        cells,
415        passed: rejections.is_empty(),
416        rejections,
417    })
418}
krabka_parse_benches/budget.rs

krabka_parse_benches/
budget.rs
