2
int a, b;
scanf("%d %d", &a, &b);
printf("%d\n", (unsigned int)a/(unsigned char)b);

When compiling, I got ...

    ::00401C1E::  C70424 24304000          MOV DWORD PTR [ESP],403024  %d %d
    ::00401C25::  E8 36FFFFFF              CALL 00401B60               scanf
    ::00401C2A::  0FB64C24 1C              MOVZX ECX,BYTE PTR [ESP+1C]
    ::00401C2F::  8B4424 18                MOV EAX,[ESP+18]                        
    ::00401C33::  31D2                     XOR EDX,EDX                             
    ::00401C35::  F7F1                     DIV ECX                                 
    ::00401C37::  894424 04                MOV [ESP+4],EAX                         
    ::00401C3B::  C70424 2A304000          MOV DWORD PTR [ESP],40302A  %d\x0A
    ::00401C42::  E8 21FFFFFF              CALL 00401B68               printf

Will it be faster if the DIV turn into MUL and use an array to store the mulvalue? If so, how to let the compiler do the optimization?

int main() {
    uint a, s=0, i, t;
    scanf("%d", &a);
    diviuint aa = a;
    t = clock();
    for (i=0; i<1000000000; i++)
        s += i/a;
    printf("Result:%10u\n", s);
    printf("Time:%12u\n", clock()-t);
    return 0;
}

where diviuint(a) make a memory of 1/a and use multiple instead Using s+=i/aa makes the speed 2 times of s+=i/a

7
  • Unlikely. You would add an indexed access to a 256 int array. Also, this sort of thing can work where you are dividing into a float but not dividing an int by a byte. You can approximate it by scaling and doing a right shift but that's even more stuff and would almost certainly be slower. This was the kind of monkey business I saw on embedded systems circa 1983 where division was slower and memory accesses relatively fast in comparison. Hasn't been the case in decades.
    – doug
    Apr 25, 2016 at 5:26
  • division can be optimized to a multiplication if b is a constant, but not when it's a variable. The compiler already knows this and will optimize when possible
    – phuclv
    Apr 25, 2016 at 5:27
  • @doug it works for integers by replacing a division with a multiplication by multiplicative inverse
    – phuclv
    Apr 25, 2016 at 5:28
  • 1
    If that "multiplicative inverse" trick would have been fast for division by a variable, division wouldn't have been slow in the first place : the CPU would have had the algorithm hardwired!
    – MSalters
    Apr 25, 2016 at 7:28
  • 1
    Which command line options do you use to compile? The output depends a lot on the optimization options you pass to gcc.
    – Jan Henke
    Apr 25, 2016 at 7:54

4 Answers 4

2

You are correct that finding the multiplicative inverse may be worth it if integer division inside a loop is unavoidable. gcc and clang won't do this for you with run-time constants, though; only compile-time constants. It's too expensive (in code-size) for the compiler to do without being sure it's needed, and the perf gains aren't as big with non compile-time constants. (I'm not confident a speedup will always be possible, depending on how good integer division is on the target microarchitecture.)


Using a multiplicative inverse

If you can't transform things to pull the divide out of the loop, and it runs many iterations, and a significant increase in code-size is with the performance gain (e.g. you aren't bottlenecked on cache misses that hide the div latency), then you might get a speedup from doing for run-time constants what the compiler does for compile-time constants.

Note that different constants need different shifts of the high half of the full-multiply, and some constants need more different shifts than others. (Another way of saying that some of the shift-counts are zero for some constants). So non-compile-time-constant divide-by-multiplying code needs all the shifts, and the shift counts have to be variable-count. (On x86, this is more expensive than immediate-count shifts).

libdivide has an implementation of the necessary math. You can use it to do SIMD-vectorized division, or for scalar, I think. This will definitely provide a big speedup over unpacking to scalar and doing integer division there. I haven't used it myself.

(Intel SSE/AVX doesn't do integer-division in hardware, but provides a variety of multiplies, and fairly efficient variable-count shift instructions. For 16bit elements, there's an instruction that produces only the high half of the multiply. For 32bit elements, there's a widening multiply, so you'd need a shuffle with that.)

Anyway, you could use libdivide to vectorize that add loop, with a horizontal sum at the end.


Other ways to get the div out of the loop

for (i=0; i<1000000000; i++)
    s += i/a;

In your example, you might get better results from using a uint128_t s accumulator and dividing by a outside the loop. A 64bit add/adc pair is pretty cheap. (It wouldn't give identical results, though, because integer division truncates instead of rounding to nearest.)

I think you can account for that by looping with i += a; tmp++, and doing s += tmp*a, to combine all the adds from iterations where i/a is the same. So s += 1 * a accounts for all the iterations from i = [a .. a*2-1]. Obviously that was just a trivial example, and looping more efficiently is usually not actually possible. It's off-topic for this question, but worth saying anyway: Look for big optimizations by re-structuring code or taking advantage of some math before trying to speed up doing the exact same thing faster. Speaking of math, you can use the sum(0..n) = n * (n+1) / 2 formula here, because we can factor a out of a*1 + a*2 + a*3 ... a*max. I may have an off-by-one here, but I'm confident a closed-form simple constant time calculation will give the same answer as the loop for any a:

uint32_t n = 1000000000 / a;
uint32_t s = a * n*(n+1)/2 + 1000000000 % a;

If you just needed i/a in a loop, it might be worth it to do something like:

// another optimization for an unlikely case
for (uint32_t i=0, remainder=0, i_over_a=0 ; i < n ; i++) {
    // use i_over_a

    ++remainder;
    if (remainder == a) {        // if you don't need the remainder in the loop, it could save an insn or two to count down from a to 0 instead of up from 0 to a, e.g. on x86.  But then you need a clever variable name other than remainder.
        remainder = 0;
        ++i_over_a;
    }
}

Again, this is unlikely: it only works if you're dividing the loop counter by a constant. However, it should work well. Either a is large so branch mispredicts will be infrequent, or a is (hopefully) small enough for a good branch predictor to recognize the repeating pattern of a-1 branches one way, then 1 branch the other way. The worst-case a value might be 33 or 65 or something, depending on microarchitecture. Branchless asm is probably possible but not worth it. e.g. handle ++i_over_a with an add-with-carry and a conditional move for zeroing. (e.g. x86 pseudo-code cmp a-1, remainder / cmovc remainder, 0 / adc i_over_a, 0. The b (below) condition is just CF==1, same as the c (carry) condition. The branchless asm would be simplified by decrementing from a to 0. (don't need a zeroed reg for cmov, and could have a in a reg instead of a-1))

2
  • Peter, this is useful stuff, a great answer, and would fit well if the OP would re-word the question away from the compiler optimization specific question towards the broader issue of increasing performance by scaled, multiplicative inverse of a common divisor.
    – doug
    Apr 28, 2016 at 14:10
  • I just simplified the background. Sometimes, when calculating a value mod m (for example, FNT), where m is unknown. I don't think it can be possible to reduce DIV's.
    – l4m2
    Apr 30, 2016 at 10:50
1

Replacing DIV with MUL may make sense (but doesn't have to in all cases) when one of the values is known at compile time. When both are user inputs, you don't know what's the range, so all usual tricks will not work.

Basically you need to handle both a and b between INT_MAX and INT_MIN. There's no space left for scaling them up/down. Even if you wanted to extend them to larger types, it would probably take longer time just to invert b and check that the result will be consistent.

1

The only way to KNOW if div or mul is faster is by testing both in a benchmark [obviously, if you use your above code, you'd mostly measure the time of read/write of the inputs and results, not the actual divide instruction, so you need something where you can isolate the divide instruction(s) from the input and output].

My guess would be that on slightly older processors, mul is a bit faster, on modern processors, div will be as fast as, if not faster than, a lookup of 256 int values.

If you have ONE target system, then it's plausible to test this. If you have several different systems you want to run on, you will have to ensure the "improved code" is faster on at least some of them - and not significantly slower on the rest.

Note also that you would introduce a dependency, which may in itself slow down the sequence of operations - modern CPU's are pretty good at "hiding" latency as long as there are other instructions to execute [so you should use this in an "as realistic scenario as possible"].

0

There is a wrong assumption in the question. The multiplicative inverse of an integer greater than 1 is a fraction less than one. These don't exist in the world of integers. A lookup table doesn't work because you can't lookup what doesn't exist. Even if you "scale" the dividend the results will not be correct in the sense of being the same as an integer division. Take this example:

printf("%x %x\n", 0x10/0x9, 0x30/0x9);
// prints: 1 5

Assuming a multiplicative inverse existed, both terms are divided by the same divisor (9) so must have the same lookup table value (multiplicative inverse). Any fixed lookup value corresponding to the divisor (9) multiplied by an integer will be precisely 3 times greater in the second term relative to the first term. As you can see from the example, the result of an actual integer division is a 5, not a 3.

You can approximate things by using a scaled lookup table. For instance a lookup table that is the multiplicative inverse when the result is divided by 2^16. You would then multiply by the lookup table value and shift the result 16 bits to the right. Time consuming and requires a 1024 byte lookup table. Even so, this would not produce the same results as an integer divide. A compiler optimization is not going to produce "approximate" results of an integer division.

7
  • 1
    On a processor which can quickly compute the top 32 bits of a 32x32->64 multiply, unsigned division by most constants can be replaced with a multiply quite nicely. For example, to divide by 3, multiply by 0x55555556 and discard the low half. In some cases an extra shift may be required, but the overall performance may still be much better than would be possible with a divide instruction. Note that these resutls are not "approximate"--they will be, for many divisors, exact for all possible dividends.
    – supercat
    Apr 26, 2016 at 18:42
  • OP's question was the use of a lookup table. a 4*2^32 size lookup table would be neither practical or fast. That said, for dividing by a select set of constants this may well be faster. It's a technique that is sometimes used when the cpu architecture benefits.
    – doug
    Apr 26, 2016 at 23:31
  • I would consider the function "f(x)=1LL+(MAX_UINT)/x" to be the inverse of the function "g(y)=(x*y) >> 32" for many values of x. Expanding the table all the way out to 2^32 wouldn't be practical, but depending upon the values to be divided expanding it out to 255 or so may be very practical.
    – supercat
    Apr 27, 2016 at 14:15
  • 1
    It takes time to find the right shifts and magic constant that will give exact results for all dividends, but it is possible for most divisors, like @supercat said. It can be worth it if you're dividing repeatedly by the same integer. Compilers have to find exact multiplicative inverses somehow, and they don't use lookup tables. There is an algorithm. I didn't describe it in my answer, since I'm not an expert, but I did link to libdivide.com Apr 28, 2016 at 3:06
  • 1
    libdivide.com has a very cool process for finding a multiply/shift operation that is almost always a match for an integer division. A compiler could reasonably optimize division by integer constants to emit a multiply/shift fo those cases that produce correct values. Aside from that it is a very useful technique for scaling non powers of 2 which does come up sometimes in DSP apps. So if all unsigned ints can be divided by using the specific multiply/shift for each of the 256, unsigned chars in the OP's possible divisors, and lookup time plus execution time is faster then it could be done.
    – doug
    Apr 28, 2016 at 13:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.