3 ms·
It's true that you can use AES instructions now on some computers, bit I honestly don't see why you'd use a heuristic hash (even if cryptographic) when you can
by thomasahle 23d ago
It's true that you can use AES instructions now on some computers, bit I honestly don't see why you'd use a heuristic hash (even if cryptographic) when you can get provable guarantees with k-wise independent hashing. Our paper makes these even faster than they already were.
See section 5.7 and 5.8 in the paper for experiments against other hashes.
- vlovich123 23d agoYou benchmarked a really old heuristic hash in Murmur and xxh64. xxh3 is ~1.6x to 1.8x faster than xxh64 - extrapolating that to 5.7 in your paper puts it at ~18-27% faster. WyHash and UMash sometimes report faster numbers. Even xxh3 isn't the cutting edge - gxhash (~1.8x faster) and aesni (~1.5x faster) use AES instructions. Compared to your approach that perf disparity should grow to ~30-40%. Hopefully that answers your question about why someone might still choose to use heuristic hashing rather than k-wise independent hashing when collision resistance isn't critical.
- thomasahle 22d ago> Hopefully that answers your question about why someone might still choose to use heuristic hashing Not really. Our method is also 2x faster than xxh3. Sure, AES make the heuristic hashes harder to break, but they still provide (1) slower performance, (2) no guarantees.