cespare / mph

Minimal perfect hashing in Go
MIT License
72 stars 11 forks source link

Switching hash function to xxh3 #3

Open SaveTheRbtz opened 1 year ago

SaveTheRbtz commented 1 year ago

xxh3 is faster than murmur (x86_64):

name          time/op
Murmur/1-8      2.68ns ± 1%
Murmur/4-8      3.45ns ± 1%
Murmur/8-8      4.70ns ± 0%
Murmur/16-8     6.19ns ± 0%
Murmur/32-8     10.6ns ± 0%
Murmur/50-8     16.3ns ± 2%
Murmur/500-8     202ns ± 0%
XXH3/1-8        2.53ns ± 2%
XXH3/4-8        2.51ns ± 2%
XXH3/8-8        2.45ns ± 1%
XXH3/16-8       2.35ns ± 1%
XXH3/32-8       3.16ns ± 0%
XXH3/50-8       4.87ns ± 5%
XXH3/500-8      38.6ns ± 1%

Using it makes mph slightly faster (Intel(R) Xeon(R) CPU @ 2.80GHz, 348454 words):

name      old time/op    new time/op    delta
Table       35.4ns ± 2%    28.4ns ± 3%  -19.70%  (p=0.000 n=10+10)
TableMap    67.8ns ±10%    66.9ns ± 6%     ~     (p=0.481 n=10+10)

Also while here you can consider switching to a generic slices.SortFunc to speed up build. Combined w/ hashing change it amounts for ~13% improvement:

name   old time/op    new time/op    delta
Build     126ms ± 6%     109ms ± 3%  -13.23%  (p=0.000 n=10+10)

I can create pull requests if you are interested: https://github.com/cespare/mph/compare/main...SaveTheRbtz:mph:main%5E

PS. It would be possible to switch to https://github.com/cespare/xxhash if it had an ability to customize seed. That said, zeebo version would likely be faster due to AVX/AVX512 support.

kamikazechaser commented 1 year ago

Looks good.

cespare commented 1 year ago

Sure, feel free to send a PR.