This article shows that

• the overhead of Java compared to C is probably about the same magnitude as that of C relative to Fortran
• There are arguments that Java may overtake C shortly; in fact this is already happening on Linux (with respect to gcc)

What is slow?

The benchmarks below show that java has e.g. 0.8-1.4 times the speed of C across a number of benchmarks, and is generally a bit faster than some C compilers (gcc). Is "slow" the right word?

When stuck on an airplane I'll sometimes look through PC World or similar magazines. They usually have a systems shootout with language like "System X trounces the competition". The table showing the WinBizBench2000 scores reveals that System X is 4% faster than the other model. If you consider a 4% speed increase to be significant then indeed Java is slow... and you write everything in assembler no doubt! On the other hand if you think C and C++ have acceptable performance, read on.

Benchmarks

1. Numerical Kernels

   Benchmarking Java against C and Fortran for Scientific Applications
   Mark Bull, Lorna Smith, Lindsay Pottage, Robin Freeman,
   EPCC, University of Edinburgh (2001).

   The authors test some real numerical codes (FFT, Matrix factorization, SOR, fluid solver, N-body) on several architectures and compilers. On Intel they found that the Java performance was very reasonable compared to C (e.g, 20% slower), and that Java was faster than at least one C compiler (KAI compiler on Linux).

   The authors conclude, "On Intel Pentium hardware, especially with Linux, the performance gap is small enough to be of little or no concern to programmers."

2. Microbenchmarks (cache effects considered)

   Two years ago these benchmarks showed java performance at the time to be somewhere in the middle of C compiler performance - faster than the worst C compilers, slower than the best. These are "microbenchmarks", but they do have the advantage that they were run across a number of different problem sizes and thus the results are not reflecting a lucky cache interaction (see more details on this problem in the next section).

   These benchmarks are newly updated here with the latest java(1.4) and gcc(3.2), using full optimization (gcc -O3 -mcpu=pentiumpro -fexpensive-optimizations -fschedule-insns2...). This time java is faster than C the majority of the tests, by a factor of more than 2 in some cases...

   ... suggesting that java performance is catching up to or even pulling ahead of gcc at least.

   These test were mostly integer (except for an FFT).

3. More numerical methods: SciMark2 scores

   R. F. Boisvert, J. Moriera, M. Phillipsen, R. Pozo,
   Java and Numerical Computing,
   Computing in Science & Engineering, 3(2):18-24, Mar.-Apr., 2001.

   Like study #1, SciMark includes a number of numerical codes. On a PIII/500, MFlops (higher is better):

   ibm jdk 1.3.0	84.5
   linux2.2 gcc (2.9x) -O6	87.1

4. Still more numerical methods

   From the book Object-Oriented Implementations of Numerical Methods by Didier Besset (MorganKaufmann, 2001). The author is a PhD in Physics, worked at Stanford Linear Accelerator, etc.

   Operation	Units	C	Smalltalk	Java
   Polynomial 10th degree	msec.	1.1	27.7	9.0
   Neville Interpolation (20 points)	msec.	0.9	11.0	0.8
   LUP matrix inversion (100 x 100)	sec.	3.9	22.9	1.0

5. Microbenchmarks (cache effects not considered)

   In January 2004 OSNews.com posted an article, Nine Language Performance Round-up: Benchmarking Math & File I-O. These are simple numeric and file I/O loops, and no doubt suffer from the arbitrary cache interaction factor described below. They were however run under several different compilers, which helps. Again Java is competitive with (actually slighty faster than) several C++ compilers including Visual C++.

   (One benchmark tested trigonometry library calls. Java numerical programmers are aware that these calls became slower in java 1.4 as identical cross platform behavior was enforced. Evidently the lack of a strictfp keyword does yet not apply to library calls?)

6. OpenGL

   Timings on several OpenGL programs available in both C++ and Java versions were reported here.

   General prediction:	65-90% of optimized C++
   Nvidia demo:	90% of optimized C++
   MIT synthetic character program:	86% of speed optimized C++ speed

   Comment: these tests used SUN's jdk1.4, which is generally worse than IBM's for numerical code.

And In Theory: Maybe Java should be faster

1) Pointers make optimization hard

In C, consider the code

        x = y + 2 * (...)
        *p = ...
        z = x + ...

This pointer problem in C resembles the array bounds checking issue in Java: in both cases, if the compiler can determine the array (or pointer) index at compile time it can avoid the issue.

In the loop below, for example, a Java compiler can trivially avoid testing the lower array bound because the loop counter is only incremented, never decremented. A single test before starting the loop handles the upper bound test if 'len' is not modified inside the loop (and java has no pointers, so simply looking for an assignment is enough to determine this):

   for( int i = 0; i < len; i++ ) { a[i] = ... }

In cases where the compiler cannot determine the necessary information at compile time, the C pointer problem may actually be the bigger performance hit. In the java case, the loop bound(s) can be kept in registers, and the index is certainly in a register, so a register-register test is needed. In the C/C++ case a load from cache is needed.

2) Garbage collection- is it worse...or better?

Consider what happens when you do a new/malloc: a) the allocator wanders through some lists looking for a slot of the right size, then returns you a pointer. b) This pointer is pointing to some pretty random place.

With GC, a) the allocator doesn't need to look for memory, it knows where it is, b) the memory it returns is adjacent to the last bit of memory you requested. The wandering around part happens not all the time but only at garbage collection. And then of course (and depending on the GC algorithm) things get moved of course as well.

The cost of missing the cache

The big benefit of GC is memory locality. Because newly allocated memory is adjacent to the memory recently used, it is more likely to already be in the cache.

How much of an effect is this? One rather dated (1993) example shows that missing the cache can be a big cost: changing an array size in small C program from 1023 to 1024 results in a slowdown of 17 times (not 17%). This is like switching from C to VB! This particular program stumbled across what was probably the worst possible cache interaction for that particular processor (MIPS); the effect isn't that bad in general...but with processor speeds increasing faster than memory, missing the cache is probably an even bigger cost now than it was then.

(It's easy to find other research studies demonstrating this; here's one from Princeton: they found that (garbage-collected) ML programs translated from the SPEC92 benchmarks have lower cache miss rates than the equivalent C and Fortran programs.)

This is theory, what about practice? In a well known paper [2] several widely used programs (including perl and ghostscript) were adapted to use several different allocators including a garbage collector masquerading as malloc (with a dummy free()). The garbage collector was as fast as a typical malloc/free; perl was one of several programs that ran faster when converted to use a garbage collector. Another interesting fact is that the cost of malloc/free is significant: both perl and ghostscript spent roughly 25-30% of their time in these calls.

3) Run time compilation

The people working on hotspot in particular have hinted that Java should sometime be faster than C because of this. Why?

• Because the compiler knows which classes are actually loaded and being called, it can remove the overhead of virtual methods.
• A dynamic compiler may also get the branch prediction hints right more often than a static compiler.

Of the three reasons why Java may soon produce faster code than C/C++, I find this one the least convincing. I think it applies mainly to tasks (like web application servers) that are literally running for months under reasonably heavy load and slowly changing conditions; recompiling repeatedly is worth it in these cases. For more typical desktop programs, the compiler would need to be sure that a particular loop is going to run long enough for a re-optimize to be worthwhile.

Don't characterize the speed of a language based on a single benchmark of a single program.

Why isn't one program good enough?

For one, it's common sense; the compiler may happen to do particularly well or particularly poorly on the inner loop of the program; this doesn't generalize. The first study in benchmark #2 above shows Java is being faster C by a factor 2 on an FFT of an array of a particular size. Should you now proclaim that Java is always twice as fast as C? No, it's just one program.

There is a more important issue than the code quality on the particular benchmark, however: Cache/Memory effects.

Look at e.g. the FFT microbenchmark that we referenced above. The figure is reproduced here:

On this single program, depending on the input size, the relative performance of 'IBM' (IBM's Java) varies from about twice as slow to twice as fast as 'max-C' (gcc) (-O3 -lm -s -static -fomit-frame-pointer -mpentiumpro -march=pentiumpro -malign-functions=4 -fu nroll-all-loops -fexpensive-optimizations -malign-double -fschedule-insns2 -mwide-multiply -finline-function s -fstrict-aliasing). So what do you conclude from this benchmark? Java is twice as fast as C, or twice as slow, or anything in-between!

For a more dramatic example of cache effects see this link, discussed more above.

The person who posted [3] demonstrated the fragility of his own benchmark in a followup post, writing that "Java now performs as well as gcc on many tests" after changing something or other (note that it was not the Java language that changed).

Conclusions: Why is "Java is Slow" so Popular?

Nevertheless, it seems like "java is slow" is widely believed. Why this is so is perhaps the most interesting aspect of this article (at least in my mind).

Let's look at several possible reasons.

• Java circa 1995 was slow. The first incarnations of java did not java a JIT compiler, and hence were bytecode interpreted (like Python for example). JIT compilers appeared in JVMs from Microsoft, Symantec, and in Sun's java1.2.

  I find this explanation inadquate. Most "computer folk" are able to rattle off the exact speed in GHz of the latest processors, and they track this information as it changes each month (and have done so for years). Yet this explanation asks us to believe that they are not able to remember that a single and rather important language speed change occurred in 1996.

• Java can be slow still. For example, programs written with the thread-safe Vector class are necessarily slower (on a single processor at least) than those written with the equivalent thread-unsafe ArrayList class.

  This explanation is equally unsatisfying, because C++ and other languages have similar penalties. For example, The Kernighan and Pike book The Practice of Programming has a table with the following entries, describing the performance of several implementations of a text processing program:

  Version	400 MHz PII
  C	0.30 sec
  C++/STL/deque	11.2 sec
  C++/STL/list	1.5 sec

  These results are dated, and C++ compilers probably do better with STL these days, but using C++ features still doesn't come for free. For more information look for results of the OOPACK benchmark -- this benchmark is specifically designed to measure the overhead of using STL-like abstraction in C++.

• Java program startup is slow. Java compiles the program as it starts up, so an interactive program can be a bit sluggish for the first couple seconds of use.

  This approaches being a reasonable explanation for the speed myth. But while it might explain user's impressions, it does not explain why many programmers (who can easily understand the idea of an interpreted program being compiled) share our belief.

The answer probably lies somewhere in sociology or psychology. Programmers, despite their professed appreciation of logical thought, are not immune to a kind of mythology, though these particular "myths" are arbitrary and relatively harmless.

References

[1] K. Reinholtz, Java will be faster than C++, ACM Sigplan Notices, 35(2) 25-28 Feb 2000.

[2] Benjamin Zorn, The Measured Cost of Conservative Garbage Collection Software - Practice and Experience 1992.

[3] Linux Number Crunching: Languages and Tools, referenced on slashdot.org

[4] Christopher W. Cowell-Shah, Nine Language Performance Round-up: Benchmarking Math & File I/O, appeared at OSnews.com, Jan. 2004.