Crate benchplot

benchplot

benchplot is a utility for benchmarking functions over various input sizes and plotting the results.

Usage

use benchplot::{BenchBuilder, BenchFnArg, BenchFnNamed};
use rand::Rng;

fn main() {
    // Functions to benchmark (with names)
    let functions: Vec<BenchFnNamed<Vec<i32>, Vec<i32>>> = vec![
        (Box::new(bubble_sort), "Bubble Sort"),
        (Box::new(insertion_sort), "Insertion Sort"),
        (Box::new(merge_sort), "Merge Sort"),
    ];

    // For each size, returns an argument to pass to the functions to benchmark
    let argfunc: BenchFnArg<Vec<i32>> = Box::new(|size: usize| {
        let mut rng = rand::thread_rng();
        (0..size).map(|_| rng.gen_range(1..=1000)).collect()
    });

    // Input sizes to test. NOTE: a wider range was used for the image above.
    let sizes: Vec<usize> = (0..15).map(|k| 1 << k).collect();

    // Build a `Bench` instance
    let mut bench = BenchBuilder::new(functions, argfunc, sizes)
        .repetitions(1)
        .parallel(true)
        .assert_equal(true)
        .build()
        .unwrap();

    // Run benchmarks and plot them
    bench
        .run()
        .plot("output.svg")
        .title("Sorting Algorithms")
        .build()
        .expect("Plotting failed");
}

// Bubble Sort: O(n²)
fn bubble_sort(mut a: Vec<i32>) -> Vec<i32> {
    let mut n = a.len();
    while n > 1 {
        let mut np = 0;
        for i in 1..n {
            if a[i - 1] > a[i] {
                a.swap(i - 1, i);
                np = i;
            }
        }
        n = np;
    }
    a
}

// Insertion Sort: O(n²)
fn insertion_sort(mut a: Vec<i32>) -> Vec<i32> {
    let n = a.len();
    for i in 1..n {
        let x = a[i];
        let mut j = i;
        while j > 0 && a[j - 1] > x {
            a[j] = a[j - 1];
            j -= 1;
        }
        a[j] = x;
    }
    a
}

// Merge Sort: O(n log n)
// Based on code from https://en.wikipedia.org/wiki/Merge_sort
fn merge_sort(mut a: Vec<i32>) -> Vec<i32> {
    let len = a.len();
    let mut b = a.clone();
    top_down_split_merge(&mut a, 0, len, &mut b);
    a
}

fn top_down_split_merge(
    b: &mut [i32],
    begin: usize,
    end: usize,
    a: &mut [i32],
) {
    if end - begin <= 1 {
        return;
    }
    let middle = (end + begin) / 2;
    top_down_split_merge(a, begin, middle, b);
    top_down_split_merge(a, middle, end, b);
    top_down_merge(b, begin, middle, end, a);
}

fn top_down_merge(
    b: &mut [i32],
    begin: usize,
    middle: usize,
    end: usize,
    a: &mut [i32],
) {
    let mut i = begin;
    let mut j = middle;
    for b_k in b.iter_mut().take(end).skip(begin) {
        if i < middle && (j >= end || a[i] <= a[j]) {
            *b_k = a[i];
            i += 1;
        } else {
            *b_k = a[j];
            j += 1;
        }
    }
}

License

This project is dual-licensed under either the Apache License, Version 2.0 or the MIT License, at your option.

Contributing

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in this project by you shall be dual-licensed as above, without any additional terms or conditions.

Structs

Bench

A structure for benchmarking functions over various input sizes and plotting the results.

BenchBuilder

Builder for creating a Bench instance.

PlotBuilder

Builder for generating a plot of the benchmark results and saving it to a file.

Enums

BenchBuilderError

Error type for BenchBuilder.

PlotBuilderError

Error type for PlotBuilder.

Type Aliases

BenchFn

Type alias for a function to benchmark that takes an argument of type T and returns a result of type R.

BenchFnArg

Type alias for a function accepting a positive integer size and returning input for the benchmarking functions.

BenchFnNamed

Type alias for a tuple containing a BenchFn and a name.