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
x = num / div; (1)
x = (num * mul) >> shift; (2)
From the story I got the idea to make a simple application that finds the values for
mul variables automatically for a given range (0..max) of
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
shift can be found. It works unless
num * mul throws an overflow exception.
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)
1 / div = mul >> shift (4)
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
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
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
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
shift. Note that the single % operator is replaced by four operators.
x = num % div; (6)
x = num - (num/div) * div; (7)
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
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
public int CelciusToFahrenheit(int celcius)
return (celcius - 32)/9 * 5;
could become to something like:
public int CelciusToFahrenheit(int celcius)
// @ORG: return (celcius - 32)/9 * 5;
int x = celcius - 32; // use register for x
if (x >=0 )
return (x * 3641 >> 15) * 5;
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.
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|
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.
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!
- 2007/01/27 - Version 1.00 - First version to publish.
- 2006/09/08 - Version 0.00 - Started experimenting.
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.