5 ms·

This is extremely timely! I was working on SIMD variants for collision-resistant rolling-hash variants in the last few weeks for the v3 release of the StringZil

• cb321 3y ago
  I timed the Buz Hash (https://en.wikipedia.org/wiki/Rolling_hash#Cyclic_polynomial https://en.wikipedia.org/wiki/Rolling_hash#Cyclic_polynomial) at about 1.38 cycles/byte on Skylake generation - but only to "hash in" (i.e. no hash-out). At 6Ghz that should translate to >4.3 GB/s/core. There is a 25 lines of Nim code implementation over at https://github.com/c-blake/ndup/blob/15ec9b0e67750ae1b70761ecd3362db0cf623488/framed.nim#L7 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.)
• cb321 3y ago
  BTW, in the original article I believe the "table based" hashing Dan alludes to is some kind of BuzHash and even mentions it probably being faster. 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.
• RaisingSpear 3y ago
  > So far I couldn't exceed 1 GB/s/core [4], so more research is needed. If you have any ideas - I am all ears! 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