sdleffler / qp-trie-rs

An idiomatic and fast QP-trie implementation in pure Rust.
Mozilla Public License 2.0
95 stars 24 forks source link

Benchmarks are outdated #29

Open YXL76 opened 2 years ago

YXL76 commented 2 years ago

The current stdlib HashMap is a wrapper for hashbrown. It uses AHash which is much faster than the previous SipHash.

QP-tries are as fast or a bit faster as Rust's HashMap with the default hasher

Therefore, This may no longer be right.

erikbrinkman commented 1 year ago

from benchmarks on my machine it is indeed the case that the standard hashmap has a faster get for the 4 byte keys that the benchmark uses, although probably benching on only "random" 4 byte keys is not a great exemplar.

For reference, my numbers:

running 10 tests
test bench_btreemap_get      ... bench:  85,723,309 ns/iter (+/- 13,328,158)
test bench_btreemap_insert   ... bench:  87,270,192 ns/iter (+/- 49,520,128)
test bench_exotrie_get       ... bench: 112,000,292 ns/iter (+/- 27,809,933)
test bench_exotrie_insert    ... bench: 127,144,570 ns/iter (+/- 29,359,885)
test bench_fnvhashmap_get    ... bench:  11,980,899 ns/iter (+/- 23,992,529)
test bench_fnvhashmap_insert ... bench:  13,185,669 ns/iter (+/- 14,332,943)
test bench_hashmap_get       ... bench:  86,086,036 ns/iter (+/- 65,197,517)
test bench_hashmap_insert    ... bench:  45,732,973 ns/iter (+/- 10,448,344)
test bench_trie_get          ... bench: 107,859,358 ns/iter (+/- 34,338,961)
test bench_trie_insert       ... bench: 104,512,068 ns/iter (+/- 5,628,416)