Skip to main content

ic_testkit/benchmark/
mod.rs

1//! Parse, pair, aggregate, compare, and report compact benchmark markers.
2//!
3//! The normal pipeline is [`parse_benchmark_events`],
4//! [`pair_benchmark_spans`], [`aggregate_benchmark_spans`], and optionally
5//! [`compare_benchmark_aggregates`]. Native report output lives in
6//! the repository's `benchmark_report` example. Marker
7//! producers can use [`format_marker`] on the host or
8//! `ic_testkit::performance::Performance` in canister code.
9//!
10//! Totals and run counts remain exact integers. Means use Testkit's exact
11//! scaled integer projection, rounded down. Callers choose the scale and handle
12//! projection errors; reports use scale one in the original counter units.
13//! Comparisons retain current and previous means instead of percentage estimates.
14
15use std::collections::{BTreeMap, btree_map::Entry};
16
17/// Why a benchmark's scaled average cannot be represented.
18#[derive(Clone, Copy, Debug, Eq, PartialEq)]
19pub enum BenchmarkAverageError {
20    /// A mean is undefined when the run count is zero, even at scale zero.
21    ZeroDenominator,
22    /// The scaled average exceeds `u128::MAX`.
23    Overflow,
24}
25
26impl std::fmt::Display for BenchmarkAverageError {
27    fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
28        formatter.write_str(match self {
29            Self::ZeroDenominator => "benchmark run count is zero",
30            Self::Overflow => "scaled benchmark average exceeds u128",
31        })
32    }
33}
34
35impl std::error::Error for BenchmarkAverageError {}
36
37fn checked_scaled_average(
38    total: u128,
39    runs: u64,
40    scale: u64,
41) -> Result<u128, BenchmarkAverageError> {
42    if runs == 0 {
43        return Err(BenchmarkAverageError::ZeroDenominator);
44    }
45    let runs = u128::from(runs);
46    let scale = u128::from(scale);
47    // Split before multiplying: only the final average must fit. The remainder
48    // and scale are at most u64::MAX, so their product always fits in u128.
49    let fraction = (total % runs) * scale / runs;
50    (total / runs)
51        .checked_mul(scale)
52        .and_then(|whole| whole.checked_add(fraction))
53        .ok_or(BenchmarkAverageError::Overflow)
54}
55
56/// Default prefix for benchmark marker lines.
57pub const DEFAULT_PREFIX: &str = "ICTK";
58
59/// Structural identity of one suite or the cross-suite aggregate.
60#[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
61pub enum BenchmarkScope {
62    /// One caller-authored suite, including a suite literally named `ALL`.
63    Suite(String),
64    /// Aggregate across every suite.
65    All,
66}
67
68#[derive(Clone, Debug, Eq, PartialEq)]
69pub struct BenchmarkParserConfig {
70    pub prefixes: Vec<String>,
71    pub suite_derivation: SuiteDerivation,
72    /// When enabled, non-empty lines without a configured marker prefix are
73    /// reported as malformed markers instead of ignored log noise.
74    pub strict: bool,
75}
76
77impl Default for BenchmarkParserConfig {
78    fn default() -> Self {
79        Self {
80            prefixes: vec![DEFAULT_PREFIX.to_string()],
81            suite_derivation: SuiteDerivation::FirstPathSegment,
82            strict: false,
83        }
84    }
85}
86
87#[derive(Clone, Debug, Eq, PartialEq)]
88pub enum SuiteDerivation {
89    FirstPathSegment,
90    Fixed(String),
91}
92
93impl SuiteDerivation {
94    #[must_use]
95    pub fn derive_suite(&self, span_label: &str) -> String {
96        match self {
97            Self::FirstPathSegment => span_label
98                .split('/')
99                .next()
100                .filter(|part| !part.is_empty())
101                .unwrap_or(span_label)
102                .to_string(),
103            Self::Fixed(suite) => suite.clone(),
104        }
105    }
106}
107
108#[derive(Clone, Copy, Debug, Eq, PartialEq)]
109pub enum BenchmarkEventKind {
110    Start,
111    End,
112}
113
114#[derive(Clone, Copy, Debug, Eq, PartialEq)]
115pub enum BenchmarkEventSource {
116    Unknown,
117    Stdout,
118    Stderr,
119    FetchedLog,
120}
121
122impl BenchmarkEventSource {
123    #[must_use]
124    pub const fn as_str(self) -> &'static str {
125        match self {
126            Self::Unknown => "unknown",
127            Self::Stdout => "stdout",
128            Self::Stderr => "stderr",
129            Self::FetchedLog => "fetched_log",
130        }
131    }
132}
133
134#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
135pub struct BenchmarkCounters {
136    pub instructions: u128,
137    pub heap_bytes: u128,
138    pub memory_bytes: u128,
139}
140
141impl BenchmarkCounters {
142    fn checked_delta(self, start: Self) -> Option<Self> {
143        Some(Self {
144            instructions: self.instructions.checked_sub(start.instructions)?,
145            heap_bytes: self.heap_bytes.checked_sub(start.heap_bytes)?,
146            memory_bytes: self.memory_bytes.checked_sub(start.memory_bytes)?,
147        })
148    }
149
150    fn checked_add(self, other: Self) -> Result<Self, BenchmarkCounter> {
151        Ok(Self {
152            instructions: self
153                .instructions
154                .checked_add(other.instructions)
155                .ok_or(BenchmarkCounter::Instructions)?,
156            heap_bytes: self
157                .heap_bytes
158                .checked_add(other.heap_bytes)
159                .ok_or(BenchmarkCounter::HeapBytes)?,
160            memory_bytes: self
161                .memory_bytes
162                .checked_add(other.memory_bytes)
163                .ok_or(BenchmarkCounter::MemoryBytes)?,
164        })
165    }
166
167    fn min_assign(&mut self, other: Self) {
168        self.instructions = self.instructions.min(other.instructions);
169        self.heap_bytes = self.heap_bytes.min(other.heap_bytes);
170        self.memory_bytes = self.memory_bytes.min(other.memory_bytes);
171    }
172
173    fn max_assign(&mut self, other: Self) {
174        self.instructions = self.instructions.max(other.instructions);
175        self.heap_bytes = self.heap_bytes.max(other.heap_bytes);
176        self.memory_bytes = self.memory_bytes.max(other.memory_bytes);
177    }
178}
179
180#[derive(Clone, Debug, Eq, PartialEq)]
181pub struct RawBenchmarkEvent {
182    pub prefix: String,
183    pub suite: String,
184    pub span_label: String,
185    pub kind: BenchmarkEventKind,
186    pub counters: BenchmarkCounters,
187    pub source_line: usize,
188    pub source: BenchmarkEventSource,
189}
190
191#[derive(Clone, Debug, Eq, PartialEq)]
192pub struct MalformedBenchmarkMarker {
193    pub source_line: usize,
194    pub source: BenchmarkEventSource,
195    pub line: String,
196    pub reason: String,
197}
198
199#[derive(Clone, Debug, Default, Eq, PartialEq)]
200pub struct BenchmarkParseReport {
201    pub events: Vec<RawBenchmarkEvent>,
202    pub malformed_markers: Vec<MalformedBenchmarkMarker>,
203    pub ignored_line_count: usize,
204}
205
206#[derive(Clone, Debug, Eq, PartialEq)]
207pub struct BenchmarkSpan {
208    pub suite: String,
209    pub span_label: String,
210    pub start_line: usize,
211    pub end_line: usize,
212    pub end: BenchmarkCounters,
213    pub delta: BenchmarkCounters,
214}
215
216#[derive(Clone, Debug, Eq, PartialEq)]
217pub struct InvalidBenchmarkSpan {
218    pub start: RawBenchmarkEvent,
219    pub end: RawBenchmarkEvent,
220}
221
222#[derive(Clone, Debug, Default, Eq, PartialEq)]
223pub struct BenchmarkSpanReport {
224    pub spans: Vec<BenchmarkSpan>,
225    pub unpaired_markers: Vec<RawBenchmarkEvent>,
226    pub invalid_spans: Vec<InvalidBenchmarkSpan>,
227}
228
229#[derive(Clone, Debug, Eq, PartialEq)]
230pub struct BenchmarkAggregateRow {
231    pub span_label: String,
232    pub runs: u64,
233    pub total: BenchmarkCounters,
234    pub min: BenchmarkCounters,
235    pub max: BenchmarkCounters,
236    pub peak_end: BenchmarkCounters,
237    /// Suite identity or the cross-suite aggregate.
238    pub scope: BenchmarkScope,
239}
240
241/// Floor-rounded scaled means of exact aggregate totals and run counts.
242///
243/// Fields are `floor(total * scale / runs)`; choose a positive scale to
244/// interpret them in the original counter unit. Scale zero projects zero.
245#[derive(Clone, Copy, Debug, Eq, PartialEq)]
246pub struct BenchmarkAverages {
247    pub scale: u64,
248    pub instructions: u128,
249    pub heap_bytes: u128,
250    pub memory_bytes: u128,
251}
252
253/// Counter whose aggregate cannot be represented.
254#[derive(Clone, Copy, Debug, Eq, PartialEq)]
255pub enum BenchmarkCounter {
256    Runs,
257    Instructions,
258    HeapBytes,
259    MemoryBytes,
260}
261
262/// Overflow rejects the complete aggregation, without returning partial totals.
263#[derive(Clone, Debug, Eq, PartialEq)]
264pub struct BenchmarkAggregateError {
265    pub span_label: String,
266    pub counter: BenchmarkCounter,
267    /// Suite identity or the cross-suite aggregate.
268    pub scope: BenchmarkScope,
269}
270
271impl std::fmt::Display for BenchmarkAggregateError {
272    fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
273        write!(
274            formatter,
275            "benchmark aggregate overflow: scope={:?}, span={}, counter={:?}",
276            self.scope, self.span_label, self.counter
277        )
278    }
279}
280
281impl std::error::Error for BenchmarkAggregateError {}
282
283/// Run count and scaled means for one present comparison side.
284#[derive(Clone, Copy, Debug, Eq, PartialEq)]
285pub struct BenchmarkMeasurement {
286    pub runs: u64,
287    pub average: BenchmarkAverages,
288}
289
290/// Current and previous measurements, preserving missing rows and measured zero.
291#[derive(Clone, Debug, Eq, PartialEq)]
292pub struct BenchmarkComparisonRow {
293    pub span_label: String,
294    pub current: Option<BenchmarkMeasurement>,
295    pub previous: Option<BenchmarkMeasurement>,
296    /// Suite identity or the cross-suite aggregate.
297    pub scope: BenchmarkScope,
298}
299
300impl BenchmarkAggregateRow {
301    /// Project exact totals at the caller's scale, rounding down.
302    /// Zero runs and unrepresentable scaled results return [`BenchmarkAverageError`].
303    pub fn average(&self, scale: u64) -> Result<BenchmarkAverages, BenchmarkAverageError> {
304        Ok(BenchmarkAverages {
305            scale,
306            instructions: checked_scaled_average(self.total.instructions, self.runs, scale)?,
307            heap_bytes: checked_scaled_average(self.total.heap_bytes, self.runs, scale)?,
308            memory_bytes: checked_scaled_average(self.total.memory_bytes, self.runs, scale)?,
309        })
310    }
311}
312
313#[must_use]
314pub fn format_marker(prefix: &str, label: &str, counters: BenchmarkCounters) -> String {
315    format!(
316        "{}|{}|{}|{}|{}",
317        prefix, label, counters.instructions, counters.heap_bytes, counters.memory_bytes
318    )
319}
320
321#[must_use]
322pub fn parse_benchmark_events(input: &str, config: &BenchmarkParserConfig) -> BenchmarkParseReport {
323    parse_benchmark_events_from_source(input, config, BenchmarkEventSource::Unknown)
324}
325
326#[must_use]
327pub fn parse_benchmark_events_from_source(
328    input: &str,
329    config: &BenchmarkParserConfig,
330    source: BenchmarkEventSource,
331) -> BenchmarkParseReport {
332    let mut report = BenchmarkParseReport::default();
333    append_benchmark_events(&mut report, input, config, source);
334    report
335}
336
337fn append_benchmark_events(
338    report: &mut BenchmarkParseReport,
339    input: &str,
340    config: &BenchmarkParserConfig,
341    source: BenchmarkEventSource,
342) {
343    for (index, line) in input.lines().enumerate() {
344        let source_line = index + 1;
345        if !has_configured_prefix(line, &config.prefixes) {
346            if config.strict && !line.trim().is_empty() {
347                report.malformed_markers.push(malformed(
348                    source_line,
349                    source,
350                    line,
351                    "line does not use a configured marker prefix",
352                ));
353            } else {
354                report.ignored_line_count += 1;
355            }
356            continue;
357        }
358
359        match parse_marker_line(line, source_line, source, config) {
360            Ok(event) => report.events.push(event),
361            Err(marker) => report.malformed_markers.push(marker),
362        }
363    }
364}
365
366/// Parse separately captured stdout and stderr.
367///
368/// Separate streams do not carry global ordering, so events are returned in
369/// stdout-then-stderr order. If a benchmark span can start on one stream and end
370/// on the other, capture combined process output and use [`parse_benchmark_events`].
371#[must_use]
372pub fn parse_benchmark_events_from_captured_output(
373    stdout: &str,
374    stderr: &str,
375    config: &BenchmarkParserConfig,
376) -> BenchmarkParseReport {
377    let mut report = BenchmarkParseReport::default();
378    append_benchmark_events(&mut report, stdout, config, BenchmarkEventSource::Stdout);
379    append_benchmark_events(&mut report, stderr, config, BenchmarkEventSource::Stderr);
380    report
381}
382
383#[must_use]
384pub fn pair_benchmark_spans(events: &[RawBenchmarkEvent]) -> BenchmarkSpanReport {
385    let mut report = BenchmarkSpanReport::default();
386    let mut open_starts: BTreeMap<(&str, &str), Vec<&RawBenchmarkEvent>> = BTreeMap::new();
387
388    for event in events {
389        let key = (event.suite.as_str(), event.span_label.as_str());
390        match event.kind {
391            BenchmarkEventKind::Start => open_starts.entry(key).or_default().push(event),
392            BenchmarkEventKind::End => match open_starts.entry(key) {
393                Entry::Occupied(mut entry) => {
394                    let start = entry
395                        .get_mut()
396                        .pop()
397                        .expect("open marker stacks must remain nonempty");
398                    if entry.get().is_empty() {
399                        entry.remove();
400                    }
401                    push_paired_span(&mut report, start, event);
402                }
403                Entry::Vacant(_) => report.unpaired_markers.push(event.clone()),
404            },
405        }
406    }
407
408    for starts in open_starts.into_values() {
409        for event in starts {
410            report.unpaired_markers.push(event.clone());
411        }
412    }
413
414    report
415}
416
417/// Aggregate spans by named suite and across all suites.
418///
419/// Returns an error if any counter total or run count overflows. No partial
420/// report is returned, and totals are never wrapped or saturated.
421pub fn aggregate_benchmark_spans(
422    spans: &[BenchmarkSpan],
423) -> Result<Vec<BenchmarkAggregateRow>, BenchmarkAggregateError> {
424    let mut rows = BTreeMap::new();
425
426    for span in spans {
427        add_span_to_aggregate(&mut rows, AggregateScope::Suite(&span.suite), span)?;
428        add_span_to_aggregate(&mut rows, AggregateScope::All, span)?;
429    }
430
431    Ok(rows
432        .into_iter()
433        .map(|((scope, span_label), builder)| {
434            builder.finish(scope.into_owned(), span_label.to_owned())
435        })
436        .collect())
437}
438
439/// Pair current and previous means at the same caller-selected scale.
440/// Returns a typed error if either side cannot supply the selected projection.
441pub fn compare_benchmark_aggregates(
442    current: &[BenchmarkAggregateRow],
443    previous: &[BenchmarkAggregateRow],
444    scale: u64,
445) -> Result<Vec<BenchmarkComparisonRow>, BenchmarkAverageError> {
446    let mut rows = BTreeMap::new();
447    for row in current {
448        rows.insert((&row.scope, row.span_label.as_str()), (Some(row), None));
449    }
450    for row in previous {
451        rows.entry((&row.scope, row.span_label.as_str()))
452            .or_insert((None, None))
453            .1 = Some(row);
454    }
455    let measurement = |row: &BenchmarkAggregateRow| -> Result<_, BenchmarkAverageError> {
456        Ok(BenchmarkMeasurement {
457            runs: row.runs,
458            average: row.average(scale)?,
459        })
460    };
461
462    rows.into_iter()
463        .map(|((scope, span_label), (current_row, previous_row))| {
464            Ok(BenchmarkComparisonRow {
465                span_label: span_label.to_owned(),
466                current: current_row.map(measurement).transpose()?,
467                previous: previous_row.map(measurement).transpose()?,
468                scope: scope.clone(),
469            })
470        })
471        .collect()
472}
473
474fn parse_marker_line(
475    line: &str,
476    source_line: usize,
477    source: BenchmarkEventSource,
478    config: &BenchmarkParserConfig,
479) -> Result<RawBenchmarkEvent, MalformedBenchmarkMarker> {
480    let mut parts = line.split('|');
481    // Five fields and an absent sixth establish the complete marker shape
482    // without collecting an arbitrary number of columns from malformed logs.
483    let columns: [Option<&str>; 6] = std::array::from_fn(|_| parts.next());
484    let [
485        Some(prefix),
486        Some(label),
487        Some(instructions),
488        Some(heap_bytes),
489        Some(memory_bytes),
490        None,
491    ] = columns
492    else {
493        return Err(malformed(
494            source_line,
495            source,
496            line,
497            "expected five pipe-separated columns",
498        ));
499    };
500
501    if !config.prefixes.iter().any(|known| known == prefix) {
502        return Err(malformed(
503            source_line,
504            source,
505            line,
506            "prefix is not configured",
507        ));
508    }
509
510    if label.is_empty() {
511        return Err(malformed(source_line, source, line, "label is empty"));
512    }
513
514    let (span_label, kind) = split_label_kind(label).ok_or_else(|| {
515        malformed(
516            source_line,
517            source,
518            line,
519            "label must end in :start or :end",
520        )
521    })?;
522
523    let counters = BenchmarkCounters {
524        instructions: parse_counter(instructions, source_line, source, line, "instructions")?,
525        heap_bytes: parse_counter(heap_bytes, source_line, source, line, "heap_bytes")?,
526        memory_bytes: parse_counter(memory_bytes, source_line, source, line, "memory_bytes")?,
527    };
528    let suite = config.suite_derivation.derive_suite(span_label);
529
530    Ok(RawBenchmarkEvent {
531        prefix: prefix.to_string(),
532        suite,
533        span_label: span_label.to_string(),
534        kind,
535        counters,
536        source_line,
537        source,
538    })
539}
540
541fn parse_counter(
542    value: &str,
543    source_line: usize,
544    source: BenchmarkEventSource,
545    line: &str,
546    name: &str,
547) -> Result<u128, MalformedBenchmarkMarker> {
548    if value.is_empty() {
549        return Err(malformed(
550            source_line,
551            source,
552            line,
553            format!("{name} counter is empty"),
554        ));
555    }
556
557    value.parse::<u128>().map_err(|_| {
558        malformed(
559            source_line,
560            source,
561            line,
562            format!("{name} counter is not an unsigned integer"),
563        )
564    })
565}
566
567fn split_label_kind(label: &str) -> Option<(&str, BenchmarkEventKind)> {
568    let start = label.strip_suffix(":start");
569    let end = label.strip_suffix(":end");
570
571    match (start, end) {
572        (Some(span_label), None) if !span_label.is_empty() => {
573            Some((span_label, BenchmarkEventKind::Start))
574        }
575        (None, Some(span_label)) if !span_label.is_empty() => {
576            Some((span_label, BenchmarkEventKind::End))
577        }
578        _ => None,
579    }
580}
581
582fn has_configured_prefix(line: &str, prefixes: &[String]) -> bool {
583    prefixes.iter().any(|prefix| {
584        line.strip_prefix(prefix)
585            .is_some_and(|rest| rest.starts_with('|'))
586    })
587}
588
589fn malformed(
590    source_line: usize,
591    source: BenchmarkEventSource,
592    line: &str,
593    reason: impl Into<String>,
594) -> MalformedBenchmarkMarker {
595    MalformedBenchmarkMarker {
596        source_line,
597        source,
598        line: line.to_string(),
599        reason: reason.into(),
600    }
601}
602
603fn push_paired_span(
604    report: &mut BenchmarkSpanReport,
605    start: &RawBenchmarkEvent,
606    end: &RawBenchmarkEvent,
607) {
608    if let Some(delta) = end.counters.checked_delta(start.counters) {
609        report.spans.push(BenchmarkSpan {
610            suite: start.suite.clone(),
611            span_label: start.span_label.clone(),
612            start_line: start.source_line,
613            end_line: end.source_line,
614            end: end.counters,
615            delta,
616        });
617    } else {
618        report.invalid_spans.push(InvalidBenchmarkSpan {
619            start: start.clone(),
620            end: end.clone(),
621        });
622    }
623}
624
625// Borrow grouping identities until a row or error must own them. Keep the same
626// suite-before-all ordering as the public report scope.
627#[derive(Clone, Copy, Eq, Ord, PartialEq, PartialOrd)]
628enum AggregateScope<'a> {
629    Suite(&'a str),
630    All,
631}
632
633impl AggregateScope<'_> {
634    fn into_owned(self) -> BenchmarkScope {
635        match self {
636            Self::Suite(suite) => BenchmarkScope::Suite(suite.to_owned()),
637            Self::All => BenchmarkScope::All,
638        }
639    }
640}
641
642#[derive(Clone, Debug)]
643struct AggregateBuilder {
644    runs: u64,
645    total: BenchmarkCounters,
646    min: BenchmarkCounters,
647    max: BenchmarkCounters,
648    peak_end: BenchmarkCounters,
649}
650
651impl AggregateBuilder {
652    const fn new(span: &BenchmarkSpan) -> Self {
653        Self {
654            runs: 1,
655            total: span.delta,
656            min: span.delta,
657            max: span.delta,
658            peak_end: span.end,
659        }
660    }
661
662    fn push(&mut self, span: &BenchmarkSpan) -> Result<(), BenchmarkCounter> {
663        let runs = self.runs.checked_add(1).ok_or(BenchmarkCounter::Runs)?;
664        let total = self.total.checked_add(span.delta)?;
665        self.runs = runs;
666        self.total = total;
667        self.min.min_assign(span.delta);
668        self.max.max_assign(span.delta);
669        self.peak_end.max_assign(span.end);
670        Ok(())
671    }
672
673    const fn finish(self, scope: BenchmarkScope, span_label: String) -> BenchmarkAggregateRow {
674        BenchmarkAggregateRow {
675            span_label,
676            runs: self.runs,
677            total: self.total,
678            min: self.min,
679            max: self.max,
680            peak_end: self.peak_end,
681            scope,
682        }
683    }
684}
685
686fn add_span_to_aggregate<'a>(
687    rows: &mut BTreeMap<(AggregateScope<'a>, &'a str), AggregateBuilder>,
688    scope: AggregateScope<'a>,
689    span: &'a BenchmarkSpan,
690) -> Result<(), BenchmarkAggregateError> {
691    match rows.entry((scope, span.span_label.as_str())) {
692        Entry::Occupied(mut entry) => entry.get_mut().push(span).map_err(|counter| {
693            let (scope, span_label) = entry.key();
694            BenchmarkAggregateError {
695                span_label: (*span_label).to_owned(),
696                counter,
697                scope: scope.into_owned(),
698            }
699        }),
700        Entry::Vacant(entry) => {
701            entry.insert(AggregateBuilder::new(span));
702            Ok(())
703        }
704    }
705}
706
707#[cfg(test)]
708mod tests {
709    use super::{AggregateBuilder, BenchmarkCounter, BenchmarkCounters, BenchmarkSpan};
710
711    #[test]
712    fn aggregate_run_count_overflow_is_rejected_without_changing_totals() {
713        let span = BenchmarkSpan {
714            suite: "probe".into(),
715            span_label: "probe/run".into(),
716            start_line: 1,
717            end_line: 2,
718            end: BenchmarkCounters::default(),
719            delta: BenchmarkCounters::default(),
720        };
721        let mut builder = AggregateBuilder::new(&span);
722        builder.runs = u64::MAX;
723        assert_eq!(builder.push(&span), Err(BenchmarkCounter::Runs));
724        assert_eq!(builder.runs, u64::MAX);
725        assert_eq!(builder.total, BenchmarkCounters::default());
726    }
727}