Let's Sieve Out Rumors of Poor Performance

One concern that many readers may have about using Java as a language for app development is efficiency. Before getting deep in app development, let's address that concern.

To see how good Visual J Plus Plus v6 performance is, I decided to use the aged, but still serviceable, Sieve of Eratosthenes benchmark. (Eratosthenes is pronounced era-TOS-the-knees.) First I wrote the sieve program in Java and compiled it under Visual J Plus Plus v6. Then I converted the program to C++ and compiled, executed, and timed that version. A comparison of the two programs indicates how Visual J Plus Plus v6 stacks up to C++.

This benchmark does a reasonable job of testing program logic, simple arithmetic, and array referencing. It does not test floating point math, the calling of functions, screen input and output (I/O) (which is more a function of the hardware and the operating system than the coding language anyway), or a number of other things.

The Sieve benchmark does do something that some programmers might consider useful: it searches for, finds, and, in this example, counts prime numbers. The Sieve benchmark does these tasks by using a very simple algorithm. First it assumes that every number between 2 and (in this case) one million is prime. It records this assumption by declaring an array of one million Booleans and setting every array element to true. (You could set the length to one million minus one because we're starting with 2, but coding is much easier if you just declare the full array and skip the first element.) The Sieve then starts looking through the array. Every time it finds a value of true, it knows that it's found a prime, so it counts the prime by incrementing a counter. However, the Sieve recognizes that multiples of a found prime are not prime, so it loops through the array and sets every multiple of the current prime to false. Once the program reaches the end of the array, the Sieve benchmark terminates.

Sieve in Visual J Plus Plus v6

The Sieve function code is shown here:

/**
 * Sieve - This class calculates prime numbers using the
 * venerable Sieve of Eratosthenes algorithm.
 * It is being used to compare Java performance
 * to that of C++.
 */
public class Class1
{
 // iteration count
 static final int ITR = 10;
 /**
 * The main entry point for the app. *
 * @param - this program takes no arguments
 */
 public static void main (String[] args)
 {
 // fetch the current time in milliseconds
 long startTime = System.currentTimeMillis();
 // allocate some variables that we'll need later
 int primeCount = 0;
 boolean[] prime = new boolean[1000000];
 int lng = prime.length;
 // repeat the process multiple times so
 // that it will take long enough to get an
 // accurate measurement
 for (int i = 0; i < ITR; i++)
 {
 // first create an array of Booleans, where
 // each member of the array stands for a number
 for (int j = 0; j < lng; j++) // NOTE 1
 {
 prime[j] = true;
 }
 // now loop through looking for prime numbers
 // (skip 0 and 1, they don't count)
 primeCount = 0;
 for (int j = 2; j < lng; j++) // NOTE2
 {
 if (prime[j])
 {
 // found a prime, count it
 primeCount++;
 // now set all of the multiples of
 // the current prime number to false
 // because they couldn't possibly be
 // prime
 for (int k = j; k < lng; k += j) // NOTE 3
 {
 prime[k] = false;
 }
 }
 }
 }
 // done!
 long stopTime = System.currentTimeMillis();
 // output the number of primes
 System.out.println("Number of primes = " + primeCount);
 // and the number of iterations
 System.out.println("Number of iterations = " + ITR);
 // now display the time difference
 System.out.println("Time delta = " + (stopTime - startTime)
 + " milliseconds");
 }
}


The program begins, as do all Java apps, at the function main(). Then it immediately uses the method System.currentTimeMillis() to record the current time (starting from some arbitrary point) in milliseconds. Next it allocates an array of Boolean values called prime. This is the array that the program will use to keep track of what is and what isn't prime.

NOTE
Java declares a type called boolean rather than relying on int. In addition, in Java an array must be declared off of the heap and uses a syntax slightly different than that of C++: boolean[] prime = new boolean[1000000]. In fact, the [] can go either before or after the variable name prime.

The outer loop of ten iterations is nothing more than a time killer; iterating ten times makes the program take ten times as long. The next loop (labeled NOTE 1) sets each member of prime to true. That loop is the equivalent of saying that all numbers are prime, but it is setting up for the main loop where we find out what numbers really are prime.

The loop labeled NOTE 2 checks each member, starting with the number 2. (The program knows that 0 and 1 are not prime by definition.) If that number is prime, which it is, then it is counted. Following that, the loop labeled NOTE 3 marks every multiple of 2 as nonprime. The loop labeled NOTE 2 is repeated for the values of 3, 4, 5, and so on, up to one million.

Once the program has completed counting all of the primes that it can find between 2 and one million and has repeated this step ten times, the program records the time again. It then outputs the number of iterations, the number of primes it found, and the difference between the starting and ending time.

Once I convinced myself that the program was working as expected, I changed the project settings to enable optimization and disable debugging. Then I ran the program from the command line of a DOS window in Windows 98 on my home machine, a 200 MHz Pentium processor with loads of RAM. The program generated the results shown in Figure 1-12.

Java Click to view at full size.

Screenshot-12. The results of running the Sieve of Eratosthenes benchmark in Visual J Plus Plus v6.

Sieve in C++

Converting the Sieve benchmark program into the C++ CSieve benchmark turned out to be amazingly easy. I had to rewrite the I/O calls (which don't figure into the measured calculation time, by the way), replace the time function, rewrite the line that allocates the prime array, and replace boolean with int. After that, the resulting CSieve program compiled and linked successfully. Because of the similarity between Java and C++ syntax, I did not have to change the code within the for loops at all. (The C++ Sieve code is included on the enclosed DVD in the C++ Benchmark folder.)

I compiled the CSieve program with debugging turned off and the compiler optimizer options set to generate the fastest possible code. I used the Visual C++ 6 compiler. The result of executing the C/C++ version of the Sieve is shown in Figure 1-13.

Java Click to view at full size.

Screenshot-13. The result of running the same Sieve of Eratosthenes in C/C++.

Comparing the Two Sieves

The Visual J Plus Plus version of the program is considerably smaller than the C++ version—8 KB for the J++ executable file versus 124 KB for the C++ version—which doesn't surprise me. The difference in size is probably because J++ relies heavily on the Microsoft Virtual Machine for Java (VM). The VM contains the classes, such as System and PrintStream. The J++ program contains little more than the Sieve program itself.

By comparison, the C++ program is more or less self-contained. While it may rely on DOS API calls to perform output to the console, accessing the iostream library to perform output causes the linker to include a large amount of library code into the CSieve executable file. (The CSieve.obj object file generated by the compiler was only 5 KB.)

I was completely surprised, however, to discover that the Visual J Plus Plus v6 version of the Sieve program runs faster than the C++ version—about 3 seconds for the J++ version vs. 6 seconds for the C++ version. I do not believe that this difference has anything to do with the size of the programs. Since the clock doesn't start until main() is called, the time needed to load the program from disk isn't included in the execution time.

I am unsure what affect the processor cache might have on the execution time. While CSieve.exe would have stretched the bounds of the cache, only a small fraction of that executable file was actually being timed. The Sieve function was less than 10 KB in both the J++ and C++ cases. The accessing of the 1-megabyte array would have pushed some of the executable code out of the cache anyway.

Notice that the possible time spent by the Visual J Plus Plus Just-In-Time compiler converting VM byte code into Pentium machine code is also not included; however, this time must have been very short. My perception when running the two benchmarks agrees with the programs' measurements: the J++ version appears to run faster than the C++ version.

I have not conducted a large suite of tests to demonstrate Visual J Plus Plus v6 performance—for what I and the vast majority of Java programmers do, the highest level of performance isn't required. Nevertheless, it seems that Microsoft has taken considerable pains to generate an optimized Just-In-Time Java compiler. The Java compiler generates console apps whose performance is at least comparable to the output of a C++ compiler. We'll reuse the Sieve metric to measure applet performance in Part II. Comments