Performance: Focusing on BinarySearch
If you take a look through Rotor you'll find a number of methods that have the signature TrySZ[...]. What these methods are meant to do is take intrinsic data types (int, float, long, etc...) and perform faster than normal operations on them. That is at least the hope. Another thing you wind up with are a bunch of conditional checks at the top of the files that tend to slow down the method if it is called often. Since we have been doing analysis of sorting algorithms, I figured, what the hell, might as well make sure all of our helper functions are as fast as possible.
If BinarySearch was a complicated function, you might be enticed to just use the available version. It isn't that difficult, and you can get some drastic performance improvements out of writing your own custom version. A custom implementation is about twice as fast as the built in version. Waiting for Whidbey might be a good idea, since intrinsics get faster, but if you check out that TrySZ[...] you can instantly note that generics won't make much of a difference... Why? Because TrySZ is taking your data back into unmanaged code and operating on it at an intrinsic level already. You are basically eating the cost of boxing only once, which doesn't have much impact. TrySZ is also skipping the use of the IComparer interface (unless you pass an IComparer in) so it is already as fast as using the generics version of the IComparer. The basic premise here, is that if our functional replacement is faster, it will more than likely remain faster even through version 2.0 of the CLR.
private static int BinarySearch(int[] searchArray, int low, int high, int start, int value) {
while(low <= high) {
if ( searchArray[start] == value ) {
return start;
}
if ( searchArray[start] > value ) {
high = start - 1;
} else {
low = start + 1;
}
start = (low + high) >> 1;
}
return ~low;
}
To explain the new algorithm a bit, we are using the same algorithm that the CLR does internally. We are inlining the comparison routines which makes a very small difference in performance. We might be able to twiddle the comparison order and see if we can get a bit more speed, but I won't worry about that for now. The method takes a start index. Where the initial binary search will begin. This is actually for an additional optimization that is talked about in Algorithms in C where you can tune the BinarySearch to be a bit faster in the case of regularly distributed data. I haven't changed any of the sorting methods to actually use the new tuning, but maybe later.
I removed all of the exceptional code-paths. Do you really need an ArgumenException instead of a NullReferenceException? What about an ArgumentOutOfRangeException in place of an IndexOutOfBoundsException? It may be nice, but it clearly isn't crucial to debugging the application if something goes wrong. The default exceptions will certainly be enough. Since I offset the initial start index, rather than compute it, you may also want to move the start computation to the top of the loop, and remove start from the parameter list. Up to you. This isn't a BinarySearch direct replacement either, as the method takes high instead of length. If you are passing length, then you'll need to do a high = low + length - 1.