heapsort benchmarks (rust)

bench.rs

#![feature(test)]

use criterion::{criterion_group, criterion_main, Criterion};
use rand::distributions::Standard;
use rand::{thread_rng, Rng};

pub fn heapsort<T, F>(v: &mut [T], mut is_less: F)
where
    F: FnMut(&T, &T) -> bool,
{
    // This binary heap respects the invariant `parent >= child`.
    let mut sift_down = |v: &mut [T], mut node| {
        loop {
            // Children of `node`:
            let left = 2 * node + 1;
            let right = 2 * node + 2;

            // Choose the greater child.
            let greater = if right < v.len() && is_less(&v[left], &v[right]) {
                right
            } else {
                left
            };

            // Stop if the invariant holds at `node`.
            if greater >= v.len() || !is_less(&v[node], &v[greater]) {
                break;
            }

            // Swap `node` with the greater child, move one step down, and continue sifting.
            v.swap(node, greater);
            node = greater;
        }
    };

    // Build the heap in linear time.
    for i in (0..v.len() / 2).rev() {
        sift_down(v, i);
    }

    // Pop maximal elements from the heap.
    for i in (1..v.len()).rev() {
        v.swap(0, i);
        sift_down(&mut v[..i], 0);
    }
}

pub fn heapsortv1<T, F>(v: &mut [T], mut is_less: F)
where
    F: FnMut(&T, &T) -> bool,
{
    // This binary heap respects the invariant `parent >= child`.
    let mut sift_down = |v: &mut [T], mut node| {
        loop {
            // Children of `node`.
            let mut child = 2 * node + 1;
            if child >= v.len() {
                break;
            }

            // Choose the greater child.
            if child + 1 < v.len() && is_less(&v[child], &v[child + 1]) {
                child += 1;
            }

            // Stop if the invariant holds at `node`.
            if !is_less(&v[node], &v[child]) {
                break;
            }

            // Swap `node` with the greater child, move one step down, and continue sifting.
            v.swap(node, child);
            node = child;
        }
    };

    // Build the heap in linear time.
    for i in (0..v.len() / 2).rev() {
        sift_down(v, i);
    }

    // Pop maximal elements from the heap.
    for i in (1..v.len()).rev() {
        v.swap(0, i);
        sift_down(&mut v[..i], 0);
    }
}

fn gen_ascending(len: usize) -> Vec<u64> {
    (0..len as u64).collect()
}

fn gen_descending(len: usize) -> Vec<u64> {
    (0..len as u64).rev().collect()
}

fn gen_random(len: usize) -> Vec<u64> {
    let rng = thread_rng();
    rng.sample_iter(&Standard).take(len).collect()
}

fn gen_mostly_ascending(len: usize) -> Vec<u64> {
    let mut rng = thread_rng();
    let mut v = gen_ascending(len);
    for _ in (0usize..).take_while(|x| x * x <= len) {
        let x = rng.gen::<usize>() % len;
        let y = rng.gen::<usize>() % len;
        v.swap(x, y);
    }
    v
}

fn gen_mostly_descending(len: usize) -> Vec<u64> {
    let mut rng = thread_rng();
    let mut v = gen_descending(len);
    for _ in (0usize..).take_while(|x| x * x <= len) {
        let x = rng.gen::<usize>() % len;
        let y = rng.gen::<usize>() % len;
        v.swap(x, y);
    }
    v
}

fn gen_big_random(len: usize) -> Vec<[u64; 16]> {
    let rng = thread_rng();
    rng.sample_iter(&Standard)
        .map(|x| [x; 16])
        .take(len)
        .collect()
}

fn gen_big_ascending(len: usize) -> Vec<[u64; 16]> {
    (0..len as u64).map(|x| [x; 16]).take(len).collect()
}

fn gen_big_descending(len: usize) -> Vec<[u64; 16]> {
    (0..len as u64).rev().map(|x| [x; 16]).take(len).collect()
}

macro_rules! sort_bench {
    ($name:ident, $gen:expr, $len:expr) => {
        fn $name(c: &mut Criterion) {
            c.bench_function(stringify!($name), |b| b.iter(|| sortboost(&mut $gen($len))));
        }
    };
}

pub fn sort<T>(v: &mut [T])
where
    T: Ord,
{
    heapsort(v, |a, b| a.lt(b));
}

pub fn sortboost<T>(v: &mut [T])
where
    T: Ord,
{
    heapsortv1(v, |a, b| a.lt(b));
}

sort_bench!(sort_small_random, gen_random, 10);
sort_bench!(sort_small_ascending, gen_ascending, 10);
sort_bench!(sort_small_descending, gen_descending, 10);

sort_bench!(sort_small_big_random, gen_big_random, 10);
sort_bench!(sort_small_big_ascending, gen_big_ascending, 10);
sort_bench!(sort_small_big_descending, gen_big_descending, 10);

sort_bench!(sort_medium_random, gen_random, 100);
sort_bench!(sort_medium_ascending, gen_ascending, 100);
sort_bench!(sort_medium_descending, gen_descending, 100);

sort_bench!(sort_large_random, gen_random, 10000);
sort_bench!(sort_large_ascending, gen_ascending, 10000);
sort_bench!(sort_large_descending, gen_descending, 10000);
sort_bench!(sort_large_mostly_ascending, gen_mostly_ascending, 10000);
sort_bench!(sort_large_mostly_descending, gen_mostly_descending, 10000);

sort_bench!(sort_large_big_random, gen_big_random, 10000);
sort_bench!(sort_large_big_ascending, gen_big_ascending, 10000);
sort_bench!(sort_large_big_descending, gen_big_descending, 10000);

criterion_group!(
    benches,
    sort_small_random,
    sort_small_ascending,
    sort_small_descending,
    sort_small_big_random,
    sort_small_big_ascending,
    sort_small_big_descending,
    sort_medium_random,
    sort_medium_ascending,
    sort_medium_descending,
    sort_large_random,
    sort_large_ascending,
    sort_large_descending,
    sort_large_mostly_ascending,
    sort_large_mostly_descending,
    sort_large_big_random,
    sort_large_big_ascending,
    sort_large_big_descending
);
criterion_main!(benches);