Regarding "A final optimization", there's another way:<p>`_mm256_cmpeq_epi32` produces `0xFFFFFFFF`, the article suggests shifting to produce a `1` and then add.<p>Instead you can interpret `0xFFFFFFFF` as negative one, and subtract. That saves a shift.<p>Flip the sign when accumulating.<p>In general I think this is a pretty common counting trick. I don't think those shift operations even exists for epi8, so there you really need to use it to avoid reduction to a narrow register. Also, in the case of epi8 you need to deal with overflow, so the pattern is like this in pseudo code:<p><pre><code> v[1:32] = 0
total = 0
for j = 0 to N / 256
for i = 0 to 255
v[1:32] -= cmpeq(..., ...)
end
total += sum(v)
end</code></pre>
Short related discussion a month ago: <a href="https://news.ycombinator.com/item?id=39254176">https://news.ycombinator.com/item?id=39254176</a>
I wonder what a designed-for-SIMD rolling hash would look like. Like—just a trivial toy experiment—suppose hash ↤ (hash * input[j]) << 1. That's a (very crappy) rolling-hash function with a window size of sizeof(hash). It's also algebraically equivalent to hash ↤ hash * (input[j] << 1), which is a parallelizable horizontal-product over the input bytevector. This shows that you can keep the "rolling window" property, without the "evaluates serially from left-to-right" requirement: it's possible to rearrange things algebraically so that the "folding" step can be evaluated in any order.<p>Are there nontrivial constructions with this property?
Are there actually practical cases where Rabin-Karp hashing is what dominates the running time of an application? The naive implementation already gives you 0.75 GB/s. Seems pretty fast.