elli-gf2 0.1.0

use std::hint::black_box;
use std::time::Instant;

use elli_gf2::{
    Strategy, avg_col_weight, generate_banded, generate_er_sparse, generate_ldpc_like,
    reduce_with_strategy,
};

fn median_u128(xs: &mut [u128]) -> u128 {
    xs.sort_unstable();
    let n = xs.len();
    if n % 2 == 0 {
        (xs[n / 2 - 1] + xs[n / 2]) / 2
    } else {
        xs[n / 2]
    }
}

fn bench_case(name: &str, rows: usize, cols: &[Vec<u32>]) {
    let reps = 3usize;

    let mut sparse_times = Vec::with_capacity(reps);
    let mut packed_times = Vec::with_capacity(reps);
    let mut dense_times = Vec::with_capacity(reps);
    let mut auto_times = Vec::with_capacity(reps);

    let sparse_ref = reduce_with_strategy(rows, cols, Strategy::SparseList);
    let packed_ref = reduce_with_strategy(rows, cols, Strategy::PackedCached);
    let dense_ref = reduce_with_strategy(rows, cols, Strategy::DenseMacro);
    let auto_ref = reduce_with_strategy(rows, cols, Strategy::Auto);

    assert_eq!(sparse_ref, packed_ref);
    assert_eq!(sparse_ref, dense_ref);
    assert_eq!(sparse_ref, auto_ref);

    for _ in 0..reps {
        let t0 = Instant::now();
        black_box(reduce_with_strategy(rows, cols, Strategy::SparseList));
        sparse_times.push(t0.elapsed().as_micros());

        let t0 = Instant::now();
        black_box(reduce_with_strategy(rows, cols, Strategy::PackedCached));
        packed_times.push(t0.elapsed().as_micros());

        let t0 = Instant::now();
        black_box(reduce_with_strategy(rows, cols, Strategy::DenseMacro));
        dense_times.push(t0.elapsed().as_micros());

        let t0 = Instant::now();
        black_box(reduce_with_strategy(rows, cols, Strategy::Auto));
        auto_times.push(t0.elapsed().as_micros());
    }

    let sparse_us = median_u128(&mut sparse_times);
    let packed_us = median_u128(&mut packed_times);
    let dense_us = median_u128(&mut dense_times);
    let auto_us = median_u128(&mut auto_times);

    println!(
        "{},{:.3},{},{},{},{},{},{:?}",
        name,
        avg_col_weight(cols),
        sparse_us,
        packed_us,
        dense_us,
        auto_us,
        sparse_ref.rank,
        elli_gf2::recommended_strategy(cols),
    );
}

fn main() {
    println!("family,avg_col_weight,sparse_us,packed_us,dense_us,auto_us,rank,auto_strategy");

    let er = generate_er_sparse(2048, 2048, 0.01, 1337);
    bench_case("er_sparse_2048", 2048, &er);

    let ldpc = generate_ldpc_like(2048, 4096, 6, 7331);
    bench_case("ldpc_like_2048x4096", 2048, &ldpc);

    let banded = generate_banded(2048, 2048, 64, 10, 4242);
    bench_case("banded_2048", 2048, &banded);
}