Java collections faster than c++ containers?

Question

I was reading the comments on this answer and I saw this quote.

Object instantiation and object-oriented features are blazing fast to use (faster than C++ in many cases) because they're designed in from the beginning. and Collections are fast. Standard Java beats standard C/C++ in this area, even for most optimized C code.

One user (with really high rep I might add) boldly defended this claim, stating that

1. heap allocation in java is better than C++'s

2. and added this statement defending the collections in java

   And Java collections are fast compared to C++ collections due largely to the different memory subsystem.

So my question is can any of this really be true, and if so why is java's heap allocation so much faster.

Answer 1

This sort of statement is ridiculous; people making it are either incredibly uninformed, or incredibly dishonest. In particular:

• The speed of dynamic memory allocation in the two cases will depend on the pattern of dynamic memory use, as well as the implementation. It is trivial for someone familiar with the algorithms used in both cases to write a benchmark proving which ever one he wanted to be faster. (Thus, for example, programs using large, complex graphs that are build, then torn down and rebuilt, will typically run faster under garbage collection. As will programs that never use enough dynamic memory to trigger the collector. Programs using few, large, long lived allocations will often run faster with manual memory management.)

• When comparing the collections, you have to consider what is in the collections. If you're comparing large vectors of double, for example, the difference between Java and C++ will likely be slight, and could go either way. If you're comparing large vectors of Point, where Point is a value class containing two doubles, C++ will probably blow Java out of the water, because it uses pure value semantics (with no additional dynamic allocation), where as Java needs to dynamically allocate each Point (and no dynamic allocation is always faster than even the fastest dynamic allocation). If the Point class in Java is correctly designed to act as a value (and thus immutable, like java.lang.String), then doing a translation on the Point in a vector will require a new allocation for every Point; in C++, you could just assign.

• Much depends on the optimizer. In Java, the optimizer works with perfect knowledge of the actual use cases, in this particular run of the program, and perfect knowledge of the actual processor it is running on, in this run. In C++, the optimizer must work with data from a profiling run, which will never correspond exactly to any one run of the program, and the optimizer must (usually) generate code that will run (and run quickly) on a wide variety of processor versions. On the other hand, the C++ optimizer may take significantly more time analysing the different paths (and effective optimization can require a lot of CPU); the Java optimizer has to be fairly quick.

• Finally, although not relevant to all applications, C++ can be single threaded. In which case, no locking is needed in the allocator, which is never the case in Java.

With regards to the two numbered points: C++ can use more or less the same algorithms as Java in its heap allocator. I've used C++ programs where the ::operator delete() function was empty, and the memory was garbage collected. (If your application allocates lots of short lived, small objects, such an allocator will probably speed things up.) And as for the second: the really big advantage C++ has is that its memory model doesn't require everything to be dynamically allocated. Even if allocation in Java takes only a tenth of the time it would take in C++ (which could be the case, if you only count the allocation, and not the time needed for the collector sweeps), with large vectors of Point, as above, you're comparing two or three allocations in C++ with millions of allocations in Java.

And finally: "why is Java's heap allocation so much faster?" It isn't, necessarily, if you amortise the time for the collection phases. The time for the allocation itself can be very cheap, because Java (or at least most Java implementations) use a relocating collector, which results in all of the free memory being in a single contiguous block. This is at least partially offset by the time needed in the collector: to get that contiguity, you've got to move data, which means a lot of copying. In most implementations, it also means an additional indirection in the pointers, and a lot of special logic to avoid issues when one thread has the address in a register, or such.

Answer 2

Your questions don't have concrete answers. For example, C++ does not define memory management at all. It leaves allocation details up to the library implementation. Therefore, within the bounds of C++, a given platform may have a very slow heap allocation scheme, and Java would certainly be faster if it bypasses that. On another platform, memory allocations may be blazing fast, outperforming Java. As James Kanze pointed out, Java also places very little constraints on memory management (e.g. even the GC algorithm is entirely up to the JVM implementor). Because Java and C++ do not place constraints on memory management, there is no concrete answer to that question. C++ is purposefully open about underlying hardware and kernel functions, and Java is purposefully open about JVM memory management. So the question becomes very fuzzy.

You may find that some operations are faster in Java, and some not. You never know until you try, however:

In practice, the real differences lie in your higher level algorithms and implementations. For all but the most absolutely performance critical applications, the differences in performance of identical data structures in different languages is completely negligible compared to the performance characteristics of the algorithm itself. Concentrate on optimizing your higher level implementations. Only after you have done so, and after you have determined that your performance requirements are not being met, and after you have benchmarked and found (unlikely) that your bottleneck is in container implementations, should you start to think of things like this.

In general, as soon as you find yourself thinking or reading about C++ vs. Java issues, stop and refocus on something productive.

Answer 3

Java heap is faster because (simplified) all you need to do to allocate is to increase heap top pointer (just like on stack). It is possible because heap is periodically compacted. So your price for speed is:

1. Periodic GC pauses for heap compacting
2. Increased memory usage

There is no free cheese... So while collection operations may be fast, it is amortized by overall slowing down during GC work.

Answer 4

While I am a fan of Java, it is worth noting that C++ supports allocation of objects on the stack which is faster than heap allocation.

If you use C++ efficiently with all it various ways of doing the same thing, it will be faster than Java (even if it takes you longer to find that optimal combination)

If you program in C++ as you would in Java, e.g. everything on the heap, all methods virtual, have lots of runtime checks which don't do anything and can be optimised away dynamically, it will be slower. Java has optimised these things further as these a) are the only thing Java does, b) can be optimised dynamically more efficiently, c) Java has less features and side effects so it is easier for optimiser for get decent speeds.

Answer 5

and Collections are fast. Standard Java beats standard C/C++ in this area, even for most optimized C code.

This may be true for particular collections, but most certainly isn't true for all collections in all usage patterns.

For instance, a java.util.HashMap will outperform a std:map, because the latter is required to be sorted. That is, the fastest Map in the Java Standard Library is faster that the fastest Map in the C++ one (at least prior to C++11, which added the std:unordered_map)

On the other side, a std:Vector<int> is far more efficient that an java.util.ArrayList<Integer> (due to type erasure, you can't use a java.util.ArrayList<int>, and therefore end up with about 4 times the memory consumption, and possibly poorer cache locality, and correspondingly slower iteration).

In short, like most sweeping generalizations, this one doesn't always apply. However, neither would the opposite assertion (that Java is always slower than C++). It really depends on the details, such as how you use the collection, or even which versions of the languages you compare).