Performance: Examining performance yardsticks, the Sieve of Eratosthenes and comparing Apples with Oranges
You have to love when a tool or construct developed over 2000 years ago plays such a huge role in modern computing. I was running through a number of different performance websites and I came across one, several months ago, that used nearly 300 smaller programs to test the performance of more than 40 languages and implementations. That someone took the time to write such a matrix of programs was astounding. Needless to say I fixed a number of non performance optimized C# applications and submitted a few that were missing. Missing code samples weighed in as a big 0 on the matrix and was negatively weighting C# as being slow.
One of the programs that I didn't even bother touching was the Sieve of Eratosthenes. The main reason is that you never know what people are examining when they use the Sieve. The first step for instance is to set all of the elements in the array to 1, to denote they haven't been tested yet. This looks something like:
for(int i = 2; i < array.Length; i++) { array[i] = 1; }
Now, if you do that in all languages you'll get similar performance, but some people try to sneak a memset in there or unbalance the situation in some other way. You can't do that becuase you aren't comparing the same features of the language. Comparing apples and oranges. If we were going to be smart about the entire process, then rather than initialize with 1, I'd initialize only the first couple of elements with 0, and swap the comparisons later in the algorithm. In that manner I don't even have to fully initialize the array in the beginning. BTW - Since C# isn't really as fast as say C++ when it comes to array manipulation it tends to fall short by this particular yardstick.
Next we have three loops that comprise the following rules for the Sieve. Take each prime number and mark off all multiples of that number. If you selected 2, then you would mark off 4, 6, 8, 10, etc... Since 3 hasn't been marked off it must not be prime, so you then mark off 6, 9, 13, 15, etc... Once you get to 4, it is already marked off, so you can skip it and move onto 5 and continue the process. When you are done marking off multiples of the primes, you'll be left with just prime numbers having not been marked off. In a popular book on performance and algorithms this is generalized as follows:
for(int i = 2; i < array.Length; i++)
if ( array[i] == 1)
for(int j = i; i*j < array.Length; j++)
a[i*j] = 0;
for(int i = 2; i < array.Length; i++)
if ( array[i] == 1 )
Console.WriteLine("Prime: {0}", i);
If this is really a test for array access, then everything that isn't an array access is going to throw off the results. It might be nice to remove the multiplication. Languages like C# don't default numeric types to binary comparisons either. array[i] == 1 in C# may be slower than array[i] in C++ where 0 is treated as false and any non-zero is treated as true. Might make sense to try changing the C# program to using a bool[] so that it is doing comparable operations wth the C++ program. You might completely miss this if you aren't aware of how the language instructions get turned into machine instructions, or in the case of C#, IL instructions. Here is just a basic test for using bools in place of integers where you can see that bools are over 50% faster. The rest of the algorithms are identical.
private static void IntSieveOfEratosthenes(int maxCount) {
uint i = 0; uint j = 0; // 2 Stack locals because C# is stupid
int[] primes = new int[maxCount];
for(i = 2; i < primes.Length; i++) { primes[i] = 1; }
for(i = 2; i < primes.Length; i++) {
if ( primes[i] == 1 ) {
for(j = i; i*j < primes.Length; j++) {
primes[i*j] = 0;
}
}
}
}
private static void BoolSieveOfEratosthenes(int maxCount) {
uint i = 0; uint j = 0; // 2 Stack locals because C# is stupid
bool[] primes = new bool[maxCount];
for(i = 2; i < primes.Length; i++) { primes[i] = true; }
for(i = 2; i < primes.Length; i++) {
if ( primes[i] ) {
for(j = i; j*i < primes.Length; j++) {
primes[i*j] = false;
}
}
}
}
Don't confuse testing the feature of a language with the performance of a particular algorithm. We are testing array access speed here by stomping on the elements as much as we possibly can while still doing some work. Fixing the instruction count by changing the integer array to a bool because of the comparisons involved is an equalizing change to keep it in parity with an equivalent C++ implementation while other changes we could make to increase the speed are more dependent on the algorithm itself and affect the quality of the comparison we are doing. A great example of that would be changing the algorithm to remove the initial array set-up.
private static void BoolReverseOperationSieveOfEratosthenes(int maxCount) {
uint i = 0; uint j = 0; // 2 Stack locals because C# is stupid
bool[] primes = new bool[maxCount];
primes[0] = false;
primes[1] = false;
primes[2] = false;
for(i = 2; i < primes.Length; i++) {
if ( !primes[i] ) {
for(j = i; j*i < primes.Length; j++) {
primes[i*j] = true;
}
}
}
}
If you make any changes, even basic ones, you have to make sure that you are doing the same amount of work across all languages. Thankfully in C# you can easily monitor the amount of work done on an array as long as you aren't worried abou the timing, by enabling a simple debug construct. We'll cover this some other time, but if you think you have an idea of how we might compare two algorithms by make sure the do the same amount of work on the array, then feel free to post it in the comments.