9 ms·

Genuine question: why would any compiler bother to optimise division with such obtuse dividends, other than a purists' satisfaction ?

warkdarrior 5y ago
Division is orders of magnitude slower than multiplication.
- Tuna-Fish 5y ago
  Less than one order of magnitude these days. On Tiger Lake, integer multiply is 3 cycles, while integer division is 12 for 32-bit integers and 15 for 64-bit. Of course, the multiply is fully pipelined while the division is only partially, but even that leaves only a 10-fold difference. Division is much faster these days than it used to be. It's still worth it to have compiler optimizations for it, but it's not important to avoid it anymore.
  - gowld 5y ago
    Why do some people assume decimal ten as the base of the orders of magnitude when discussing binary arithmetic?
    - cma 5y ago
      Timespan/cycle count is almost always denoted in base 10 in conversation.
  - mmoskal 5y ago
    Cortex-M4 (think $2) has 1 cycle multiplication and 2-12 cycle division (with early termination). If you go down to Cortex-M0 (think $0.50) then you get software division which is indeed orders of magnitude slower. Of course lower down the line there isn't even hardware multiplication. Interestingly, the ARM11 in original RPi and RPi0 doesn't have hardware integer division (despite being 10x faster than typical M4 and typically having 10000x RAM), but it does have floating point division.
  - Fordec 5y ago
    > Less than one order of magnitude these days. > only a 10-fold difference. A ten fold difference is literally one order of magnitude. Which is what the post you're replying to factually stated.
    - cma 5y ago
      orders usually means 2 or more
      - mattkrause 5y ago
        Also the actual values were 4-5x (12 or 15 versus 3 cycles), adjusted up to 10x for pipelining.
        cma 5y ago
        10X is one order of magnitude, 100X is two.
        mattkrause 5y ago
        Indeed...and 4 to 5x is less than that! My clumsily-made point was that there were two sets of numbers in the GP, and the smaller is unambiguously less than one order of magnitude different.
      - Y_Y 5y ago
        This depends on context. more often (in my experience) people are using base 10 , but also sometimes 2 or e. Even still people (unfortunately) use "orders of magnitude" like "exponential growth", signifying something like "wow, a lot, but no idea how much".
        bloak 5y ago
        And for astronomers an order of magnitude can sometimes be 100^(1/5) =~ 2.512. I hate it, too, when people call a quadratic curve "exponential".
  - jbay808 5y ago
    Embedded systems programmers don't always have such luxury!
martincmartin 5y ago
They're often special cases of general algorithms. You can do many divisions as combinations of multiplications & shifts; in this case, the resulting code simplifies down to the smallest possible.
Denvercoder9 5y ago
There's no specific optimisation for these specific numbers. There's a more general optimisation to turn division by a fixed number into a multiplication and shift where possible (because division is a lot slower than multiplication), and there is another optimisation that eliminates useless shifts. Combined they yield this result for these specific numbers.
- joe_the_user 5y ago
  Yeah, a more detailed description of this general method seems missing from the article. Anyone care to provide it?
  - chrchang523 5y ago
    See the "Labor of Division" blog posts by the author of libdivide: https://ridiculousfish.com/blog/posts/labor-of-division-episode-i.html https://ridiculousfish.com/blog/posts/labor-of-division-epis... https://ridiculousfish.com/blog/posts/labor-of-division-episode-iii.html https://ridiculousfish.com/blog/posts/labor-of-division-epis...
    - joe_the_user 5y ago
      So basically calculating the multiplicative inverse of a number and storing it as something like a float (digits + exponent) with the digits and exponent stored separately to avoid overflow, underflow, accuracy issues. And it's faster if and only if you're repeating division by a single number since you're still doing the equivalent of divide to get the invest (but repeated division is actually quite common so this is useful).
      - yakubin 5y ago
        > And it's faster if and only if you're repeating division by a single number since you're still doing the equivalent of divide to get the invest This is done at compile-time by the compiler. We're talking about division by a constant, not by a variable. So it's always faster.

warkdarrior 5y ago

Division is orders of magnitude slower than multiplication.

Tuna-Fish 5y ago
Less than one order of magnitude these days. On Tiger Lake, integer multiply is 3 cycles, while integer division is 12 for 32-bit integers and 15 for 64-bit. Of course, the multiply is fully pipelined while the division is only partially, but even that leaves only a 10-fold difference. Division is much faster these days than it used to be. It's still worth it to have compiler optimizations for it, but it's not important to avoid it anymore.
- gowld 5y ago
  Why do some people assume decimal ten as the base of the orders of magnitude when discussing binary arithmetic?
  - cma 5y ago
    Timespan/cycle count is almost always denoted in base 10 in conversation.
- mmoskal 5y ago
  Cortex-M4 (think $2) has 1 cycle multiplication and 2-12 cycle division (with early termination). If you go down to Cortex-M0 (think $0.50) then you get software division which is indeed orders of magnitude slower. Of course lower down the line there isn't even hardware multiplication. Interestingly, the ARM11 in original RPi and RPi0 doesn't have hardware integer division (despite being 10x faster than typical M4 and typically having 10000x RAM), but it does have floating point division.
- Fordec 5y ago
  > Less than one order of magnitude these days. > only a 10-fold difference. A ten fold difference is literally one order of magnitude. Which is what the post you're replying to factually stated.
  - cma 5y ago
    orders usually means 2 or more
    - mattkrause 5y ago
      Also the actual values were 4-5x (12 or 15 versus 3 cycles), adjusted up to 10x for pipelining.
      - cma 5y ago
        10X is one order of magnitude, 100X is two.
        mattkrause 5y ago
        Indeed...and 4 to 5x is less than that! My clumsily-made point was that there were two sets of numbers in the GP, and the smaller is unambiguously less than one order of magnitude different.
    - Y_Y 5y ago
      This depends on context. more often (in my experience) people are using base 10 , but also sometimes 2 or e. Even still people (unfortunately) use "orders of magnitude" like "exponential growth", signifying something like "wow, a lot, but no idea how much".
      - bloak 5y ago
        And for astronomers an order of magnitude can sometimes be 100^(1/5) =~ 2.512. I hate it, too, when people call a quadratic curve "exponential".
- jbay808 5y ago
  Embedded systems programmers don't always have such luxury!

martincmartin 5y ago

They're often special cases of general algorithms. You can do many divisions as combinations of multiplications & shifts; in this case, the resulting code simplifies down to the smallest possible.

Denvercoder9 5y ago

There's no specific optimisation for these specific numbers. There's a more general optimisation to turn division by a fixed number into a multiplication and shift where possible (because division is a lot slower than multiplication), and there is another optimisation that eliminates useless shifts. Combined they yield this result for these specific numbers.

joe_the_user 5y ago
Yeah, a more detailed description of this general method seems missing from the article. Anyone care to provide it?
- chrchang523 5y ago
  See the "Labor of Division" blog posts by the author of libdivide: https://ridiculousfish.com/blog/posts/labor-of-division-episode-i.html https://ridiculousfish.com/blog/posts/labor-of-division-epis... https://ridiculousfish.com/blog/posts/labor-of-division-episode-iii.html https://ridiculousfish.com/blog/posts/labor-of-division-epis...
  - joe_the_user 5y ago
    So basically calculating the multiplicative inverse of a number and storing it as something like a float (digits + exponent) with the digits and exponent stored separately to avoid overflow, underflow, accuracy issues. And it's faster if and only if you're repeating division by a single number since you're still doing the equivalent of divide to get the invest (but repeated division is actually quite common so this is useful).
    - yakubin 5y ago
      > And it's faster if and only if you're repeating division by a single number since you're still doing the equivalent of divide to get the invest This is done at compile-time by the compiler. We're talking about division by a constant, not by a variable. So it's always faster.