Benchmarking Java versus C++ with A*

How much faster is C++ than Java?  Can we trust the microbenchmarks?

I have been a hard core C++ fan, but I've recently started learning Java.   I got frustrated at the fact that I couldn't get a straight answer out of the internet to the question:  "How much faster is C++ than Java?"   I was expecting a figure like 2 (C++ being 2 times faster than Java).  I understand that it can be very difficult to give a single answer to the question - there are just so many variables, but I wanted to get some idea - some data-points from people who have done their own comparisons, or some comparisons involving larger programs.


I found Java to be 30% faster on the A* shortest path search

I have a large in-memory database of a 'graph', consisting of about 400,000 nodes.  My Java program was taking quite a long time to calculate the shortest path between 2 nodes.  I didn't expect it to take so long, and I thought this must be evidence of Java being slow, so I wrote the same program in C++.

To my great surprise, Java outperformed C++ by 30%  - a 30% drop in runtime.  

This comparison is not what I would call a "significantly sized program", but it is larger than the programs you typically find reported with the micro-benchmarks.   The A* algorithm involves:

  • A hash-table
  • A priority queue
  • Graph traversal
  • Floating-point arithmetic


Are you sure you did it right?

I was fairly careful, and I do consider myself an expert C++ programmer.

  • I was running on a Dell Intel laptop.  
  • I used Visual Studio 2008
  • The C++ was release mode
  • I set _SCL_SECURE=0 and double-checked that I wasn't using the *!$ Microsoft checked iterators
  • I took into account the cost of garbage collection in Java
  • The Java program was compiled with IntelliJ, running in Tomcat 6.0.24
  • I checked that I got the same answer in both programs

 In fact I tried to slant the comparison in favour of C++ in a number of ways:

  • The database is in the form of "a data-structure in a memory-mapped file".  C++ can read this directly, interpreting regions of the file as native C++ objects.  Java on the other hand needs to read it integer by integer, datum by datum.
  • I tried both the built-in Microsoft new/delete operators as well as my own "SnazzyHeap" implementation.  The Microsoft 'delete' operator was very slow, even in release mode.  The figures reported are using 'SnazzyHeap'.
  • The A* algorithm requires a "decreaseKey()" operation on the priority queue.  I did this using PriorityQueue.remove(o), which I'm sure is an O(n) operation - I even stepped into the Java source-code, and it's using just a standard "Binary Heap" implementation straight out of a textbook.
  • I don't trust STL.  Way too many temporary objects being created and destroyed.  So I used my own implementation of vectors (using realloc() - can't go wrong there) and priority queues (using the same binary heap implementation as Java).   As I said earlier, I consider myself an expert C++ programmer and I'm quite confident that these components can't be improved upon.

BTW, I did try Java Persistence, but this was a mistake - it took 2 minutes to load the data-structure, whether it was from the raw XML files or from Java Persistence.  The memory-mapped file on the other hand loads instantly if you've been accessing it recently.


Why might this be?

Everyone assumes that C++ must be faster than Java, or at least as fast.

I know that people who write C++ optimising compilers are often bemoaning the fact that they could get huge performance improvements if they could assume "no aliasing", i.e. to make stronger assumptions about when variables are modified, than what the C++ language allows them.  Developers of java compilers & JVM's on the other hand can make stronger assumptions about every aspect of a program.  This is my main theory of why Java might be faster.

Another theory that Max Prakoso suggested is that the Visual Studio compiler doesn't have the benefit of being able to optimise the code with knowledge of its run-time profile.  HotSpot on the other hand, does do this.   I'm skeptical that this would produce a significant difference.

Max also asked me if I tried "whole program optimisation".  I didn't initially, but it didn't make a huge difference when I did briefly try it.  It might bring the difference down to 20%, but I should stress I didn't extensively test this variation.

 

Can I check this for myself?

Source-code is attached.  Skype me on "drtimcooper" if you want the datafile.


Conclusion

I suppose it’s “hats off” to the HotSpot people.

Č
ċ
ď
AStarC++.zip
(9k)
Tim Cooper,
Jul 7, 2010, 7:44 AM
ċ
ď
AStarJava.zip
(28k)
Tim Cooper,
Jul 7, 2010, 7:44 AM
Comments