Open ashvardanian opened 7 months ago
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.
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.
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!