Rust (criterion): how to pass mutable reference within bench_with_input()

Question

I am new to Rust and am trying to benchmark sorting algorithms.

The functions take immutable references to a slice (fn sort(&self, slice: &mut [T])).

I am trying to use the criterion crate to benchmark them for different inputs (random vectors of increasing length).

However I cannot figure out how to pass the vectors to the functions as mutable references. I have tried the the fixes suggested by rustc but each generates another error.

The benchmark code is (shortened example to exclude all the functions):

use criterion::{black_box, criterion_group, criterion_main, BenchmarkId, Criterion, Throughput};
use rand::{distributions::Uniform, Rng};
use sorting::*;

fn sorting_benchmarks(c: &mut Criterion) {
    let mut group = c.benchmark_group("Sorting");

    for i in [1, 10, 100].iter() {
        let mut rng = rand::thread_rng();
        let range = Uniform::new(0, 100);
        let nums: Vec<usize> = (0..(*i)).map(|_| rng.sample(&range)).collect();

        let mut v = black_box(nums.to_vec());
        group.bench_with_input(BenchmarkId::new("Bubble Sort {}", i), &v, |b, v| {
            b.iter(|| BubbleSort.sort(v))
        });
    group.finish();
}

The function for BubbleSort.sort is:

impl<T> Sorter<T> for BubbleSort {
    fn sort(&self, arr: &mut [T])
    where
        T: Ord,
    {
        let mut swapped = true;
        while swapped {
            swapped = false;
            for i in 1..arr.len() {
                if arr[i - 1] > arr[i] {
                    arr.swap(i - 1, i);
                    swapped = true;
                }
            }
        }
    }
}

Some examples of the error messages.

First:

error[E0596]: cannot borrow `v` as mutable, as it is not declared as mutable
  --> benches/criterion_bench.rs:16:39
   |
15 |         group.bench_with_input(BenchmarkId::new("Bubble Sort {}", i), &v, |b, v| {
   |                                                                               - help: consider changing this to be mutable: `mut v`
16 |             b.iter(|| BubbleSort.sort(&mut v))
   |                                       ^^^^^^ cannot borrow as mutable

If I do the suggested fix, I still get cannot borrow as mutable.

I have successfully benchmarked the functions using bench_function from the criterion crate. But this does not help me with benchmarking against multiple inputs for comparison.

Answer 1

The direct problem in your code is that you used &v where you needed &mut v. But that's not actually going to work well, and you should not be using bench_with_input for this purpose. (In fact, I'm not sure what bench_with_input is good for — closure captures work just fine.)

The key thing to understand is that Criterion is going to run your benchmarked function many times (when you call iter). If you did arrange to pass a mutable reference to the same vector for each run, that would not be appropriate for benchmarking a sorting algorithm because it means all iterations but the first would receive already-sorted input. When the performance of the algorithm depends on the order of the input, you want a fresh non-sorted vector each time.

When you want to benchmark a function that consumes or mutates input, you use a different Bencher method than iter(). In particular, iter_batched_ref() is most appropriate for benchmarking a sorting algorithm (or any other function which takes a mutable reference and mutates it).

fn sorting_benchmarks(c: &mut Criterion) {
    let mut group = c.benchmark_group("Sorting");

    for i in [1, 10, 100] {
        let mut rng = rand::thread_rng();
        let range = Uniform::new(0, 100);

        group.bench_function(BenchmarkId::new("Bubble Sort {}", i), |b| {
            b.iter_batched_ref(
                || -> Vec<usize> { (0..i).map(|_| rng.sample(&range)).collect() },
                |v| BubbleSort.sort(v),
                BatchSize::SmallInput,
            )
        });
    }
    group.finish();
}

Notice that the input vector is constructed inside of a function passed to iter_batched_ref. iter_batched_ref will call that function several times, then call the function being benchmarked several times to measure it, with a fresh input each time.