6 ms·
Hey, if you're looking for a real-world pragmatic and performant implementation of a theoretically-cool algorithm, my https://github.com/tpn/perfecthash https:/
by trentnelson 3y ago
Hey, if you're looking for a real-world pragmatic and performant implementation of a theoretically-cool algorithm, my https://github.com/tpn/perfecthash https://github.com/tpn/perfecthash project might fit the bill.
It's geared to generating perfect hash tables with the fastest possible lookup/index times (for 32-bit keys), for key sets in the <=100,000 range. (It scales well up to millions of keys, but the solving time takes a lot longer.)
- vlovich123 3y agoMy hunch is that boomphf will outperform and also supports any key type: https://github.com/10XGenomics/rust-boomphf https://github.com/10XGenomics/rust-boomphf Construction is ~10m keys/s on old hardware and uses very few bits per key. Implementation is based on the bbhash paper: https://arxiv.org/abs/1702.03154 https://arxiv.org/abs/1702.03154
- trentnelson 3y agoWhat’s its fastest index function look like in assembly? My MultiplyShiftRX clocks in at like 5 cycles on x64 and 3 cycles on my M1. Mine is optimized for offline table generation so construction speed isn’t really relevant for its primary use.