search

sdleffler / qp-trie-rs

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

Benchmark against FNV hashmaps #8

Closed tapeinosyne closed 7 years ago

tapeinosyne commented 7 years ago

Between Fx and FNV, only FNV provides a useful comparison: on my machine, Fx performs only marginally better than SipHash, and FNV handily bests either. Arguably this is an artifact of working with very short keys only (and possibly of the fixed key distribution), and should be addressed at some later time.

The updated results are included in the readme, although strictly speaking "Chromebook Pixel 2.0 running GalliumOS" becomes a white lie. I can amend the patch with your own results if you are feeling zealous enough.

sdleffler commented 7 years ago

"Zealous enough?" I'm always zealous enough.

test bench_btreemap_insert   ... bench: 132,659,398 ns/iter (+/- 29,673,138)
test bench_exotrie_get       ... bench:  62,867,047 ns/iter (+/- 46,904,086)
test bench_exotrie_insert    ... bench:  71,044,302 ns/iter (+/- 27,054,086)
test bench_fnvhashmap_get    ... bench:  21,425,239 ns/iter (+/- 14,735,369)
test bench_fnvhashmap_insert ... bench:  29,832,873 ns/iter (+/- 18,091,472)
test bench_hashmap_get       ... bench:  69,368,166 ns/iter (+/- 21,790,902)
test bench_hashmap_insert    ... bench:  69,711,467 ns/iter (+/- 26,807,672)
test bench_trie_get          ... bench:  57,712,953 ns/iter (+/- 30,994,598)
test bench_trie_insert       ... bench:  67,280,758 ns/iter (+/- 27,402,253)

Wouldn't mind listing the results for your hardware too, though.

tapeinosyne commented 7 years ago

Mh, if we're feeling zealous, I should grumble that the variance on some of those results is rather too high (e.g. fnvhashmap_get […] 21,425,239 ns/iter (+/- 14,735,369)).

Frankly, my own preference would be to use results with reasonable variance and jilt any concrete reference to hardware or compiler: it's given that differing machines and rustc versions will affect benchmarks, and results are mostly offered as a quick comparison anywhow. We can expand the section again after the benchmarks themselves paint a more complete picture of the QP-trie's performance profile.

sdleffler commented 7 years ago

That's fair - in my own defense I tend to thrash this machine a bit. Would you mind removing the machine bit entirely then?