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!