Benchmarks

[eira-fransham]

The probing algorithms used in this crate for IndexMap are pretty rudimentary, and from my pretty unscientific benchmarks (basically just copying the benchmarks from the hashbrown crate, comparing FnvHashMap with the fnv-based hashmap from this crate) it seems like IndexMap is around 15x slower than std::collections::HashMap:

test indexmap::tests::get_remove_insert_heapless ... bench:         665 ns/iter (+/- 263)
test indexmap::tests::get_remove_insert_std      ... bench:          43 ns/iter (+/- 19)

Here are the benchmarks used to get the results above. I compiled with LTO and codegen-units = 1 in order to make sure that std wasn't getting benefits from being inlining where heapless wasn't, most notably around std::hash vs hash32. Of course, these benchmarks are for large maps and smaller maps won't give such pronounced differences. Also, the use of hash32 will probably give a speedup on 32-bit targets that the std map doesn't have access to.

#[bench]
fn get_remove_insert_heapless(b: &mut Bencher) {
    let mut m = crate::FnvIndexMap::<_, _, U1024>::new();

    for i in 1..1001 {
        m.insert(i, i).unwrap();
    }

    let mut k = 1;

    b.iter(|| {
        m.get(&(k + 400));
        m.get(&(k + 2000));
        m.remove(&k);
        m.insert(k + 1000, k + 1000).unwrap();
        k += 1;
    })
}

#[bench]
fn get_remove_insert_std(b: &mut Bencher) {
    let mut m = fnv::FnvHashMap::with_capacity_and_hasher(1024, Default::default());

    for i in 1..1001 {
        m.insert(i, i);
    }

    let mut k = 1;

    b.iter(|| {
        m.get(&(k + 400));
        m.get(&(k + 2000));
        m.remove(&k);
        m.insert(k + 1000, k + 1000);
        k += 1;
    })
}

I'm writing an embedded project that needs a hashmap, and although I do have access to an allocator avoiding it will make my performance more predictable. So I might try to put in a PR improving the performance of IndexMap if I get some spare time to do so.

[japaric]

I last ported Index{Map,Set} from indexmap v0.4.1. It would be good to check if the latest version of the crate has a better probing algorithm. And if you can improve the performance here, I'm sure the indexmap devs would love to have those improvements upstream!

[wangyi-fudan]

just mention wyhash, the fastest high quality conventional hash function: https://github.com/wangyi-fudan/wyhash

[eldruin]

It is worth mentioning that I ported wyhash to Rust and is no-std compatible: wyhash As of version 0.3 only version 1 of the algorithm is available but I will update it soon so you can expect further improvements.

[eira-fransham]

Improving the speed of the hash function will not fix anything, as the std hash map is generic over hash function. The bottleneck is the probing algorithm itself.