Introduction
Some time ago I read an very interesting story about the Fastest way to format time. In this story a remarkable performance boost was created by optimizing integer divisions. This inspiring optimization was proposed by Jeffrey Sax (thanx) and it is based upon the following equivalence for a certain range of num:
x = num / div; (1)
equals
x = (num * mul) >> shift; (2)
From the story I got the idea to make a simple application that finds the values for shift and mul variables automatically for a given range (0..max) of num.
How it works
The division (1) is replaced by a multiply/shift (2) pair which is in fact an approximation of the original division. The optimization is based upon the fact that the multiply and shift operators are far faster than the division operator. Depending on the range of values (0..max) the variable num can take and the value of div, valid values for mul and shift can be found. It works unless num * mul throws an overflow exception.
The bool FindMulShift(..) function searches for the values for multiply and the shift in the following way. It takes the absolute values of the two parameters to get a positive values for mul. The value of shift wil allways be positive. This implies that in your code you must map the calculation to the domain of positive integers and take care of sign bits yourselve.
First the function checks if div == 0 as this cannot be handled. Then it checks the trivial case where max < div as this allways results in a value 0. Then it is checked if div is a power of two, this is done by checking all possible (0..63) powers in a straightforward loop. For non powers of 2 more math comes in, we can derive the mul factor from the equivalence of formula (1) and (2).
max / div = max * mul >> shift (3)
equals
1 / div = mul >> shift (4)
equals
mul = (1<< shift) / div (5)
It is clear that the mul depends on the shift, so we cannot calculate the value for mul directly. As div is a long we only need to test the 64 possible values for shift, in fact even less. If the value of shift is known the value for mul can be determined too. Due to rounding errors of the division operator we must add 1 to formula (5) to get the right value for mul. By testing the possible values for shift from 0 to 63 we get automatically the smallest possible values for both mul and shift. The current implementation of FindMulShift tests the complete range for num if the value is less than 1.000.000. An alternative way to test the validness of mul and shift is implemented but I have not worked out the mathematical proof. However it seems OK and it is much faster! Todo: work out the mathematical proof.
I think it is possible to calculate valid values for shift and mul directly, but first 'experiments' gave not allways the minimal values and reducing to the minimal value was not always possible in a simple way.
Based upon the same equivalence the performance of the modulo function, %, can also be improved. The modulo or remainder function (6) can be replaced with formula (7) that contains a division operation, and this can be rewritten to formula (8) based upon mul and shift. Note that the single % operator is replaced by four operators.
x = num % div; (6)
equals
x = num - (num/div) * div; (7)
equals
x = num - ((num * mul) >> shift) * div; (8)
The order of the expression (8) is important as in this order it reduces the chance of an overflow exception. Note that this expression is only valid for positive values of num and div.
When to use
The optimization can be used in any application that implements a lot of integer divisions or modulos and in which the range of the numerator is known. Think of graphic libraries, processing very large (database)tables, averaging samples of real time sensors, Math libraries, webservices etc. I can also imagine that a programmer gives hints about the range of the variables passed to a function. The compiler can use this information to optimize the resulting code beyond current levels. In pseudocode it could look like below. The code
[OPTIMIZE celcius={-273..10000}]
public int CelciusToFahrenheit(int celcius)
{
return (celcius - 32)/9 * 5;
}
could become to something like:
[OPTIMIZED celcius={-273..10000}]
public int CelciusToFahrenheit(int celcius)
{
int x = celcius - 32;
if (x >=0 )
return (x * 3641 >> 15) * 5;
else
return -((-x) * 3641 >> 15) * 5;
}
Another way to use this optimizer is as a "Math Optimizer Plugin" for the programming environment. Such a plugin could include a whole range of 'tricks' like the bithacks collected by Sean Anderson.
Performance
The src application makes some simple performance measurements. To see the influence of the debugger I ran the test both in debug and in release mode(.NET 2.0, 1.6 Ghz PC).
- integer division versus MulShift
- modulo operator versus MulShift
The table below gives the measurements made on my PC. For timing I used the
high performancetimer of Daniel Strigl (thanx). The test exists of 1000 divides and 1000 modulos for dividers -100..100, and a range of -1000..1000. Of course you can change these values to your needs.
| mode |
operator |
average gain % |
numbers |
| debug |
/ |
-12 |
pos + neg |
| release |
/ |
90 |
pos + neg |
| debug |
% |
-18 |
pos + neg |
| release |
% |
92 |
pos + neg |
| debug |
/ |
42 |
pos only |
| release |
/ |
90 |
pos only |
Because I use both negative and positive test values there is a 'complex' if then else structure in the test program to choose the right formula, especially for the modulo operator. Normally the denominator is fixed and the code can be much simpler of course. The last test of the application does a test for positive numbers only. Working with only positive numbers did also show improvements in the debug mode. Finally in the release code the overhead of handling the signs yourself seems to have no substantial influence.
As the scheduling of the OS influences the measurements there will be differences when the test is run again. Performance gains will also differ on different hardware and for different programming languages. Just measure your own.
Finale
In short a substantial gain can be made by replacing integer divisions by a multiply/shift pair. Be aware that in the debug mode the optimized code can be slower, especially if you have both negative and positive numbers and you have to handle the sign yourself.
Some items to improve the FindMulShift algorithm include:
- rangefinder, given a certain dividor what is the maximum range?,
- work out a mathematical proof of the fast verify method,
- investigate the limits of the optimization,
- investigate direct calculation of mul and shift,
- investigate doubles as divider?
- refactor ad fundum!
History
- 2007/01/27 - Version 1.00 - First version to publish.
- 2006/09/08 - Version 0.00 - Started experimenting.
Usage rights
Everybody is granted to use this code (at own risk) as long as you refer to the original work of Jeffrey Sax and this article.
