5 ms·

Probably 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 ago
This 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 ago
  Couldn't that be addressed via a floor operation afterwards?
  - SolarNet 10y ago
    Because unless you are on a video card (e.g. doing SIMD) floating point operations are very very expensive.
    - adwn 10y ago
      That 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 ago
On 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/
- kr7 10y ago
  That page has a warning at the top: > IMPORTANT: Useful feedback revealed that some of these measures are seriously flawed. A major update is on the way. Looking over the results, some of the numbers are off. On Intel CPUs, FP multiplication is faster than integer division. Might not be true on ARM CPUs which generally have slower FPUs. On Skylake, for example, 32-bit unsigned integer division has a 26 cycle latency with a throughput of 1 instruction / 6 cycles, while 32/64-bit floating point multiplication has a 4 cycle latency with a throughput of 2 instructions / cycle. Source: http://agner.org/optimize/instruction_tables.pdf http://agner.org/optimize/instruction_tables.pdf
  - yuriks 10y ago
    The crucial point, however, is that while FP multiplication is faster than integer division, converting between a floating point and an integer is very slow: cvtsi2ss and cvtss2si have a latency of 6 cycles each. This adds a latency of 12 cycles for each of these multiplications. For divisions by a constant value that don't easily decompose into shifts you can fall back to multiplication by a magic constant which is the integer reciprocal. (This is also something compilers do and is what's being explained in the article.)
    - caf 10y ago
      Multiplying by the integer reciprocal only works if the dividend is an integer multiple of the divisor. What's being explained in the article is multiplying by a fraction the value of which is close to the rational reciprocal of the divisor, and where the denominator of the fraction is an integer power of two (so dividing by the denominator can be done with a shift). The fraction in this case is (2938661835 + 2^32) / 2^37.
kr7 10y ago
It does work, though not as well as using an integer multiply. The approximate latencies for Skylake are: div --> 26 cycles cvtsi2sd + mulsd + cvttsd2siq --> 6 + 4 + 6 = 16 cycles I did a quick (and imperfect) microbenchmark, got these results: Real integer division (-Os) --> 1.392s FPU Multiply (-Os) --> 0.243s FPU Multiply (-O2) --> 0.197s Integer Multiply (-O2) --> 0.164s The code: #include <stdio.h> int main() { volatile unsigned x; for (unsigned n = 0; n < 100000000; ++n) { #if 1 /* Change to 0 to use FPU. */ /* Compile with -Os to get GCC to emit div instruction. -O2 to emit integer multiply. Clang emits integer multiply, even with -Os. */ x = n / 19; #else /* Use the FPU. */ x = (double)n * (1.0 / 19.0); #endif } }
- the-dude 10y ago
  Is it correct? What is x for n < 19 for example?
  - kr7 10y ago
    It works for 32-bit unsigned integers and double precision floats. For n < 19, "(double)n * (1.0 / 19.0)" evaluates to a double between 0.0 and 1.0, then it is truncated to 0 when it is implicitly converted to unsigned int. Since there are only 2^32 values for 32-bit integers, it is possible to test all values in under a minute: #include <stdio.h> #include <stdint.h> int main() { uint32_t n = 0; do { uint32_t a = n / 19; uint32_t b = (double)n * (1.0 / 19.0); if (a != b) { printf("Not equal for n = %u\n", n); } ++n; } while (n != 0); }
ridiculous_fish 10y ago
Note that approach done naively will produce wrong answers for lots of divisors, because the reciprocal will not be exactly representable. For example, 49*(1.0/49) is less than one. If you round the FP division up (to the next largest representable value, that is), it should be correct, for 32 bit integer types at least.

jeffasinger 10y ago

This 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 ago
Couldn't that be addressed via a floor operation afterwards?
- SolarNet 10y ago
  Because unless you are on a video card (e.g. doing SIMD) floating point operations are very very expensive.
  - adwn 10y ago
    That 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 ago

On 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/

kr7 10y ago
That page has a warning at the top: > IMPORTANT: Useful feedback revealed that some of these measures are seriously flawed. A major update is on the way. Looking over the results, some of the numbers are off. On Intel CPUs, FP multiplication is faster than integer division. Might not be true on ARM CPUs which generally have slower FPUs. On Skylake, for example, 32-bit unsigned integer division has a 26 cycle latency with a throughput of 1 instruction / 6 cycles, while 32/64-bit floating point multiplication has a 4 cycle latency with a throughput of 2 instructions / cycle. Source: http://agner.org/optimize/instruction_tables.pdf http://agner.org/optimize/instruction_tables.pdf
- yuriks 10y ago
  The crucial point, however, is that while FP multiplication is faster than integer division, converting between a floating point and an integer is very slow: cvtsi2ss and cvtss2si have a latency of 6 cycles each. This adds a latency of 12 cycles for each of these multiplications. For divisions by a constant value that don't easily decompose into shifts you can fall back to multiplication by a magic constant which is the integer reciprocal. (This is also something compilers do and is what's being explained in the article.)
  - caf 10y ago
    Multiplying by the integer reciprocal only works if the dividend is an integer multiple of the divisor. What's being explained in the article is multiplying by a fraction the value of which is close to the rational reciprocal of the divisor, and where the denominator of the fraction is an integer power of two (so dividing by the denominator can be done with a shift). The fraction in this case is (2938661835 + 2^32) / 2^37.

kr7 10y ago

It does work, though not as well as using an integer multiply. The approximate latencies for Skylake are: div --> 26 cycles cvtsi2sd + mulsd + cvttsd2siq --> 6 + 4 + 6 = 16 cycles I did a quick (and imperfect) microbenchmark, got these results: Real integer division (-Os) --> 1.392s FPU Multiply (-Os) --> 0.243s FPU Multiply (-O2) --> 0.197s Integer Multiply (-O2) --> 0.164s The code: #include <stdio.h> int main() { volatile unsigned x; for (unsigned n = 0; n < 100000000; ++n) { #if 1 /* Change to 0 to use FPU. */ /* Compile with -Os to get GCC to emit div instruction. -O2 to emit integer multiply. Clang emits integer multiply, even with -Os. */ x = n / 19; #else /* Use the FPU. */ x = (double)n * (1.0 / 19.0); #endif } }

the-dude 10y ago
Is it correct? What is x for n < 19 for example?
- kr7 10y ago
  It works for 32-bit unsigned integers and double precision floats. For n < 19, "(double)n * (1.0 / 19.0)" evaluates to a double between 0.0 and 1.0, then it is truncated to 0 when it is implicitly converted to unsigned int. Since there are only 2^32 values for 32-bit integers, it is possible to test all values in under a minute: #include <stdio.h> #include <stdint.h> int main() { uint32_t n = 0; do { uint32_t a = n / 19; uint32_t b = (double)n * (1.0 / 19.0); if (a != b) { printf("Not equal for n = %u\n", n); } ++n; } while (n != 0); }

ridiculous_fish 10y ago

Note that approach done naively will produce wrong answers for lots of divisors, because the reciprocal will not be exactly representable. For example, 49*(1.0/49) is less than one. If you round the FP division up (to the next largest representable value, that is), it should be correct, for 32 bit integer types at least.