News for hackers. Stuff that matters.
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.