4 ms·
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 deno
by PeterisP 10y ago
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.
- MaulingMonkey 10y agoIf you want to see what the magic looks like for yourself: https://godbolt.org/g/5LZy2t https://godbolt.org/g/5LZy2t
- Sharlin 10y agoYep, 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.
- flamedoge 10y agoIs this from r=n-x*711; x=n/711 done via long binary division?
- pwdisswordfish 10y agoNot quite. See https://zneak.github.io/fcd/2017/02/19/divisions.html https://zneak.github.io/fcd/2017/02/19/divisions.html — it was posted here some time ago.
- tehwalrus 10y agoIs 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.
- gpderetta 10y agoIIRC that only work if a%b==0 otherwise the general division trick is more complex.
- caf 10y agoYes, you are correct - multiplying by the integer inverse only works for dividends that are an integer multiple of the divisor.
- tomsmeding 10y agoIt 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.
- tehwalrus 10y agoYes 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.
- PeterisP 10y agoAnd 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.
- minimax 10y agoAny 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.
- rurban 10y agoBut 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 https://github.com/lemire/fastrange There's no need for a slow modulo.
- antirez 10y agoRelated 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.
- gpderetta 10y agocareful, 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).
- antirez 10y agoTrue, multiplication latency is a big high, 4 clocks basically in most recent Intel processors: https://software.intel.com/sites/default/files/managed/9e/bc/64-ia-32-architectures-optimization-manual.pdf 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.
- bodyfour 10y agoIf you're interested in learning more: * Check out libdivide: http://libdivide.com/ 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
- csl 10y agoThere seems to be a preprint on that chapter from here: http://www.hackersdelight.org/divcMore.pdf http://www.hackersdelight.org/divcMore.pdf I recommend the book as well, it's got a lot of really awesome tricks!
- torrent-of-ions 10y agoThat'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).
- gpderetta 10y agoThe 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.
- kwillets 10y agoIt'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.