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.
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.