Improve Rolling Hashes

[ashvardanian]

In StringZilla a 64-bit rolling hash function is reused for both string hashes and substring hashes, Rabin-style fingerprints. Rolling hashes take the same amount of time to compute hashes with different window sizes, and are fast to update. Those are not however perfect hashes, and collisions are frequent. StringZilla attempts to use SIMD, but the performance is not yet satisfactory. On Intel Sapphire Rapids, the following numbers can be expected for N-way parallel variants.

• 4-way AVX2 throughput with 64-bit integer multiplication (no native support): 0.28 GB/s.
• 4-way AVX2 throughput with 32-bit integer multiplication: 0.54 GB/s.
• 4-way AVX-512DQ throughput with 64-bit integer multiplication: 0.46 GB/s.
• 4-way AVX-512 throughput with 32-bit integer multiplication: 0.58 GB/s.
• 8-way AVX-512 throughput with 32-bit integer multiplication: 0.11 GB/s.

That's extremely slow. Using SIMD and a better scheme, we should be approaching memcpy speeds. Trying alternative rolling hash approaches is the biggest goal for the library in the upcoming releases, so algorithm recommendations would be appreciated!

[ashvardanian]

As discussed with @jandrewrogers, the AES instructions on modern CPUs represent a great opportunity for designing high-throughput hash-functions. A great example is his AquaHash library, using AES extensions, performing one AES-128 round over an entire XMM register in 3 CPU cycles. In AVX-512 the same can be done for the entire ZMM register. This can also be used as a good constituent part of a "block-rolling" hash function, that will process 16 or 64 bytes at a time, as opposed to 1.