Optimizing Rabin-Karp Hashing(mattsills.github.io)
mattsills.github.io
Optimizing Rabin-Karp Hashing
https://mattsills.github.io/2024/03/02/rabin-karp/
9 comments
Short related discussion a month ago: https://news.ycombinator.com/item?id=39254176
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.
Are there nontrivial constructions with this property?
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.
Compression, synchronization and backup systems often use rolling hash to implement "content-defined chunking", an effective form of deduplication.
In optimized implementations, Rabin-Karp is likely to be the bottleneck. See for instance https://github.com/facebook/zstd/pull/2483 which replaces a Rabin-Karp variant by a >2x faster Gear-Hashing.
In optimized implementations, Rabin-Karp is likely to be the bottleneck. See for instance https://github.com/facebook/zstd/pull/2483 which replaces a Rabin-Karp variant by a >2x faster Gear-Hashing.
I found it to be a good pedagogical tool. In terms of actual use cases, maybe something like rsync'ing a large directory where only a few files have changed? It starts to get pretty contrived though.
Maybe implementing `foo LIKE '%bar%'` in a columnar DB backed by SSDs. Even if you're not strictly CPU-bound, there's a scale where you might care about the power use.
A response to a question posed by Daniel Lemire.
`_mm256_cmpeq_epi32` produces `0xFFFFFFFF`, the article suggests shifting to produce a `1` and then add.
Instead you can interpret `0xFFFFFFFF` as negative one, and subtract. That saves a shift.
Flip the sign when accumulating.
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: