Re:Optimizating Rabin-Karp Hashing
by stabbles on Saturday March 09, 2024 @03:52AM
(#39650418)
Regarding "A final optimization", there's another way:
`_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. So you're counting -1, -2, -3, etc.
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:
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
Re:Optimizating Rabin-Karp Hashing
by namibj on Saturday March 09, 2024 @12:39PM
(#39653296)
8bit permutations are part of GF-NI; you select which source bits to XOR together for each output bit, and for each output bit whether to start with a 0 or a 1.
`_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. So you're counting -1, -2, -3, etc.
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: