Intersted in a comparison benchmark?

[eadf]

I recently wrote a benchmark so see if i should use a HashSet or a Vob to keep track of some 10000 indices.

use std::collections::HashSet;
use criterion::{black_box, criterion_group, criterion_main, Criterion};
use rand::prelude::*;

const SIZE: usize = 10000;

#[cfg(test)]
fn vob_vs_hashset_bench(c: &mut Criterion) {
    // Generate 10000 random (seeded) points
    let mut rng: StdRng = SeedableRng::from_seed([42; 32]);
    let mut points = Vec::<usize>::new();
    for i in 0..SIZE {
        points.push(i);
    }
    points.shuffle(&mut rng);

    c.bench_function("HashSet Insert and Lookup", |b| {
        b.iter(|| {
            let mut hash_set = HashSet::new();
            // set half of the set
            for point in points.iter().skip(SIZE/2) {
                black_box(hash_set.insert(point));
            }

            for point in &points {
                black_box(hash_set.contains(point));
            }
        })
    });

    c.bench_function("Vob Insert and Lookup", |b| {
        b.iter(|| {
            let mut vob: vob::Vob<u32> = vob::Vob::new_with_storage_type(SIZE);
            vob.resize(SIZE, false);

            // set half of the vob to true
            for point in points.iter().skip(SIZE/2) {
                black_box(vob.set(*point, true));
            }

            for point in &points {
                black_box(vob[*point]);
            }
        })
    });
}

criterion_group!(benches, vob_vs_hashset_bench);
criterion_main!(benches);

I did not expect the Vob to be more than 20 times faster under these specific conditions:

     Running benches/vob_vs_hashset.rs (target/release/deps/vob_vs_hashset-cffc05ea033ccce1)
HashSet Insert and Lookup
                        time:   [259.60 µs 260.00 µs 260.41 µs]
                        change: [-0.0723% +0.1207% +0.3150%] (p = 0.21 > 0.05)
                        No change in performance detected.
Found 4 outliers among 100 measurements (4.00%)
  1 (1.00%) low severe
  3 (3.00%) low mild

Vob Insert and Lookup   time:   [10.050 µs 10.052 µs 10.056 µs]
                        change: [-0.0235% +0.0260% +0.0740%] (p = 0.31 > 0.05)
                        No change in performance detected.
Found 19 outliers among 100 measurements (19.00%)
  1 (1.00%) low severe
  1 (1.00%) low mild
  8 (8.00%) high mild
  9 (9.00%) high severe

Using something like AHashSet cuts the hashset times in half, but it still can't be compared to a vob. But then again, maybe the test is a bit skewed as the CPU can keep the entire vob in registers during the test.

Do you want a PR for this?

[ltratt]

Thanks for this -- I'm glad to hear that Vob is giving you good performance!

I'd certainly welcome more benchmarks in the benches directory https://github.com/softdevteam/vob/tree/master/benches. That said, I've noticed a) that we're not doing `cargo bench in CI and b) there are build errors. Mea culpa! I'll raise a PR to fix them, as that will otherwise make adding new benchmarks for you a bit tricky.

[eadf]

Ok, i'll come back with a PR later then

[ltratt]

I've raised https://github.com/softdevteam/vob/pull/70 (I've not used criterion before, so I might not have done it correctly).