One book cited several times in the preprint of OP is the volume 2 of the famous book series of Knuth, The Art of Computer Programming, notably its section 4.6.4. For readers interested in this kind of results, it is a really interesting gathering of classical theorems and useful tricks to evaluate quickly polynomials.
Show HN: Compute polynomials twice as fast
41–42 of 42 posts
Re: Show HN: Compute polynomials twice as fast
#42Earlier quoted context omitted.
No, though even a hash like xxh3 can be useful when speed is more important than collision resistance. There are many hashes that use more thorough mixing functions than can be achieved with one or a few arithmetic operations (like in universal hashes), thus for them the collision probability reaches the limit imposed by the length of the hash value. Modern CPUs have various instructions that can be exploited in mixi…
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.
You 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.