Hacker News Reader

Comment by Sharlin | Hacker News Reader

Yep, there's pretty much a trick for every reasonably small divisor. For instance GCC 4.9 translates division by 711 as follows (dividend in edi):

        mov     eax, edi
        mov     edx, -1202107583
        imul    edx 
        mov     eax, edi
        sar     eax, 31
        add     edx, edi
        sar     edx, 9
        sub     edx, eax
        mov     eax, edi
        imul    edx, edx, 711
        sub     eax, edx

This is, uh, pretty deep magic. Apparently this sequence of ops, including those two imuls, is still faster than a single idiv.

View on HN

And don't forget that you still have a switch statement with multiple branching operations that pick out this code among the various options of hash table size!

This is something where function pointers / overloading would likely have even better performance than direct switching - when the hash table size changes, switch out the function from modulo_by_511 to modulo_by_711.

Any reasonably good optimizing compiler will implement that switch statement as a jump table so it's really just one conditional branch even though it doesn't look like it.

But this compiler will add unneeded bounds checking (3-10% perf. hit). A computed goto table would fix that. (on modern compilers).

Anyway, Lemire's fastrange modulo solved that problem better. https://github.com/lemire/fastrange There's no need for a slow modulo.

Is this the trick where you multiply by the two's-compliment inverse instead of dividing? That was the coolest thing I learned when I spent a few days coding assembly.

I can't see the shift that you normally need after pulling the result out of the overflow register though. My asm is a little rusty though.

It doesn't need the shift because it retrieves the result of the first imul from edx, which contains the upper word of the result. The lower word is placed in eax, which this code completely ignores.

Yes but even in the upper register you still need to lshift by one or two bits depending on the constant IIRC. Five had me shifting by (1 or 2), and seven by (2 or 1) I seem to recall. I can't remember what property of the number determines the size of the shift though.

IIRC that only work if a%b==0 otherwise the general division trick is more complex.

Yes, you are correct - multiplying by the integer inverse only works for dividends that are an integer multiple of the divisor.

Is this from r=n-x*711; x=n/711 done via long binary division?

Not quite. See https://zneak.github.io/fcd/2017/02/19/divisions.html — it was posted here some time ago.

Reply on news.ycombinator.com