Java collections faster than c++ containers?

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

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.