How fast is rolling Karp-Rabin hashing?

There is a 25 lines of Nim code implementation over at https://github.com/c-blake/ndup/blob/15ec9b0e67750ae1b70761e... but the charm of the technique / idea of Bob Uzgalis' ("buz") is its extreme simplicity. (That Nim version also uses the ease of computing very statistically independent hashes in parallel for this near duplicate detection idea.) I'm sure you could write your own pronto.

I haven't tried it, but if your CPU L1/L2 cache is big enough, you might be able to get a boost from doing 2-bytes at a time instead of 1 byte at a time. (65536 entries * hash-size per entry =~ maybe as little as 256..512 KiB. Big "IF", though.. since while you can do half as many loops, you will also be waiting a lot more on cache.

(EDIT: and dunno - it may not be as collision resistant as your end-use case needs. Perhaps that's why you qualified that sub-kind of rolling hash being of interest.)

I also just noticed that one of your intended applications is DNA sequences. For a tiny 2-bit AGTC alphabet, you could probably assign random 4..8 byte table codes for a basic size-4 table and then pre-compute the first several "powers" of that table in the same way as suggested in my big "IF" sibling comment here.

To elaborate, every possible sextuplet becomes a table with 2 * 6=2^12=4096 * 8byte entries probably fitting in a 32 KiB CPU L1 cache. Of course, if you are hashing out and then also in 6 basepairs at a time to have 6X fewer loops, then you lose "single base pair granularity" of window sizes. I.e., every window has to be a multiple of 6 basepairs. But for DNA, there may be actual end-user applications where 3 bp (1 codon) is useful and 3X fewer loops is nothing to sneeze at.

You could do the same thing with your current Rabin-Karp with an alphabet mapping table, of course. (A pair of simple arrays taking triplet numbers to/from codon numbers).

Given the sensitivity of optimizations in both approaches to alphabet size, you may profitably improve your API to include alphabet size and possibly alphabet translation tables as parameters.

I don't know much about the space you're working in, but some things I'd point out:

* 32b and 64b SIMD multiplication have very high latency on Intel CPUs (actually, expect multiplication to have high latency in general on any CPU). If you're not using multiple independent chains of zmm registers, performance will suck

* _mm512_set_epi64 with memory sources likely performs poorly. See if you can do full vector loads and swizzle the data into position (i.e. unpack/shuffle operations)

* do you really need to split the string into 4 parts? Can you just use the same "part", but offset each lane by a byte?

* what about CRC64? Like 32/64b multiplication, CLMUL/PMULL instructions tend to have high latency, so might not help on that front, but there may be other benefits