Small Comparison Optimization = Big Gains

This is a small and pretty well known trick, but its worth mentioning since a lot of high-level coders don't seem to realize it, and it could result in some big speedups.

Lets take a look at some random code snippet:

int main() {
    const double len   = 10000;
    const double fract = 1.0/3.0;
    for(double i = 1; i < len; i++) {
    for(double j = 1;        ; j++) {
        if (j/i < fract) {
            cout << j << " / " << i << endl;
        }
        else break;
    }}
}

What this code is doing is printing out all fractions that are less than 1/3, for all denominators less than 10,000.

Notice anything that we can optimize?

Well if you take a look at the if-statement, notice we are dividing j by i, and then doing a comparison. But as we should know by now, division is a slow operation.

On Core 2 Duos, double floating-point division has a 6~32 clock cycle latency (exact latency depends on the operand values), whereas multiplication is only 5 cycles, and add/sub are 3 cycles.

So it would be nice if we can omit that division from the comparison... oh wait we can!

Using simple mathematics we can do:

     j/i  < fract      =>
i * (j/i) < fract * i  =>
      j   < fract * i

Now we got the same equation, but we were able to remove the division completely!
So in the worst-case that our division was taking ~32 clock cycles, this new optimization is ~6 times faster.

Now lets see this code in action.
Here is the same problem as above, except we've now increased 'len' to 100,000, and instead of printing out the results, we just count the fractions (this way we're not limited by console-write speed):

int main() {
    const double len   = 100000;
    const double fract = 1.0/3.0;
    int ret = 0;
    for(double i = 1; i < len; i++) {
    for(double j = 1;        ; j++) {
        if (j < fract * i) {
            ret++;
        }
        else break;
    }}
    cout << ret << endl;
}

When I ran the above code using "if (j/i < fract)", it took ~19 seconds to finish on my PC.
When I ran the optimized version using "if (j < fract*i), it took ~2 seconds to finish executing! That's an even bigger speedup than predicted.

I hope this shows why optimization is important.

One last thing to note:
When using integers, you might not always want to do this trick.
j/i > x, is not necessarily the same as j > x*i when using integers, since the first one truncates the value (obviously, since integers don't hold the fractional part).
For example:

int main() {
    int i = 21;
    int j =  2;

    if (i/j > 10) cout << "First one"  << endl;
    if (i > 10*j) cout << "Second one" << endl;
}

The above example only prints out "Second one" since we're using integers (if i and j were doubles, it would print out "First one" and "Second one").

This isn't really a negative, since when using integers you probably want to be using the second-method anyways, so you don't have to deal with converting to floats; in that case, you not only would save time by not doing a division, but you would also save time by not doing an int-to-float conversion.