Abstract
This page compares the execution speed of Java versus C++
using two different types of sort algorithms
-- a generic bubble sort and the sort algorithms from the
Java and C++ libraries.
The runtimes of the algorithms
are measured in several different execution
environments, so they can also be used to compare
machines and operating systems.
FAQ
All runtimes are measured using the 'time' command. While this
includes HotSpot compilation time, I ran independent experiments
that showed that the time spent in HotSpot compilation is just a
small fraction of total runtime for the examples. (Nonetheless,
the code could be extended to measure "steady-state" runtimes.)
Other Resources
updates:
12/25/2003: added Other Resources
older updates:
10/20/2002: added Perl versions of bubble sort and library sort
12/19/2001: added results for JRockit 3.0.1
04/27/2001: added results for sorting variables of a
built-in type (int) using the respective libraries
02/17/2001: added results for Java 1.3.1-beta
01/23/2001: added results for a Sun Ultra 10 running Solaris 8
01/14/2001: added results for IBM's Classic VM 1.3.0
01/12/2001: added Java library example using ArrayList instead
of Vector
01/11/2001: added results for the HotSpot Server VM under Linux
01/09/2001: added results for my 800 MHz Pentium III PC running
Windows 2000 and the HotSpot Server VM
The project started when Amit challenged me to write a generic sort algorithm in Java. He suggested quicksort, but I was lazy and hacked up only a bubble sort. Amit wrote the corresponding generic bubble sort in C++, and after a short while we had four C++ and three Java versions of the generic bubble sort. :)
Of course, bubble sort is quadratic and not the most efficient sort algorithm, but this does not make the results less meaningful. Just think of them as results for a (particular) quadratic algorithm. For results on efficient sort algorithms, see the second comparison below.
Here the four C++ versions. The first two versions use C++ arrays, the last two versions use STL vectors (while the first one uses only vector, the second one uses also iterators and swap()).
| Version | operates on |
| C++ pointer | array of object pointers |
| C++ object | array of objects |
| C++ vector | vector of objects |
| C++ STL | vector of objects and STL |
Here the three Java versions. The first version uses Java arrays, the second version uses the thread-safe java.util.Vector class, and the third version uses the java.util.ArrayList class, which was introduced in Java 1.2 and is not thread-safe. Non-thread-safe libraries make locking the responsibility of the user (client) of the library, which gives the user more flexibility and typically results in faster execution. The C++ STL is not thread-safe.
| Version | operates on | equivalent C++ version |
| Java array | array of object references | C++ pointer |
| Java Vector | vector of object references | roughly C++ vector or C++ STL, except for locking |
| Java ArrayList | ArrayList of object references | roughly C++ vector or C++ STL |
Note that generic programming in Java requires casts, which might result in runtime errors that could have been detected at compile time in C++.
Here the results for a 233 MHz Pentium PC running Windows 95:
| Version | Execution Environment | Execution Time |
| Java array | Classic VM, JDK-1.2.2-001 | 81s |
| HotSpot VM 1.0.1 / Client VM 1.3beta-O | 58s / 58s | |
| Java Vector | HotSpot VM 1.0.1 / Client VM 1.3beta-O | 216s / 215s |
| Java ArrayList | Client VM 1.3beta-O | 166s |
| C++ pointer | MS Visual C++ 6.0 | 44s |
| Cygwin B20.1, egcs-2.91.57 | 19s | |
| C++ object | MS Visual C++ 6.0 | 11s |
| Cygwin B20.1, egcs-2.91.57 | 16s | |
| C++ vector | Cygwin B20.1, egcs-2.91.57 | 15s |
| C++ STL | Cygwin B20.1, egcs-2.91.57 | 11s |
I would have expected the C++ pointer version to be faster than the C++ object version since no objects are copied, but caching(?) effects seem to dominate. The Cygnus Cygwin version of egcs seems to be producing slightly better code than Visual C++.
Here the results for a Sun Ultra 2/2170 running Solaris 2.6 (SunOS 5.6):
| Version | Execution Environment | Execution Time |
| Java array | JVM 1.1.5 / 1.2 | 427s / 47s |
| Java Vector | JVM 1.1.5 / 1.2 | 1804s / 343s |
| Java ArrayList | JVM 1.2 | 187s |
| C++ pointer | gcc version 2.8.1 | 11.6s |
| C++ object | gcc version 2.8.1 | 16.7s |
| C++ vector | gcc version 2.8.1 | 17.6s |
| C++ STL | gcc version 2.8.1 | 14.6s |
Note that the C++ pointer version is faster than the C++ object version, as one would expect. Also notice the big difference in speed between Java versions 1.1.5 and 1.2. The JVM in version 1.1.5 is a pure interpreter, while version 1.2 includes a Just In Time compiler.
The non-thread-safe Java ArrayList version is 45% faster than the thread-safe Java Vector version. The locking in Java Vector hence has a relatively large overhead. Josh Bloch had initially suggested the use of ArrayList instead of Vector. At that point in time, however, I was mainly using the Java 1.1 environment that does not include ArrayList. It took some more time and additional motivation by Vincent Joseph before I added the Java ArrayList example.
Here the results for my 400 MHz Pentium II PC running RedHat 5.2 / 6.1:
| Version | Execution Environment | Execution Time |
| Java array | JVM 1.1.5 v7 / 1.2 pre-v2 / 1.2.2 rc2 | 192s / 96s / 118s |
| HotSpot Server 1.3.0 / IBM Classic VM 1.3.0 | 16.7s / 10.7s | |
| HotSpot Server 1.3.1beta-b15 | 16.3s | |
| Java Vector | JVM 1.1.5 v7 / 1.2 pre-v2 / 1.2.2 rc2 | 698s / 481s / 543s |
| HotSpot Server 1.3.0 / IBM Classic VM 1.3.0 | 46.5s / 71.5s | |
| HotSpot Server 1.3.1beta-b15 | 45.6s | |
| Java ArrayList | JVM 1.2 pre-v2 / 1.2.2 rc2 | - / 260s |
| HotSpot Server 1.3.0 / IBM Classic VM 1.3.0 | 18.8s / 62.8s | |
| HotSpot Server 1.3.1beta-b15 | 18.8s | |
| C++ pointer | gcc version egcs-2.90.29 / 2.95 | 3.6s / 3.3s |
| C++ object | gcc version egcs-2.90.29 / 2.95 | 5.7s / 3.9s |
| C++ vector | gcc version egcs-2.90.29 / 2.95 | 6.0s / 5.9s |
| C++ STL | gcc version egcs-2.90.29 / 2.95 | 3.8s / 3.9s |
Josh Bloch ran the Java versions on his 400 MHz Pentium II PC running Windows NT:
| Version | Execution Environment | Execution Time |
| Java array | HotSpot Client VM 1.3beta | 19.6s |
| Java Vector | HotSpot Client VM 1.3beta | 90.2s |
| Java ArrayList | HotSpot Client VM 1.3beta | 60.1s |
The latest Windows NT HotSpot virtual machine is a vast improvement over the Linux 1.1.5 and 1.2 virtual machines. The speedup of Java 1.2 in comparison to 1.1.5 on Linux seems disappointing, however, when compared with the speedup of the Solaris versions above.
While I got the Linux version of Java 1.2 from blackdown.org, I got Java 1.2.2 directly from Sun. Note that Sun's Linux version is even slower than Blackdown's version. Linus Torvalds's (Aug 1998) opinion on Java is interesting in this context.
Note that the Java array version running under the Windows NT HotSpot virtual machine is still a factor of six slower than the C++ pointer version running under Linux on a machine with the same power. The Java ArrayList version is a factor of 15 slower than the similar C++ STL version.
Here some results for my 800 MHz Pentium III PC running Windows 2000 and using Sun's HotSpot Server and AVM's JRockit virtual machine.
| Version | Execution Environment | Execution Time |
| Java array | HotSpot Server VM 2.0fcs-E | 8.3s |
| HotSpot Server VM 1.4.0-b92 | 7.1s | |
| JRockit 3.0.1 | 11.4s | |
| Java ArrayList | HotSpot Server VM 2.0fcs-E | 10.1s |
| HotSpot Server VM 1.4.0-b92 | 8.3s | |
| JRockit 3.0.1 | 31.2s | |
| C++ pointer | Cygwin 1.1.x, gcc 2.95.2 | 1.04s |
| C++ STL | Cygwin 1.1.x, gcc 2.95.2 | 1.27s |
| Perl | ActiveState Perl 5.6.1 | 1391s |
Here more results for a Sun Ultra 10 running Solaris 8 (SunOS 5.8).
| Version | Execution Environment | Execution Time |
| Java array | HotSpot Server VM 1.3.0 | 17.4s |
| Java ArrayList | HotSpot Server VM 1.3.0 | 26.3s |
| C++ pointer | Sun CC 5.1 | 5.22s |
| gcc 2.95.2 | 5.84s | |
| C++ STL | gcc 2.95.2 | 6.55s |
In C++, using STL vectors instead of built-in arrays has only little impact on the performance of the code (compare the C++ object and vector versions) or can even improve performance (compare the C++ object and STL versions). In Java, using Vectors instead of the built-in arrays can slow down the speed considerably (compare the Java array and vector versions). This is not too surprising since the Java Vector class, like most of Java's libraries, is not native code, but implemented in Java. Josh Bloch pointed out to me that the Java library sort algorithm dumps the List (Vector implements List) into an array before sorting it to avoid the expense of polymorphic dispatches in the inner loop.
Sun's new HotSpot Server VM makes the performance difference between ArrayLists and built-in arrays quite small. Nevertheless, Java is still roughly a factor of eight slower than C++ on this example.
In a second set of experiments, we compared the execution speed of Java vs. C++ for the library sort algorithms. We did this comparison for sorting variables of both a user-defined type (Range) and a built-in type (int).
For sorting user-defined types, we used Java's Collections.sort.
The Java library version using ArrayList instead of Vector was suggested by Josh Bloch, and is the version that should be compared to the C++ library version. (The difference between the two Java versions is small, however, since the library sort works with an array internally.)
| Version | uses |
| Java library | Collections.sort |
| Java library ArrayList | Collections.sort |
| C++ library | STL sort |
Here the runtimes:
| Machine | Version | Execution Environment | Execution Time |
| 233 MHz Pentium, Windows 95 | Java library | HotSpot Client VM 1.3beta | 112s |
| C++ library | Cygwin B20.1, egcs-2.91.57 | 10.6s | |
| 400 MHz Pentium II, Windows NT | Java library | HotSpot Client VM 1.3beta | 23.3s |
| 400 MHz Pentium II, RedHat 6.1 | Java library | HotSpot Server VM 1.3.0 | 31.4s |
| Java library ArrayList | HotSpot Server VM 1.3.0 | 31.1s | |
| 1.3.1beta-b15 | 32.5s | ||
| RedHat 5.2 | C++ library | gcc version 2.95 | 2.9s |
| 800 MHz Pentium III, Windows 2000 | Java library | HotSpot Server VM 2.0fcs-E | 18.0s |
| HotSpot Server VM 1.4.0-b92 | 18.5s | ||
| JRockit 3.0.1 | 34.1s | ||
| Java library ArrayList | HotSpot Server VM 2.0fcs-E | 17.8s | |
| HotSpot Server VM 1.4.0-b92 | 19.9s | ||
| JRockit 3.0.1 | 32.2s | ||
| C++ library | Cygwin 1.1.x, gcc 2.95.2 | 2.39s | |
| Perl | ActiveState Perl 5.6.1 | 193s | |
| Sun Ultra 10, Solaris 8 | Java library ArrayList | HotSpot Server VM 1.3.0 | 34.8s |
| C++ library | gcc 2.95.2 | 4.53s |
When sorting a vector of objects (Ranges of two int values in this example), the library sort algorithm in Java is roughly a factor of eight to ten slower than the one in C++. But Java looks much better when sorting built-in types (see below).
Note that the Pentium III is only slightly faster than the Pentium II on this example, suggesting that the memory access is the bottleneck. The Pentium III uses PC133 SDRAM and the VIA Apollo chipset, while the Pentium II uses PC100 SDRAM and the (good old) Intel BX chipset.
For sorting built-in types, we used Java's Arrays.sort. Interestingly, using Arrays.sort on an int[] resulted in a roughly 10-fold speedup over using Collections.sort on an ArrayList with Integers. Thanks again to Josh Bloch who pointed out the use of Arrays.sort (and who also wrote the Arrays.sort library :). I am looking forward to his new book Effective Java.
| Version | uses |
| Java library | Arrays.sort |
| C++ library | STL sort |
Here the runtimes:
| Machine | Version | Execution Environment | Execution Time |
| 400 MHz Pentium II, RedHat 6.1 | Java library | HotSpot Server VM 1.3.1beta-b15 | 9.4s |
| C++ library | gcc version 2.91.66 | 6.6s | |
| 800 MHz Pentium III, Windows 2000 | Java library | HotSpot Server VM 2.0fcs-E | 5.6s |
| HotSpot Server VM 1.4.0-b92 | 5.9s | ||
| JRockit 3.0.1 | 6.9s | ||
| C++ library | Cygwin 1.1.x, gcc 2.95.2 | 4.0s |
Java does quite well sorting built-in types. But I suspect the runtimes to be mostly memory-bound.