3 ms·
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
by Sharlin 10y ago
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.
- 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.