9 ms·
How do compilers optimize divisions?
- glangdale 10y agoHacker's Delight - an excellent book in general - has an extensive chapter on this, for those who are interested in this topic. http://www.hackersdelight.org/ http://www.hackersdelight.org/
- WalterBright 10y agoHere's how the dmd D compiler does it: https://github.com/dlang/dmd/blob/master/src/backend/divcoeff.c https://github.com/dlang/dmd/blob/master/src/backend/divcoef...
- metaphor 10y agoNoticed Granlund and Montgomery paper[1] cited in comment. Apparently, Warren also cites the same in Hacker's Delight. [1] https://doi.org/10.1145/773473.178249 https://doi.org/10.1145/773473.178249
- Cyph0n 10y agoHe is also known for Montgomery modular multiplication, which is a technique widely used to efficiently implement RSA in hardware.
- amelius 10y agoIt could also be a neat trick around the Intel Pentium's FDIV bug, [1]. [1] https://en.wikipedia.org/wiki/Pentium_FDIV_bug https://en.wikipedia.org/wiki/Pentium_FDIV_bug
- lfowles 10y agoI'm not sure I follow your line of thought given the post is talking integer division and FDIV is floating point division.
- amelius 10y agoWell, you can build a floating point DIV out of an integer DIV, I suppose. Roughly speaking, you divide the (integer) mantissa, and subtract the exponent, and you normalize.
- bbcbasic 10y agoCool. Time to dust off that old PC in the attic.
- Sohcahtoa82 10y agoBecause people are totally going to be concerned about working around a bug that was fixed over 20 years ago.
- raphlinus 10y agoHere's a trick I came across recently which I found quite neat: you can test for divisibility by 3 using (x * 0xaaaaaaab) < 0x55555556. Same concept works for 5 and 15, but sadly not other factors. LLVM does not currently generate that code, but you can make a case it should.
- conistonwater 10y agoThat's pretty cool, although it ought to be mentioned that x must be a uint32. Here's a proof: λ> import Data.SBV λ> prove $ do x <- Data.SBV.sWord32 "x"; return $ (x * 0xaaaaaaab .< 0x55555556) .== (x `sMod` 3 .== 0) Q.E.D. Are you sure it doesn't work for other factors? It seems it works for 7, 9, and 11. λ> sat $ do [a,b] <- sWord16s ["a", "b"]; forAll_ (\x -> (x * a .< b) <=> (x `sMod` 7 .== 0)) Satisfiable. Model: a = 28087 :: Word16 b = 9363 :: Word16 λ> sat $ do [a,b] <- sWord16s ["a", "b"]; forAll_ (\x -> (x * a .< b) <=> (x `sMod` 9 .== 0)) Satisfiable. Model: a = 36409 :: Word16 b = 7282 :: Word16 λ> sat $ do [a,b] <- sWord16s ["a", "b"]; forAll_ (\x -> (x * a .< b) <=> (x `sMod` 11 .== 0)) Satisfiable. Model: a = 35747 :: Word16 b = 5958 :: Word16 So a is equal to 7^{-1} mod 2^16, and b to ceil((2^16-1)/7), etc.
- panic 10y agoWow, that's really cool! Looks like this is a Haskell library: https://hackage.haskell.org/package/sbv-5.15/docs/Data-SBV.html https://hackage.haskell.org/package/sbv-5.15/docs/Data-SBV.h...
- conistonwater 10y agoYes, it's really good! Makes it feasible to "sat first, ask questions later", especially for bit trickery.
- raphlinus 10y agoDuh, you're right on both counts. It should work for any odd divisor, I was just computing the inverse in a dumb way when I tried out other divisors. And I should have stated u32 wrapping arithmetic.
- Someone 10y agoOn this subject, these three blog posts are hard to beat: http://ridiculousfish.com/blog/posts/labor-of-division-episode-i.html http://ridiculousfish.com/blog/posts/labor-of-division-episo... http://ridiculousfish.com/blog/posts/labor-of-division-episode-ii.html http://ridiculousfish.com/blog/posts/labor-of-division-episo... http://ridiculousfish.com/blog/posts/labor-of-division-episode-iii.html http://ridiculousfish.com/blog/posts/labor-of-division-episo... The same author wrote a library for doing this (and more; it also uses bit shifts) at runtime: http://libdivide.com http://libdivide.com Of course, that only makes sense if you know you will do lots of divisions by the same number
- morecoffee 10y agoFrom what I understand, inlining is the key optimization that compilers make to speed up code. Once inlined, the excess computations of a function body can be removed or shortened, based on the calling context. With that in mind, how can the decompiler identify such "magic multiplication" division given that the compiler might mutate the division code at the callsite?
- WalterBright 10y agoRegister allocation is the key to victory.
- qznc 10y agoMy rule of thumb is: If an optimization reduces memory accesses, it is important today. Register allocation fits that pattern, because the alternative is to spill values to memory. Disclaimer: That rule is restricted to fast processors, not low-power embedded stuff. Inlining is not that important for speed itself. It rather is an optimization booster, which makes many other optimization much more effective. If your other optimizations are crap, then inlining will not help much, because the call overhead is not that big.
- WalterBright 10y agoInlining makes for better register allocation :-)
- caf 10y agoThe result of 7233629131 / 137438953472 is 18.999999997649866. This is wrong, the divisor and dividend are the wrong way around. ..and in case anyone else is wondering how those numbers relate to the constant in the code, it's 2^37 / (2938661835 + 2^32)
- jwilk 10y agoIt's been fixed.
- dmichulke 10y agoProbably I'm missing something here: Why can't one just multiply with the inverse of 19 (which can be calc'ed during compile time)?
- jeffasinger 10y agoThis is an unsigned int, so the expectation would be to do integer division, which would not get you the same result as multiplying by the inverse.
- dmichulke 10y agoCouldn't that be addressed via a floor operation afterwards?
- SolarNet 10y agoBecause unless you are on a video card (e.g. doing SIMD) floating point operations are very very expensive.
- adwn 10y agoThat is not true; compare kr7's comment [1]: > On Skylake [...] 32/64-bit floating point multiplication has a 4 cycle latency with a throughput of 2 instructions / cycle. Of course, there are some operations that are very expensive (trigonometric functions, for example), but they're not necessary here, and they're also very expensive on the GPU. [1] https://news.ycombinator.com/item?id=13693749 https://news.ycombinator.com/item?id=13693749
- desdiv 10y agoOn most modern platforms, the cost of each operation, from smallest to largest, is roughly something like this[0]: 1. Bit shifting 2. Integer multiplication 3. Integer division 4. Floating point multiplication The trick in the article works because the cost of 1 + 2 is still smaller than 3. Multiplying with the inverse of 19, a floating point number, wouldn't work because 4 is more costly than 3. [0] http://nicolas.limare.net/pro/notes/2014/12/12_arit_speed/ http://nicolas.limare.net/pro/notes/2014/12/12_arit_speed/
- xelxebar 10y agoIs there a reason compilers don't just use modular inverses and let overflow take care of things? 19 * 678,152,731 = 1 (mod 2^32) 19 * 9,708,812,670,373,448,219 = 1 (mod 2^64) As long as we already know the size of an int Euclid's algorithm should be able to find these inverses if they exist.
- jwilk 10y agoI don't see how finding the modular inverse helps with division. What algorithm do you have in mind?
- SamReidHughes 10y agoThat only works when the value is known to be a multiple of whatever you're dividing by, and they do use that when it is the case, such as for pointer subtraction.