Hacker News Reader

Comment by PeterisP | Hacker News Reader

I wouldn't ever have thought that replacing the generic integer modulo operation with a switch statement and a modulo operation with a particular hardcoded denominator could possibly cause a performance improvement.

Especially for primes. I can imagine that various power-of-two related values could have some bit-twiddling ways to make them much faster, but assuming that the compiler will be able to improve x mod 711 to something better than using the CPU modulo operation seems weird... but it somehow works.

View on HN

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.

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.

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.

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.

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.

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.

If you're interested in learning more: * Check out libdivide: http://libdivide.com/ * Also, the awesome book "Hacker's Delight" has extensive information about how and why these tricks work. It's the bit-twiddling bible -- probably my favorite programming book I've ever read

There seems to be a preprint on that chapter from here: http://www.hackersdelight.org/divcMore.pdf

I recommend the book as well, it's got a lot of really awesome tricks!

That's very cool... Some years ago I wrote my own multiple-precision arithmetic library. I implemented a lot of it in assembly so that I could access the carry bit and do full-word multiplication etc. I studied GMP and realised that my addition and subtraction were near enough perfect, but multiplication and division were far off. I now see that just because I was way off with division because I simply implemented the long division algorithm and used IDIV for words (and even that was more difficult than the other algorithms).

If you want to see what the magic looks like for yourself:

https://godbolt.org/g/5LZy2t

Related to that, it's incredible how modern CPUs can perform anything in a cycle of clock or less (multiple ops at the same time), but with division. Division is still at ~100 clocks cycles! So it is definitely the first thing to look when optimizing inner loops.

careful, a multiply usually has a latency of 3 or 4 clock cycles; the trick is that the multiply unit is fully pipelined and there are multiple units, so you can start a couple of multiplies every clock cycle. The latency is still relevant if you have low ILP.

Division is hard to fully pipeline; IIRC Skylake can start a new division every 6 clock cycles, but the latency for 32 bit integer division is 19 cycles (which is pretty amazing BTW).

True, multiplication latency is a big high, 4 clocks basically in most recent Intel processors:

https://software.intel.com/sites/default/files/managed/9e/bc...

However 64 bit divisions is terrible at ~100 cycles per 64 bit division. It is true that the 32 bit division is much faster, but now that the target is 64 bit, the 64 bit divisions are very popular. It's something to take in mind when doing fast math... when 32 bits are enough and there are unavoidable divisions, use 32 bits integers.

The Hacker's Delight has a pretty good treatment of the topic on chapter 9.

But the trick in the link shared by jlrubin is more relevant for hash tables.

It's dozens of cycles to do a DIV. On Skylake the various DIV instructions range from 23 to 95 cycles. That's longer than a pipeline stall.

In the case of a switch like this I would try something horrible like a template for each prime, so that the code is inlined.

Reply on news.ycombinator.com