How to benchmark a function with an upper bound on the number of calls

[Luro02]

Right now, I am working on an Array based HashMap. Because Arrays have a fixed size, one can not insert an infinite amount of elements (after N elements the benchmark would crash).

What would be the best way to bench something like this? (Setting BatchSize::NumIterations(u64)?)
I have already read a bit through the book and the documentation, but I seem to have either missed an option or did not understand the documentation correctly.

The BatchSize docs could profit from some kind of example calculations. For example, it is unclear to me what exactly a batch is and how many batches are executed depending on the setting.

BatchSize::SmallInput and BatchSize::LargeInput seem to be used to control how many benchmarks can be run in parallel? (so you do not run into memory issues?), but what is a batch and how many are executed?

I currently have this benchmark, but sometimes random reruns cause a +-5% fluctuations:

const CAPACITY: usize = 3083;

let mut group = c.benchmark_group("insert");
group.sample_size(300);

for elems in [CAPACITY, CAPACITY / 2, CAPACITY / 3, CAPACITY / 4] {
    group.throughput(Throughput::Elements(elems as u64));
    group.bench_with_input(
        // the name of the benchmark group
        BenchmarkId::from_parameter(format!("::ArrayMap({}/{})", elems, CAPACITY)),
        // data passed to the benchmark function
        &elems,
        // benchmark function
        |b, &elems| {
            b.iter_batched(
                || {
                    (
                        (0..elems).zip((0..elems).map(|i| i * 2 + 5)),
                        ArrayMap::<_, _, CAPACITY>::new()
                    )
                },
                |(mut iter, mut map)| {
                    let (k, v) = iter.next().unwrap();
                    map.insert(k, v).unwrap();
                },
                BatchSize::SmallInput,
            );
        },
    );
}
group.finish();

[bheisler]

Hello! Thanks for your patience.

The correct answer is to create a new map with a known state for each iteration. Criterion-rs' statistics assume that each iteration is doing the same work (or at least, that the differences in the work done by each iteration is independent of which iteration it is). Inserting another value into the data structure on each iteration means that future iterations have more work to do (more key collisions, etc.), so the time goes up on each iteration and that will confuse the statistics.

However, it looks as though you've misunderstood, and you already are doing that. iter_batched creates one (iterator, map) pair for each iteration and passes a different one to each iteration of the benchmark. So what you're actually measuring here is the time to insert elems elements into a map, starting with an empty map, not the time to insert one element into a map. The reason it's batched is because it creates potentially thousands of inputs and then consumes them; if the inputs are individually large but the benchmark function is fast it might run out of memory storing all of the inputs to be used. So it proceeds in batches, generating some number of inputs and then consuming them. BatchSize::SmallInput basically means 'the inputs are small, create as many of them as you need' where BatchSize::LargeInput means 'the inputs are large, create only one at a time'. Batch size has nothing to do with parallelism.

BatchSize is intentionally vague because the benchmark author is not able to specifically control the number of iterations - the number of iterations must be generated by Criterion-rs in order for some parts of the statistics to work.

+-5% seems like a pretty typical number for noise in a benchmark, I wouldn't worry about it. If you need greater precision, consider increasing the measurement time or (if you're on Linux) using Iai instead.

[lemmih]

Looks like your issue has been resolved. If this is not the case, feel free to re-open.