Friday, July 9, 2010

Compare Optimization Tricks

Okay I invented these bitwise tricks myself, so they shouldn't be as well known as the last one I posted; well the first one is more obvious (so probably other people have used it), but the other one not so much.

If you're ever comparing an integer being in the range 0...n, you can normally do this:

// Normal Compare
bool compare(int x) {
return (x >= 0) && (x <= 10)
}


However, you can do that same operation with just one compare instruction:

// Optimized Compare
bool compare(int x) {
return (unsigned int)x <= 10;
}



Now this second trick is if you want to compare 2 different integers, and want to check if they're both in the range 0...2^n

Normally you could do this:

// Normal Compare
bool compare(int x, int y) {
return (x >= 0) && (x <= 16)
&& (y >= 0) && (y <= 16);
}


Using the trick mentioned before, we figured out you can optimize it to this:

// Optimized Compare
bool compare(int x, int y) {
return ((unsigned int)x <= 16)
&& ((unsigned int)y <= 16);
}


But now we can further optimize this to just one single compare!

// Very Optimized Compare!
bool compare(int x, int y) {
return ((unsigned int)(x|y) <= 16);
}


That ends up doing the work of 4 comparisons, with just 1!
(Although you now have the added OR instruction; but OR is very fast to compute on almost every processor).

I want to stress again that the last optimization only works when the value is a power of two (2^n).

No comments:

Post a Comment