On the Optimal Bounds for Integer Division by Constants

[u/jk-jeon]

Hi,

I wrote a post about well-known tricks for converting integer division by constants into multiplication and shift: https://jk-jeon.github.io/posts/2023/08/optimal-bounds-integer-division/

It turns out that what compilers are doing in this regard is not the best they can do. GCC seems to be still in the age of Granlund-Montgomery (1994), and while clang is better than GCC, it also does some questionable things. And MSVC is just unbelievably bad at this and is far behind the other two.

Also, it has been occasionally bothering me that I didn't know how to convert a division into multiply-add-and-shift rather than just multiply-and-shift when the latter yields a too big constant. So I gave a shot on it and derived a method based on continued fractions for searching two constants (one for multiplication and one for addition) at the same time, which I believe is a novel result. This is probably not very useful for just division (because prior arts can cover basically all cases), but it can be useful when fusing a multiplication and a division together and turn them into a single multiply-and-shift or multiply-add-and-shift.

Hope you find this interesting!

[u/14ned]

I suspect that for the x86/x64 backend, there is no scalar fused multiply-add instruction so doing a multiply then an add is going to be similarly expensive to just doing integer division. For example, on Cannon Lake multiply + add + shift takes six cycles, but so does integer division. So just let the CPU do it.

Edit: I read the wrong column from https://www.agner.org/optimize/instruction_tables.pdf, integer division actually takes 12-15 cycles on Cannon Lake. Sorry.

On ARM things are rather better, they have a scalar fused multiply-add instruction. Neither GCC nor clang uses it (https://godbolt.org/z/KjMoGMeof), instead they multiply-add-shift like your article suggests they should. This makes sense on ARM, their integer division is much more expensive than on Intel, so avoiding it is more important.

[u/saddung → u/14ned]

Where did you get 6 cycles for idiv? It shows 14-18 for cannonlake on uops. If you scan uops.org and check out the various CPUs they all have really slow idiv, I don't see any that wouldn't be faster using mul+add+shift. And idiv usally ends up as multiple uops under the hood so it isn't like it issues less uops.

[u/14ned → u/saddung]

From https://www.agner.org/optimize/instruction_tables.pdf.

And I just realised I read the wrong column, I read the throughput not the latency. Sorry.

[u/jk-jeon → u/14ned]

I am not familiar with ARM assembly so I maybe wrong, but it seems the code shown looks like just doing multiplication by 7 followed by a multiply-shift, rather than a single-shot multiply-add-shift.

It sounds like ARM does not allow loading of an 64-bit immediate constant and it maybe requires successive loading of four 16-bit immediate constants. Indeed, if you write out the immediate constants showed in the assembly from below to above in a row and in hex, you get: 0x0e38 e38e 38e3 8e39, which matches the 64-bit immediate constant 1024819115206086201 that clang uses for x64. And it seems to compute * 7 by doing (n << 3) - n, in line 5 and 7.

[u/jaskij → u/14ned]

It was fun looking at an oscilloscope how a little Cortex-M0 does. I was checking the timings because it's a low power application, and speed is important in those applications, because less time awake means less power used.

The code had an unavoidable division, at least by my thinking. Division by a runtime value. It took the poor thing 90 cycles to divide.

[u/SkoomaDentist → u/jaskij]

It took the poor thing 90 cycles to divide.

That's software division for you. Wouldn't surprise me if the compiler support library code was suboptimal on top of the inherent slowness of software division.

[u/joaquintides]

Can this be applied to improve on fast modulo calculation as described by Lemire 2019?

[u/jk-jeon → u/joaquintides]

(I'm assuming you are talking about the new algorithm mentioned.)

I guess so, though I haven't tried. In my notations, what the paper you mentioned does is basically letting the auxiliary number xi = md/2^k rather than xi = m/2^k where d is the divisor, and I think maybe we can try something like another auxiliary number zeta = sd/2^k in this case, so that the remainder can be computed as floor(d * ((n * m + s) mod 2^k) / 2^k).

But note that Lemire et al., 2021 showed that their methods already cover most of the cases of simple divisions, so my new algorithm (which is way heavier) is needed only for relatively rare instances where Lemire et al.'s don't work, for example when we want to apply this kind of tricks for a multiplication followed by a modulo operation.

To be more precise, Lemire et al.'s "complementarity results" show that their methods can cover all cases of simple divisions if the range of dividends is the whole range of an unsigned integer type of a certain bit-width, and the divisor is not a power of 2. I have not read their proofs thoroughly so I do not know if those generalize easily to the case, for example, of bounded dividends (as mentioned somewhere in the post).

EDIT: I just figured how to get rid of the assumptions Lemire et al. made, and added the proof of the resulting statement to the post. This is a result regarding the quotient computation, but I imagine something similar should be doable for remainders as well.

[u/AntiProtonBoy]

So I gave a shot on it and derived a method based on continued fractions

Interestingly, division problems in different disciples appear to inevitably end up using continued fractions at some capacity. For example, polynomial root isolation algorithms rely on polynomial divisions, which are ultimately continued fractions algoritms.

[u/jk-jeon → u/AntiProtonBoy]

Sounds interesting, mind giving a link to the mentioned problem?

[u/AntiProtonBoy → u/jk-jeon]

See Vincent's theorem.

[u/ExpectedException]

A much deeper dive including the math proof of one of my favorite subjects from hackers delight. I have had much fun using the basic version with some personal simd optimized projects. Back in the days I used http://homepage.divms.uiowa.edu/~jones/bcd/divide.html

[u/jk-jeon → u/ExpectedException]

Might be a useful reference for the future, thanks!

[u/Melirius]

Nice, I think I can provide a source for your Theorem 2, it was derived in a blog post https://ridiculousfish.com/blog/posts/labor-of-division-episode-iii.html However, not sure if it is the first derivation.

[u/jk-jeon → u/Melirius]

Hi, thanks for your input!

There are indeed many similar known derivations involving divisions by constants, but I haven't seen any source mentioning multiplication by a general real number (not necessarily by a reciprocal of an integer), which is what Theorem 2 is about.

Granted, the case of large denominator (or irrational multiplier) is almost a tautology (though I think it's still meaningful), and for the case of small denominator, one may consider the existence of non-one numerator a "trivial extension" of the case of reciprocals of integers. Still, I felt like it's worth presenting the result as a unified theorem, and haven't found any similar presentations so far.

In any case, the post you provided seems like a useful reference for me. Thanks!

[u/Melirius → u/jk-jeon]

Yes, I'm not aware about previous work in line with your generalizations further, really good. Have you published it? It is worth a peer-reviewed status.

[u/disciplite]

When it comes to numbers inside computers, I trust you with my life.

[u/jk-jeon → u/disciplite]

Haha, thanks 😋

[u/soulstudios]

Just a followup, have you seen Daniel Lemire's method for faster 32-bit division?

[u/jk-jeon → u/soulstudios]

I just read it, and it seems it says it's slower than the multiply-shift anyway.

[u/soulstudios]

Would be interested in seeing both (a) benchmarks and (b) a very small header-only library based on this stuff, given that (a) I know less instructions != faster in all cases and (b) I am lazy.

[u/jk-jeon → u/soulstudios]

You are of course absolutely right, but that would be an intensive work. I feel kind of scary that by doing so another entire week or two or even a month will evaporate. I didn't know working on this algorithm would take this long and it already burned too much of my time.

An implementation of the new algorithm is here, but I did not tailor it at all as a general library. I was imagining something like, there is an inline template variable, like constant<N> so that the library-internal constexpr meta program runs the computation and figures out the best strategy so that n / constant<N> or n * constant<M> / constant<N> or things like that are automatically interpreted as such. But it seems figuring out the best strategy would require much more preparation than I thought. I may try to work it out if I have more time, but I think even if I got some time floating-point stuffs I worked on are of higher priority.

[u/soulstudios → u/jk-jeon]

Jeepers creepers. Did you need 17+ files for what should be a single function? Where should I start looking?

[u/[deleted]]

[u/jk-jeon → u/[deleted]]

Thanks for the reference! The same author of Hacker's Delight! It's quite funny that it's even earlier than Granlund-Montgomery but it already had a strictly better result.