This is a result from criterion benchmark of the standard library BTreeMap.

Sget/Std/10

It isn’t important, but I am curious to know what might lead to this unusual distribution with two distinct peaks. It doesn’t occur for values of n other than 10. Have you seen similar double-peak results when using criterion?

The benchmark code ( I am comparing my “pstd” implementation against “std” ):

fn bench_sget(c: &mut Criterion) {
    //use rand::Rng;
    //let mut rng = rand::thread_rng();
    let mut group = c.benchmark_group("Sget");
    for n in [10, 20, 50, 100, 200, 500, 1000].iter() {
        let n = *n;
        let mut s = Vec::new();
        for i in 0..n {
            s.push(i.to_string());
        }
        group.bench_function(BenchmarkId::new("Exp", n), |b| {
            let mut map = pstd::collections::BTreeMap::new();
            for i in 0..n {
                map.insert(i.to_string(), i.to_string());
            }
            b.iter(|| {
                for i in 0..n {
                    /* let ri = rng.gen::<usize>() % n; */
                    assert!(map.get(&s[i]).unwrap() == &s[i]);
                }
            })
        });
        group.bench_function(BenchmarkId::new("Std", n), |b| {
            let mut map = std::collections::BTreeMap::new();
            for i in 0..n {
                map.insert(i.to_string(), i.to_string());
            }
            b.iter(|| {
                for i in 0..n {
                    /* let ri = rng.gen::<usize>() % n; */
                    assert!(map.get(&s[i]).unwrap() == &s[i]);
                }
            })
        });
    }
    group.finish();
}

This is the result for Sget/Exp/10 (about twice as fast as std, with no strange double peak ):

13 posts - 3 participants

Read full topic