Estimate asymptotic complexity from benchmarks over a range of input sizes

[gnzlbg]

I'd like to be able to parametrize benchmarks by input size, pass criterion a size range, and have criterion run tests for it.

Ideally, I'd like to configure the step size:

• linear: [0, 10) with step of 2: 0, 2, 4, 6, 8
• logarithimc: [0, 1000]: 1, 10, 100, 1000

It would be cool if criterion could have a way, of given a range, determine the minimum number of inputs to measure to get a performance curve with a bounded error tolerance.

That is, given my benchmark function f, an interval [a, b], and the time it takes for f to run for a given input i: Delta_t(f(i)), compute an approximation to this called g (e.g. a polynom, wavelet, fourier series, piece-wise linear function, ...) such that |Delta_t(f(x)) - g(x)| <= C in [a, b] where C is an upper bound on the approximation error.

Another cool thing would be if given the set of steps, criterion would try to fit the results using a linear function (N), logarithmic (logN), logarithmic times linear (NlogN), quadratic (N^2), cubic (N^3), ... and return which of these functions fit the results best.

This could be a way to, for example, estimate the algorithmic complexity of a function empirically.

[bheisler]

Thanks for the suggestion.

You can currently provide custom inputs using bench_function_with_inputs, so you could provide a range of input sizes yourself.

As for estimating performance curves - although that would be cool, I think that might be out of scope for Criterion.rs, at least for now. In the future, I might consider making it so that custom analyses and reports and the like can be added by external crates, though that isn't a priority right now.

[gnzlbg]

FWIW Google Benchmark estimates asymptotic complexity:

• https://github.com/google/benchmark
• https://github.com/google/benchmark/blob/master/src/complexity.cc