Java collections faster than c++ containers?

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.