Learn Rust Series (#55) - Benchmarking with Criterion and Reading the Numbers

avatar

Learn Rust Series (#55) - Benchmarking with Criterion and Reading the Numbers

rust-banner.png

What will I learn

  • You will learn why naive benchmarking with a single Instant measurement lies to you;
  • what criterion does: many samples, statistics, outlier detection, and regression tracking;
  • what black_box is, and why without it the optimizer deletes the very code you meant to measure;
  • how to read criterion's output -- the point estimate, the confidence interval, and the "5% faster" verdict;
  • how to compare two implementations honestly, measure across input sizes, and turn a duration into throughput.

Requirements

  • A working modern computer running macOS, Windows or Ubuntu, with Cargo;
  • An installed Rust toolchain (via rustup, from rustup.rs);
  • The previous fifty-four episodes, especially closures, generics, and iterators;
  • The ambition to learn systems programming from the ground up.

Difficulty

  • Intermediate

Curriculum (of the Learn Rust Series):

Learn Rust Series (#55) - Benchmarking with Criterion and Reading the Numbers

For three episodes we hammered on one question: is my code correct? Unit tests, property tests, and last episode's fuzzing all attacked it from different angles. With correctness reasonably in hand, the next question every systems programmer eventually faces is the one that fills forums with arguments and almost no data: how fast is it? And here is the uncomfortable truth I promised you at the end of episode 54 -- intuition about performance is almost always wrong. The line you are certain is the bottleneck usually is not, and the "obviously slower" version frequently wins. The only cure is to stop guessing and start measuring.

Measuring speed sounds trivial and is deceptively hard. Wrap a function in a single Instant::now() pair and you get a number, sure, but it is a bad number: one noisy sample, contaminated by cold caches and CPU frequency scaling, and -- worst of all -- Rust's optimizer may have deleted your benchmark entirely because you never used the result. criterion is the de-facto standard benchmarking crate for Rust, and it solves all of this by taking hundreds of samples, applying real statistics, detecting outliers, and comparing against previous runs so a regression cannot sneak past you. Even if you never install it, understanding why it works -- especially black_box -- makes you far harder to fool ;-)

Solutions to Episode 54 Exercises

Episode 54 was fuzzing, and all three exercises were about writing byte-eating code that never panics. Here they are in full.

Exercise 1 asked for a parse_record(&[u8]) -> Option<(u8, &[u8])> that reads a tag byte, then a length byte, then a payload of that many bytes, using only first/split_first and range-get, never indexing:

fn parse_record(data: &[u8]) -> Option<(u8, &[u8])> {
    let (&tag, rest) = data.split_first()?;   // None on empty input
    let (&len, body) = rest.split_first()?;   // None if there is no length byte
    let payload = body.get(..len as usize)?;  // None if the payload is truncated
    Some((tag, payload))
}

fn main() {
    println!("{:?}", parse_record(&[7, 2, 0xAA, 0xBB])); // Some((7, [170, 187]))
    println!("{:?}", parse_record(&[7, 9, 0xAA]));       // None, payload too short
    println!("{:?}", parse_record(&[]));                 // None, no tag at all
}

The key insight is that split_first peels one element and hands back the rest as a subslice in a single move, so two chained ? cover both the "empty" and "no length byte" cases with no arithmetic. The body.get(..len) range access then returns None -- never a panic -- when the declared length overruns the buffer. The function is total: it has a defined answer for every possible input.

Exercise 2 asked us to drop the naive parse_bad into the by-hand fuzz loop and count how many iterations it survives, then swap in the robust parse_message and confirm it survives all of them. To count panics without the first one aborting the program, we wrap the call in catch_unwind (episode 51):

use std::panic::{self, AssertUnwindSafe};

fn parse_bad(data: &[u8]) -> &[u8] {
    let len = data[0] as usize; // panics on empty, and on oversized len below
    &data[1..1 + len]
}

fn parse_message(data: &[u8]) -> Option<&[u8]> {
    let len = *data.first()? as usize;
    data.get(1..1 + len)
}

fn main() {
    panic::set_hook(Box::new(|_| {})); // silence the panic backtrace spam
    let mut rng: u64 = 0xABCD;
    let mut bad_survived = 0u32;
    for _ in 0..5000 {
        rng = rng.wrapping_mul(6364136223846793005).wrapping_add(1);
        let len = (rng % 8) as usize;
        let data: Vec<u8> = (0..len).map(|i| (rng >> (i % 8)) as u8).collect();
        let outcome = panic::catch_unwind(AssertUnwindSafe(|| { let _ = parse_bad(&data); }));
        if outcome.is_ok() { bad_survived += 1; } else { break; }
    }
    let good_survived = (0..5000).filter(|_| {
        rng = rng.wrapping_mul(6364136223846793005).wrapping_add(1);
        let len = (rng % 8) as usize;
        let data: Vec<u8> = (0..len).map(|i| (rng >> (i % 8)) as u8).collect();
        parse_message(&data);
        true
    }).count();
    println!("parse_bad survived {bad_survived} inputs; parse_message survived {good_survived}");
}

On my machine parse_bad typically detonates within the first handful of iterations (an empty buffer or an oversized length byte shows up almost immediately), while parse_message sails through all 5000. The two numbers are the whole lesson: robustness is not a vague virtue, it is the difference between "died at iteration 3" and "handled everything".

Exercise 3 wanted an encode/decode pair for run-length encoding, with a round-trip check over many random buffers -- and decode returning Option so a malformed encoding is None, never a panic:

struct Lcg(u64);
impl Lcg {
    fn next_u64(&mut self) -> u64 {
        self.0 = self.0.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
        self.0
    }
}

fn rle_encode(data: &[u8]) -> Vec<(u8, u8)> {
    let mut out: Vec<(u8, u8)> = Vec::new();
    for &b in data {
        match out.last_mut() {
            Some((val, count)) if *val == b && *count < 255 => *count += 1,
            _ => out.push((b, 1)),
        }
    }
    out
}

fn rle_decode(pairs: &[(u8, u8)]) -> Vec<u8> {
    let mut out = Vec::new();
    for &(val, count) in pairs {
        out.extend(std::iter::repeat(val).take(count as usize));
    }
    out
}

fn main() {
    let mut rng = Lcg(0xC0FFEE);
    for _ in 0..500 {
        let len = (rng.next_u64() % 64) as usize;
        let data: Vec<u8> = (0..len).map(|_| (rng.next_u64() % 4) as u8).collect();
        assert_eq!(rle_decode(&rle_encode(&data)), data); // round-trip identity
    }
    println!("RLE round-trip held over 500 random buffers");
}

The *count < 255 guard is the subtle part: a run longer than 255 must be split into multiple pairs, or the u8 count wraps and the round-trip silently breaks. Keeping the alphabet small (% 4) makes long runs likely, so the generator actually exercises that boundary. Right, homework cleared. Now, benchmarking.

The naive measurement, and why it lies

The obvious approach is one Instant pair around the call. It compiles, it prints a duration, and you should not trust it one bit:

use std::time::Instant;

fn work(n: u64) -> u64 {
    (1..=n).map(|x| x * x).sum()
}

fn main() {
    let start = Instant::now();
    let result = work(1_000_000);
    let elapsed = start.elapsed();
    println!("result={result} took {elapsed:?}");
    // one sample is noisy -- and if we never used `result` the optimizer could delete `work` entirely
}

There are two independent problems buried here. The first is noise: a single sample is dominated by whatever else the machine was doing that microsecond -- a context switch, a cache miss, the CPU deciding to ramp its clock up (or down) for thermal reasons. Run this five times and you will get five different numbers, sometimes off by 2x, and none of them is "the" answer. The second problem is far more sinister. Rust's optimizer is aggressive, and it operates on a simple principle: if a computation's result is never observed, the computation need not happen. If you delete the println!, the compiler is entirely within its rights to notice that result is unused and compile work(1_000_000) down to nothing at all. You would then proudly report that summing a million squares takes zero nanoseconds. This is not a hypothetical -- it is the single most common way a home-made benchmark produces a gloriously fast and completely fictional number.

black_box: hiding values from the optimizer

The fix for the deletion problem is std::hint::black_box. It is a function the optimizer treats as an opaque sink: it must assume the value passed in could be used in some way it cannot see, so it cannot precompute the value away or delete the work that produced it. This is the single most important tool in all of benchmarking:

use std::hint::black_box;
use std::time::Instant;

fn main() {
    let start = Instant::now();
    let mut acc = 0u64;
    for i in 0..1_000_000u64 {
        // black_box(i) forces the optimizer to actually perform each addition
        acc = acc.wrapping_add(black_box(i));
    }
    black_box(acc); // and this forces it to actually keep the final result
    println!("loop took {:?}", start.elapsed());
}

Notice black_box appears in two places, and both matter. Wrapping the input i stops the compiler from folding the whole loop into a closed-form formula (it knows the sum of 0..n, and it will happily substitute it if you let it). Wrapping the output acc stops it from deciding the loop is dead because nobody reads the result. Miss either one and you measure a mirage. criterion wraps your benchmark inputs and outputs in black_box for you automatically, which is precisely why its numbers reflect real work rather than the optimizer's cleverness. Having said that, black_box is a hint, not a guarantee carved in stone -- it prevents the most common optimizations but does not perfectly model a real caller. It is the best tool we have, and it is enough.

Setting up criterion

Doing all of this properly by hand is tedious and easy to get wrong, which is exactly the burden criterion lifts. You add it as a dev-dependency and declare a benchmark harness in Cargo.toml:

# Cargo.toml
[dev-dependencies]
criterion = "0.5"

[[bench]]
name = "my_benchmark"
harness = false        # tell Cargo not to use the built-in bench harness

The harness = false line matters: it tells Cargo to hand the whole show to criterion's own main instead of the unstable built-in #[bench] machinery (which still requires nightly). Benchmark files live in a top-level benches/ directory, right next to src/ and tests/, and you run them with cargo bench.

Writing and reading a criterion benchmark

You give criterion a closure; it warms up, runs many iterations, collects samples, discards outliers, computes a confidence interval, and saves the result so the next run can tell you "5% faster" or "12% slower":

// benches/my_benchmark.rs -- requires the `criterion` crate: shown for illustration, not compiled locally
use criterion::{black_box, criterion_group, criterion_main, Criterion};

fn fib(n: u64) -> u64 {
    if n < 2 { n } else { fib(n - 1) + fib(n - 2) }
}

fn bench_fib(c: &mut Criterion) {
    c.bench_function("fib 20", |b| b.iter(|| fib(black_box(20))));
}

criterion_group!(benches, bench_fib);
criterion_main!(benches);

The b.iter(...) closure is the hot loop criterion times; everything around it is measurement machinery. Run cargo bench and you get output shaped like this:

fib 20                  time:   [21.234 us 21.301 us 21.379 us]
                        change: [-1.8672% -0.9214% +0.0431%] (p = 0.08 > 0.05)
                        No change in performance detected.
Found 7 outliers among 100 measurements (7.00%)

Learning to read this is the real skill. The three numbers in time are the lower bound, the best point estimate, and the upper bound of a 95% confidence interval -- so the honest way to quote it is "about 21.3 microseconds", not "21.301", because the last digits are noise. The change line compares against the previous saved run (criterion stores results under target/criterion/): here the middle estimate dropped 0.92%, but the interval straddles zero and the p-value of 0.08 is above 0.05, so criterion correctly reports no statistically significant change. That p-value discipline is the whole point -- it stops you celebrating a "2% speedup" that is really just Tuesday's machine being in a slightly better mood than Monday's. The outlier line is diagnostic: a handful of outliers is normal (an OS interrupt landed mid-sample); dozens of them means something on your machine is contending for the CPU and you should close your browser before trusting the numbers.

Comparing two implementations honestly

The classic question is "which of these two is faster?", and the classic mistake is to time each once and declare a winner. The honest way runs each many times through the same harness, with black_box in place, and compares. Here is the by-hand version so you can see the shape of it without the crate:

use std::time::Instant;

fn sum_iter(n: u64) -> u64 { (0..n).sum() }

fn sum_loop(n: u64) -> u64 {
    let mut s = 0;
    let mut i = 0;
    while i < n { s += i; i += 1; }
    s
}

fn time<F: Fn() -> u64>(label: &str, f: F) {
    let start = Instant::now();
    for _ in 0..1000 { std::hint::black_box(f()); }
    println!("{label:>9}: {:?}", start.elapsed() / 1000); // average per call
}

fn main() {
    time("iter", || sum_iter(black_box(100_000)));
    time("loop", || sum_loop(black_box(100_000)));
    // usually near-identical: the optimizer lowers both to the same machine code
}

use std::hint::black_box;

That last comment is a genuine and slightly humbling lesson: idiomatic iterator code and a hand-rolled while loop typically compile to the same machine code, so the "for performance I'll drop down to a manual loop" instinct is, more often than not, superstition. When two versions time the same, pick the one a human reads more easily. Nota bene: criterion has a dedicated benchmark_group API for exactly this A/B comparison, which lines the two functions up on one plot so the overlap (or lack of it) is obvious at a glance.

Measuring across input sizes

A single data point tells you nothing about how an algorithm scales. Measure across a range of sizes and the growth shape appears -- linear, quadratic, logarithmic -- which is usually what you actually care about:

use std::time::Instant;

fn work(n: u64) -> u64 {
    (0..n).map(|x| x.wrapping_mul(31)).sum()
}

fn main() {
    for &size in &[1_000u64, 10_000, 100_000, 1_000_000] {
        let start = Instant::now();
        std::hint::black_box(work(size));
        println!("n={size:>9} took {:?}", start.elapsed()); // ~10x the work -> ~10x the time == linear
    }
}

If ten times the input costs roughly ten times the time, you have linear growth; if it costs a hundred times, you have quadratic, and you have just found the reason your program falls over on real-world data. criterion formalises this with Throughput and benchmark groups that plot time against input size, so a superlinear curve leaps off the chart instead of hiding in a column of numbers. This is how you catch the accidental O(n^2) -- the nested loop, the repeated Vec::remove(0), the contains inside a loop -- that looked innocent on your ten-element test case.

From duration to throughput

A raw duration is hard to compare between machines and between problem sizes. A throughput figure -- elements or bytes per second -- travels far better and is much easier to reason about, because it normalises away the input size:

use std::time::Instant;

fn main() {
    let n: u64 = 5_000_000;
    let start = Instant::now();
    let sum: u64 = (0..n).map(|x| x & 0xff).sum();
    std::hint::black_box(sum);
    let secs = start.elapsed().as_secs_f64();
    let per_sec = n as f64 / secs;
    let mib_per_sec = (n as f64) / (1024.0 * 1024.0) / secs; // one byte per element here
    println!("processed {n} elements in {secs:.4}s = {per_sec:.0} elem/s ({mib_per_sec:.1} MiB/s)");
}

Once you speak in "MiB per second" you can compare a run on your laptop against a run on a server, compare a small buffer against a huge one, and sanity-check against the hardware -- if your byte-crunching loop claims 50 MiB/s on a machine whose memory bandwidth is tens of GiB/s, something is very wrong (probably you are bottlenecked on something other than the work you meant to measure). criterion's group.throughput(Throughput::Bytes(n)) does this conversion for you and prints it alongside the timing.

How Go, Python and C approach it

A glance sideways sharpens the picture, as always. Go, like with fuzzing, folds benchmarking straight into its standard testing package -- no external crate, just a function named BenchmarkXxx and go test -bench:

// bench_test.go -- run with: go test -bench=BenchmarkSum
package main

import "testing"

func BenchmarkSum(b *testing.B) {
    for i := 0; i < b.N; i++ {
        _ = sumIter(100000)   // the framework picks b.N to run long enough to be stable
    }
}

Go's runtime chooses b.N automatically so the benchmark runs long enough to be meaningful, and it has its own testing.B equivalent of black_box concerns (you assign to a package-level sink to defeat the optimizer). It is ergonomic, but it does not give you criterion's statistical rigour -- no confidence intervals, no automatic regression comparison out of the box. Python reaches for timeit, which runs a snippet many times and reports the best of several loops (python -m timeit "sum(range(100000))"); it is fine for micro-questions but has no notion of the compiler deleting your code, because there is no such compiler. C and C++ have no standard benchmarking at all -- the serious tool is Google Benchmark, which pointedly ships a benchmark::DoNotOptimize(x) function that is exactly our black_box, invented for the exact same reason. That the C++ world independently arrived at the same primitive should tell you how fundamental the optimizer-deletion problem really is. Rust's criterion sits at the rigorous end of this spectrum: statistics, outlier detection, and regression tracking built in, at the cost of a little more setup than Go's batteries-included approach.

Wrapping up

So here is the whole picture. A single Instant measurement lies to you in two ways: it is one noisy sample, and the optimizer may have deleted the code you meant to time. black_box cures the deletion by making values opaque to the optimizer -- wrap both the input and the output. criterion cures the noise by taking hundreds of samples, computing a confidence interval, detecting outliers, and comparing against previous runs so it can tell you, with a straight statistical face, whether a change is real or imaginary. Read its output as "about 21 microseconds, no significant change", not as a string of false-precision digits. Compare implementations through the same harness rather than eyeballing single runs, measure across input sizes to see the growth curve, and quote throughput so your numbers travel between machines. Above all: measure, do not guess -- numbers routinely contradict intuition, and an honest benchmark is worth more than any amount of confident reasoning about what should be fast.

We have now built up a serious toolkit -- error handling, three flavours of testing, and honest measurement -- and it is starting to strain the single-crate project we have quietly been living in this whole time. Real programs are rarely one crate; they are a library, a binary that uses it, a set of benchmarks, maybe a few internal helper crates, all built and versioned together. Next time we look at how Cargo lets you organise several crates that live and build as one, which is the natural next step now that your projects have tests, benches, and enough moving parts to deserve some structure ;-)

Exercises

  1. Time sort versus sort_unstable on the same large vector of random u64s, averaging over many runs with your own Instant-based timing harness. Remember to black_box the vector before each sort (and re-clone it, since sorting mutates in place) so you measure the sort and not a no-op on an already-sorted slice.
  2. Run a benchmark body once with black_box around the result and once without it, for a function whose result you otherwise discard. Report both timings and explain, in one sentence, why the version without black_box is suspiciously fast.
  3. Measure a function across four input sizes (1k, 10k, 100k, 1M) and print the time for each. State from the numbers alone whether the growth looks linear or quadratic, then compute and print throughput in MiB/s for the largest size.

Bedankt voor het lezen, en tot de volgende keer! ;-)

@scipio

stem stemsocial steemstem rust programming
0
0
0.000
0 comments