Benchmark (the score of) a randomized local search algorithm in Rust with Criterion

Question

I have a score function to evaluate a local search algorithm whose results vary between seeds. The algorithm is anytime and its runtime is fixed. Even though the Criterion framework generalizes over impl Measurement, I couldn't find a way for it to measure using the score function instead. I'd like to know if it is possible to implement this with Criterion?

I cannot implement the API for Measurement, from https://docs.rs/criterion/latest/criterion/measurement/trait.Measurement.html. Precisely, start(&self) and end(&self, i) does not depend on the output of the algorithm.

Answer 1

MarcoXerox, that is correct. Criterion is not really designed for what you are attempting to do (I think it may make some assumptions that the measurement is proportional to the time of execution). However, I think this should be fairly easy to achieve with iter_custom since it lets you provide the measurement instead of calling start and end . First define a placeholder measurement for your score type.

pub struct Points;

impl Measurement for Points {
    type Intermediate = ();
    type Value = f64;

    fn start(&self) -> Self::Intermediate {
        panic!("value should be manually created")
    }

    fn end(&self, i: Self::Intermediate) -> Self::Value {
        panic!("value should be manually created")
    }

    fn add(&self, v1: &Self::Value, v2: &Self::Value) -> Self::Value {
        v1 + v2
    }

    fn zero(&self) -> Self::Value {
        0.0
    }

    fn to_f64(&self, value: &Self::Value) -> f64 {
        *value
    }

    fn formatter(&self) -> &dyn ValueFormatter {
        &PointsFormatter
    }
}

pub struct PointsFormatter;

impl ValueFormatter for PointsFormatter {
    fn scale_values(&self, _typical_value: f64, _values: &mut [f64]) -> &'static str {
        "points"
    }

    fn scale_throughputs(&self, _typical_value: f64, throughput: &Throughput, values: &mut [f64]) -> &'static str {
        let (n, units) = match throughput {
            Throughput::Bytes(x) => (*x as f64, "points/byte"),
            Throughput::BytesDecimal(x) => (*x as f64, "points/byte"),
            Throughput::Elements(x) => (*x as f64, "points/element"),
        };

        for value in values {
            *value /= n;
        }

        units
    }

    fn scale_for_machines(&self, _values: &mut [f64]) -> &'static str {
        "points"
    }
}

Then just return the value manually as part of iter_custom instead of letting criterion perform the measurement. Just make sure you properly account for the number of iterations being requested.

fn bench(c: &mut Criterion<Points>) {
    c.bench_function("foo", move |b| {
        b.iter_custom(|iters| {
            let total_score: f64 = 0.0;
            for _ in 0..iters {
                let score = black_box(foo());
                total_score += score;
            }
            total_score
        })
    });
}

I believe this should work for your problem.