benchmark to find scaling (and prefactor) of a function
I'm working on a function like this:
pub fn bench_power_scaling<G, F, I, O>(mut gen_env: G, f: F, nmin: usize, nmax: usize) -> ScalingStats
where
G: FnMut(usize) -> I,
F: Fn(&mut I) -> O,
{
which will measure the scaling of a function (theusize input). I'd love feedback on the interface as well as to hear whether you would accept a pull request. This is something I've often wished for (for criterion), and that can't efficiently be implemented on top of easybench, since you'd like to thrown all the raw data into the regression to find the scaling prefactor, rather than first regress to find a bunch of times for different N values, and then regress to fit those times to another curve.
One API question is whether we do want to set minimum and maximum N values as I currently do. For some cases (in particular my tiny set), there are ranges of sizes for which the scaling will not be the same. But it does complicate the API, and we could potentially make the generating function reject sizes like:
G: FnMut(usize) -> Option<I>,
or we could just not allow domain restrictions.
Currently, I've got ScalingStats looking like:
/// Statistics for a benchmark run determining the scaling of a function.
#[derive(Debug, PartialEq, Clone)]
pub struct ScalingStats {
pub scaling: Scaling,
pub goodness_of_fit: f64,
/// How many times the benchmarked code was actually run.
pub iterations: usize,
/// How many samples were taken (ie. how many times we allocated the
/// environment and measured the time).
pub samples: usize,
}
/// The timing and scaling results (without statistics) for a benchmark.
#[derive(Debug, PartialEq, Clone)]
pub struct Scaling {
/// The scaling exponent
/// If this is 2, for instance, you have an O(N²) algorithm.
pub exponent: usize,
/// The time, in nanoseconds, per scaled size of the problem. If
/// the problem scales as O(N²) for instance, this is the number
/// of nanoseconds per N².
pub ns_per_scale: f64,
}
where Scaling displays like 0.32ns/N, 0.1ns/N² or 103ns/iter.
Another API question is whether to support logarithmic scaling, in which case we'd have to change Scaling to be able to represent those options. Not too hard, but since I'm not doing anything with log scaling I haven't bothered. Also, I'm not sure the cleanest way to represent that.
The implementation is basically to iterate over "numbers of iters" the same as you currently do, but also to set N equal to the number of iters. Then we do a fit on all the data we are able to collect for each power of N that we want to consider.