genmap 1.0.3

//! Do NOT trust these benchmarks!
//!
//! They are quite crude and I made them mainly to learn how to use
//! `criterion.rs`.  They may be interesting, maybe even slightly
//! useful, but do not take them as authorative.

#[macro_use]
extern crate criterion;

use criterion::black_box;
use criterion::BenchmarkId;
use criterion::Criterion;

use genmap;
use handy;
use slotmap;
use generational_arena as ga;

fn insert_elems(c: &mut Criterion) {
    static KB: usize = 1024;

    let mut group = c.benchmark_group("add_many");
    for size in [KB, 2 * KB, 4 * KB, 8 * KB, 16 * KB].iter() {
        group.bench_with_input(BenchmarkId::new("genmap", size), size, |b, &size| {
            b.iter(|| {
                let map = &mut genmap::GenMap::default();
                for i in 0..size {
                    map.insert(i);
                }
            });
        });

        group.bench_with_input(BenchmarkId::new("slotmap", size), size, |b, &size| {
            b.iter(|| {
                let map = &mut slotmap::SlotMap::new();
                for i in 0..size {
                    map.insert(i);
                }
            });
        });

        group.bench_with_input(BenchmarkId::new("slotmap_dense", size), size, |b, &size| {
            b.iter(|| {
                let map = &mut slotmap::dense::DenseSlotMap::new();
                for i in 0..size {
                    map.insert(i);
                }
            });
        });

        group.bench_with_input(BenchmarkId::new("handy", size), size, |b, &size| {
            b.iter(|| {
                let map = &mut handy::HandleMap::new();
                for i in 0..size {
                    map.insert(i);
                }
            });
        });
        group.bench_with_input(BenchmarkId::new("generational_arena", size), size, |b, &size| {
            b.iter(|| {
                let map = &mut ga::Arena::new();
                for i in 0..size {
                    map.insert(i);
                }
            });
        });
    }
    group.finish();
}

fn insert_and_remove_elems(c: &mut Criterion) {
    static KB: usize = 1024;

    let mut group = c.benchmark_group("add_remove_many");
    for size in [KB, 2 * KB, 4 * KB, 8 * KB, 16 * KB].iter() {
        group.bench_with_input(BenchmarkId::new("genmap", size), size, |b, &size| {
            let map = &mut genmap::GenMap::default();
            b.iter(|| {
                let keys = &mut vec![];
                for i in 0..size {
                    keys.push(map.insert(i));
                }
                for i in keys {
                    map.remove(*i);
                }
            })
        });

        group.bench_with_input(BenchmarkId::new("slotmap", size), size, |b, &size| {
            let map: &mut slotmap::SlotMap<slotmap::DefaultKey, usize> =
                &mut slotmap::SlotMap::default();
            b.iter(|| {
                let keys = &mut vec![];
                for i in 0..size {
                    keys.push(map.insert(i));
                }
                for i in keys {
                    map.remove(*i);
                }
            });
        });

        group.bench_with_input(BenchmarkId::new("slotmap_dense", size), size, |b, &size| {
            let map = &mut slotmap::dense::DenseSlotMap::default();
            b.iter(|| {
                let keys: &mut Vec<slotmap::DefaultKey> = &mut vec![];
                for i in 0..size {
                    keys.push(map.insert(i));
                }
                for i in keys {
                    map.remove(*i);
                }
            });
        });

        group.bench_with_input(BenchmarkId::new("handy", size), size, |b, &size| {
            let map = &mut handy::HandleMap::default();
            b.iter(|| {
                let keys = &mut vec![];
                for i in 0..size {
                    keys.push(map.insert(i));
                }
                for i in keys {
                    map.remove(*i);
                }
            });
        });
        group.bench_with_input(BenchmarkId::new("generational_arena", size), size, |b, &size| {
            let map = &mut ga::Arena::new();
            b.iter(|| {
                let keys = &mut vec![];
                for i in 0..size {
                    keys.push(map.insert(i));
                }
                for i in keys {
                    map.remove(*i);
                }
            });
        });
    }
    group.finish();
}

fn remove_elems(c: &mut Criterion) {
    static KB: usize = 1024;

    let mut group = c.benchmark_group("remove_many");
    for size in [KB, 2 * KB, 4 * KB, 8 * KB, 16 * KB].iter() {
        group.bench_with_input(BenchmarkId::new("genmap", size), size, |b, &size| {
            let map = &mut genmap::GenMap::default();
            let keys = &mut vec![];
            for i in 0..size {
                keys.push(map.insert(i));
            }
            b.iter(|| {
                for i in keys.iter() {
                    map.remove(*i);
                }
            })
        });

        group.bench_with_input(BenchmarkId::new("slotmap", size), size, |b, &size| {
            let map: &mut slotmap::SlotMap<slotmap::DefaultKey, usize> =
                &mut slotmap::SlotMap::default();
            let keys = &mut vec![];
            for i in 0..size {
                keys.push(map.insert(i));
            }
            b.iter(|| {
                for i in keys.iter() {
                    map.remove(*i);
                }
            });
        });

        group.bench_with_input(BenchmarkId::new("slotmap_dense", size), size, |b, &size| {
            let map = &mut slotmap::dense::DenseSlotMap::default();
            let keys: &mut Vec<slotmap::DefaultKey> = &mut vec![];
            for i in 0..size {
                keys.push(map.insert(i));
            }
            b.iter(|| {
                for i in keys.iter() {
                    map.remove(*i);
                }
            });
        });

        group.bench_with_input(BenchmarkId::new("handy", size), size, |b, &size| {
            let map = &mut handy::HandleMap::default();
            let keys = &mut vec![];
            for i in 0..size {
                keys.push(map.insert(i));
            }
            b.iter(|| {
                for i in keys.iter() {
                    map.remove(*i);
                }
            });
        });

        group.bench_with_input(BenchmarkId::new("generational_arena", size), size, |b, &size| {
            let map = &mut ga::Arena::new();
            let keys = &mut vec![];
            for i in 0..size {
                keys.push(map.insert(i));
            }
            b.iter(|| {
                for i in keys.iter() {
                    map.remove(*i);
                }
            });
        });
    }
    group.finish();
}

fn insert_lookup_and_remove_elems(c: &mut Criterion) {
    static KB: usize = 1024;

    let mut group = c.benchmark_group("add_lookup_remove_many");
    for size in [KB, 2 * KB, 4 * KB, 8 * KB, 16 * KB].iter() {
        group.bench_with_input(BenchmarkId::new("genmap", size), size, |b, &size| {
            let map = &mut genmap::GenMap::default();
            b.iter(|| {
                let keys = &mut vec![];
                for i in 0..size {
                    keys.push(map.insert(i));
                }
                for i in keys.iter() {
                    let _ = black_box(map.get(*i));
                }
                for i in keys {
                    map.remove(*i);
                }
            });
        });

        group.bench_with_input(BenchmarkId::new("slotmap", size), size, |b, &size| {
            let map = &mut slotmap::SlotMap::default();
            b.iter(|| {
                let keys: &mut Vec<slotmap::DefaultKey> = &mut vec![];
                for i in 0..size {
                    keys.push(map.insert(i));
                }
                for i in keys.iter() {
                    let _ = black_box(map.get(*i));
                }
                for i in keys {
                    map.remove(*i);
                }
            });
        });

        group.bench_with_input(BenchmarkId::new("slotmap_dense", size), size, |b, &size| {
            let map = &mut slotmap::dense::DenseSlotMap::default();
            b.iter(|| {
                let keys: &mut Vec<slotmap::DefaultKey> = &mut vec![];
                for i in 0..size {
                    keys.push(map.insert(i));
                }
                for i in keys.iter() {
                    let _ = black_box(map.get(*i));
                }
                for i in keys {
                    map.remove(*i);
                }
            });
        });

        group.bench_with_input(BenchmarkId::new("handy", size), size, |b, &size| {
            let map = &mut handy::HandleMap::default();
            b.iter(|| {
                let keys = &mut vec![];
                for i in 0..size {
                    keys.push(map.insert(i));
                }
                for i in keys.iter() {
                    let _ = black_box(map.get(*i));
                }
                for i in keys {
                    map.remove(*i);
                }
            });
        });

        group.bench_with_input(BenchmarkId::new("generational_arena", size), size, |b, &size| {
            let map = &mut ga::Arena::new();
            b.iter(|| {
                let keys = &mut vec![];
                for i in 0..size {
                    keys.push(map.insert(i));
                }
                for i in keys.iter() {
                    let _ = black_box(map.get(*i));
                }
                for i in keys {
                    map.remove(*i);
                }
            });
        });
    }
    group.finish();
}

fn lookup_elems(c: &mut Criterion) {
    static KB: usize = 1024;

    let mut group = c.benchmark_group("lookup_many");
    for size in [KB, 2 * KB, 4 * KB, 8 * KB, 16 * KB].iter() {
        group.bench_with_input(BenchmarkId::new("genmap", size), size, |b, &size| {
            let map = &mut genmap::GenMap::default();
            let keys = &mut vec![];
            for i in 0..size {
                keys.push(map.insert(i));
            }
            b.iter(|| {
                for i in keys.iter() {
                    let _ = black_box(map.get(*i));
                }
            });
        });

        group.bench_with_input(BenchmarkId::new("slotmap", size), size, |b, &size| {
            let map = &mut slotmap::SlotMap::default();
            let keys: &mut Vec<slotmap::DefaultKey> = &mut vec![];
            for i in 0..size {
                keys.push(map.insert(i));
            }
            b.iter(|| {
                for i in keys.iter() {
                    let _ = black_box(map.get(*i));
                }
            });
        });

        group.bench_with_input(BenchmarkId::new("slotmap_dense", size), size, |b, &size| {
            let map = &mut slotmap::dense::DenseSlotMap::default();
            let keys: &mut Vec<slotmap::DefaultKey> = &mut vec![];
            for i in 0..size {
                keys.push(map.insert(i));
            }
            b.iter(|| {
                for i in keys.iter() {
                    let _ = black_box(map.get(*i));
                }
            });
        });

        group.bench_with_input(BenchmarkId::new("handy", size), size, |b, &size| {
            let map = &mut handy::HandleMap::default();
            let keys = &mut vec![];
            for i in 0..size {
                keys.push(map.insert(i));
            }
            b.iter(|| {
                for i in keys.iter() {
                    let _ = black_box(map.get(*i));
                }
            });
        });

        group.bench_with_input(BenchmarkId::new("generational_arena", size), size, |b, &size| {
            let map = &mut ga::Arena::new();
            let keys = &mut vec![];
            for i in 0..size {
                keys.push(map.insert(i));
            }
            b.iter(|| {
                for i in keys.iter() {
                    let _ = black_box(map.get(*i));
                }
            });
        });
    }
    group.finish();
}

/// GOOD iteration benchmarks are too much work, since to be interesting they have to be on partially-empty lists.
/// Oh well, not gonna bother this instant!
/// Just be aware that these are pretty darn stupid; don't take them seriously.
fn iterate_full_list(c: &mut Criterion) {
    static KB: usize = 1024;

    let mut group = c.benchmark_group("bench_iter");
    for size in [KB, 2 * KB, 4 * KB, 8 * KB, 16 * KB].iter() {
        group.bench_with_input(BenchmarkId::new("genmap", size), size, |b, &size| {
            let map = &mut genmap::GenMap::default();
            for i in 0..size {
                map.insert(i);
            }
            b.iter(|| {
                for i in map.iter() {
                    let _ = black_box(map.get(i));
                }
            });
        });

        group.bench_with_input(BenchmarkId::new("slotmap", size), size, |b, &size| {
            let map: &mut slotmap::SlotMap<slotmap::DefaultKey, usize> =
                &mut slotmap::SlotMap::default();
            for i in 0..size {
                map.insert(i);
            }
            b.iter(|| {
                for (k, _) in map.iter() {
                    let _ = black_box(map.get(k));
                }
            });
        });

        group.bench_with_input(BenchmarkId::new("slotmap_dense", size), size, |b, &size| {
            let map: &mut slotmap::dense::DenseSlotMap<slotmap::DefaultKey, usize> =
                &mut slotmap::dense::DenseSlotMap::default();
            for i in 0..size {
                map.insert(i);
            }
            b.iter(|| {
                for (k, _) in map.iter() {
                    let _ = black_box(map.get(k));
                }
            });
        });

        group.bench_with_input(BenchmarkId::new("handy", size), size, |b, &size| {
            let map = &mut handy::HandleMap::default();
            for i in 0..size {
                map.insert(i);
            }
            b.iter(|| {
                for (i, _) in map.iter_with_handles() {
                    let _ = black_box(map.get(i));
                }
            });
        });

        group.bench_with_input(BenchmarkId::new("generational_arena", size), size, |b, &size| {
            let map = &mut ga::Arena::new();
            for i in 0..size {
                map.insert(i);
            }
            b.iter(|| {
                for (i, _) in map.iter() {
                    let _ = black_box(map.get(i));
                }
            });
        });
    }
    group.finish();
}

criterion_group!(
    benches,
    insert_elems,
    insert_and_remove_elems,
    remove_elems,
    insert_lookup_and_remove_elems,
    lookup_elems,
    iterate_full_list,
);

criterion_main!(benches);