@@ 0,0 1,528 @@
+//! 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.
+
+use criterion::{black_box, criterion_group, criterion_main, BenchmarkId, Criterion};
+
+use generational_arena as ga;
+use genmap;
+use handy;
+use slotmap;
+use thunderdome;
+
+use oorandom::*;
+
+const KB: usize = 1024;
+const SIZES: [usize; 3] = [KB, 4 * KB, 16 * KB];
+
+// TODO: The bounds involved in this may not be correct.
+fn shuffle<T>(rng: &mut Rand64, slice: &mut [T]) {
+ for i in (0..slice.len()).rev() {
+ let j = rng.rand_range(0..(i as u64)) as usize;
+ slice.swap(j, i);
+ }
+}
+
+macro_rules! generate_insert_remove {
+ ($group:expr,$size:expr,$name:expr,$init:expr) => {
+ $group.bench_with_input(BenchmarkId::new($name, $size), $size, |b, &size| {
+ let rng = &mut Rand64::new(4);
+ let map = &mut $init;
+ b.iter(|| {
+ let keys = &mut vec![];
+ for i in 0..size {
+ keys.push(map.insert(black_box(i)));
+ }
+ shuffle(rng, keys);
+ for i in keys {
+ map.remove(black_box(*i));
+ }
+ })
+ });
+ };
+}
+
+fn insert_and_remove_elems(c: &mut Criterion) {
+ let mut group = c.benchmark_group("add_random_remove");
+ for size in SIZES.iter() {
+ generate_insert_remove!(group, size, "genmap", genmap::GenMap::default());
+ /*
+ generate_insert_remove!(group, size, "slotmap", slotmap::SlotMap::default());
+ generate_insert_remove!(
+ group,
+ size,
+ "slotmap_dense",
+ slotmap::DenseSlotMap::default()
+ );
+ */
+ generate_insert_remove!(group, size, "handy", handy::HandleMap::default());
+ generate_insert_remove!(group, size, "generational_arena", ga::Arena::new());
+ generate_insert_remove!(group, size, "thunderdome", thunderdome::Arena::new());
+ /*
+ group.bench_with_input(BenchmarkId::new("genmap", size), size, |b, &size| {
+ let map = &mut genmap::GenMap::default();
+ b.iter(|| {
+ let keys = &mut vec![];
+ let rng = &mut Rand64::new(4);
+ for i in 0..size {
+ keys.push(map.insert(black_box(i)));
+ }
+ shuffle(rng, keys.as_mut_slice());
+ for i in keys {
+ map.remove(black_box(*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(black_box(i)));
+ }
+ for i in keys {
+ map.remove(black_box(*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(black_box(i)));
+ }
+ for i in keys {
+ map.remove(black_box(*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(black_box(i)));
+ }
+ for i in keys {
+ map.remove(black_box(*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(black_box(i)));
+ }
+ for i in keys {
+ map.remove(black_box(*i));
+ }
+ });
+ },
+ );
+ group.bench_with_input(BenchmarkId::new("thunderdome", size), size, |b, &size| {
+ let map = &mut thunderdome::Arena::new();
+ b.iter(|| {
+ let keys = &mut vec![];
+ for i in 0..size {
+ keys.push(map.insert(black_box(i)));
+ }
+ for i in keys {
+ map.remove(black_box(*i));
+ }
+ });
+ });
+ */
+ }
+ group.finish();
+}
+
+fn remove_elems(c: &mut Criterion) {
+ let mut group = c.benchmark_group("remove_many");
+ for size in SIZES.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(black_box(*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(black_box(*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(black_box(*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(black_box(*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(black_box(*i));
+ }
+ });
+ },
+ );
+ group.bench_with_input(BenchmarkId::new("thunderdome", size), size, |b, &size| {
+ let map = &mut thunderdome::Arena::default();
+ let keys = &mut vec![];
+ for i in 0..size {
+ keys.push(map.insert(i));
+ }
+ b.iter(|| {
+ for i in keys.iter() {
+ map.remove(black_box(*i));
+ }
+ })
+ });
+ }
+ group.finish();
+}
+
+fn insert_lookup_and_remove_elems(c: &mut Criterion) {
+ let mut group = c.benchmark_group("add_lookup_remove_many");
+ for size in SIZES.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.bench_with_input(BenchmarkId::new("thunderdome", size), size, |b, &size| {
+ let map = &mut thunderdome::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) {
+ let mut group = c.benchmark_group("lookup_many");
+ for size in SIZES.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.bench_with_input(BenchmarkId::new("thunderdome", size), size, |b, &size| {
+ let map = &mut thunderdome::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) {
+ let mut group = c.benchmark_group("bench_iter");
+ for size in SIZES.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.bench_with_input(BenchmarkId::new("thunderdome", size), size, |b, &size| {
+ let map = &mut thunderdome::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!(
+ fancy_benches,
+ insert_and_remove_elems,
+ /*
+ remove_elems,
+ insert_lookup_and_remove_elems,
+ lookup_elems,
+ iterate_full_list,
+ */
+);
+
+criterion_main!(fancy_benches);