Java Heap Allocation Faster than C++

Question

I already posted this question on SO and it did ok. It was unfortunately closed though(only needs one vote to reopen) but someone suggested I post it on here as it is a better fit so the following is literally a copy paste of the 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 is an interesting question, and the answer is complex.

Overall, I think it is fair to say that the JVM garbage collector is very well designed and extremely efficient. It's probably the best general purpose memory management system.

C++ can beat the JVM GC with specialised memory allocators that are designed for specific purposes. Examples might be:

• Per-frame memory allocators, which wipe the whole memory area at periodic intervals. These are frequently used in C++ games, for example, where a temporary memory area is used once per frame and immediately discarded.
• Custom allocators managing a pool of fixed-sized objects
• Stack based allocation (although note that the JVM also does this in various circumstances, e.g. via escape analysis)

Specialised memory allocators are, of course, limited by definition. They usually have restrictions on object lifecycle and/or restrictions on the type of object that can be managed. Garbage collection is much more flexible.

Garbage collection also gives you a some significant advantages from a performance perspective:

• Object instantiation is indeed extremely fast. Because of the way that new objects are allocated sequentially in memory, it often requires little more than one pointer addition, which is certainly faster than typical C++ heap allocation algorithms.
• You avoid the need for lifecycle management costs - e.g. reference counting (sometimes used as an alternative to GC) is extremely poor from a performance perspective since the frequent incrementing and decrementing of reference counts adds a lot of performance overhead (typically much more than GC).
• If you use immutable objects, you can take advantage of structural sharing to save memory and improve cache efficiency. This is used heavily by functional languages on the JVM like Scala and Clojure. It is very difficult to do this without GC, because it is extremely hard to manage the lifetimes of shared objects. If you believe (as I do) that immutability and structural sharing are key to building large concurrent applications, then this is arguably the biggest performance advantage of GC.
• You can avoid copying if all types of object and their respective lifecycles are managed by the same garbage collection system. Contrast with C++, where you often have to take full copies of data because the destination requires a different memory management approach or has a different object lifecycle.

Java GC has one major downside: because the work of collecting garbage is deferred and done in chunks of work at periodic intervals, it causes occasional GC pauses to collect garbage, which can affect latency. This is usually not a problem for typical applications, but can rule Java out in situations where hard realtime is a requirement (e.g. robotic control). Soft realtime (e.g. games, multimedia) is typically OK.

Answer 2

The main reason is that, when you ask Java for a new lump of memory,it goes straight to the end of the heap and gives you a block. In these way, memory allocation is as fast as allocating on the stack (which is how you do it most of the time in C/C++, but apart from that..)

So allocations are fast as anything but... that doesn't count the cost of freeing the memory. Just because you don't free anything until much later doesn't mean it doesn't cost quite a lot, and in the case of GC system, the cost is quite a lot more than 'normal' heap allocations - not only does the GC have to run through all objects to see if they're alive or not, it also then has to free them, and (the big cost) copy the memory around to compact the heap - so you can have the fast allocation at the end mechanism (or you'd run out of memory, C/C++ for example will walk the heap on every allocation looking for the next block of free space that can fit the object).

This is one reason why Java/.NET benchmarks show such good performance, yet real-world applications show such bad performance. I only have to look at the apps on my phone - the really fast, responsive ones are all written using the NDK, so much so even I was surprised.

Collections nowadays can be fast if all the objects are locally allocated, eg in a single contiguous block. Now, in Java, you simply don't get contiguous blocks as objects are allocated one at a time from the free end of the heap. You can end up with them happily contiguous, but only by luck (ie down to the whim of the GC compaction routines and how it copies objects). C/C++ on the other hand explicitly supports contiguous allocations (via the stack, obviously). Generally heap objects in C/C++ is no different from Java's BTW.

Now with C/C++ you can get better than the default allocators which were designed to save memory and use it efficiently. You can replace the allocator with a set of fixed-block pools, so you can always find a block that is exactly the right size for the object you're allocating. Walking the heap just becomes a matter of a bitmap lookup to see where a free block is, and de-allocation is simply re-setting a bit in that bitmap. The cost is that you use more memory as you allocate in fixed-size blocks, so you have a heap of 4 byte blocks, another for 16 byte blocks, etc.

Answer 3

Eden Space

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

I've been studying a bit about how the Java GC works since it's very interesting to me. I'm always trying to expand my collection of memory allocation strategies in C and C++ (interested in trying to implement something similar in C), and it is a very, very fast way to allocate a lot of objects in a burst fashion from a practical perspective but primarily due to multithreading.

The way the Java GC allocation works is to use an extremely cheap allocation strategy to initially allocate objects to "Eden" space. From what I can tell, it's using a sequential pool allocator.

That's a whole lot faster just in terms of algorithm and reducing compulsory page faults than general-purpose malloc in C or default, throwing operator new in C++.

But sequential allocators have a glaring weakness: they can allocate variable-sized chunks, but they can't free any individual chunks. They just allocate in a straight sequential fashion with padding for alignment, and can only purge all the memory they allocated at once. They're useful typically in C and C++ for constructing data structures which only need insertions and no removals of elements, like a search tree which only needs to be built once when a program starts and then is repeatedly searched or only has new keys added (no keys removed).

They can also be used even for data structures that allow elements to be removed, but those elements won't actually be freed from memory since we can't deallocate them individually. Such a structure using a sequential allocator would just consume more and more memory, unless it had some deferred pass where the data was copied to a fresh, compacted copy using a separate sequential allocator (and that's sometimes a very effective technique if a fixed allocator won't do for some reason -- just straight up sequentially allocate a new copy of the data structure and dump all the memory of the old one).

Collection

As in the data structure/sequential pool example above, it would be a huge problem if Java GC only allocated this way even though it's super fast for a burst allocation of many individual chunks. It wouldn't be able to free anything until the software is shut down, at which point it could free (purge) all the memory pools all at once.

So, instead, after a single GC cycle, a pass is made through existing objects in "Eden" space (sequentially allocated), and ones that are still referenced then get allocated using a more general-purpose allocator capable of freeing individual chunks. Ones that are no longer referenced will simply be deallocated in the process of purging. So basically it's "copy objects out of Eden space if they're still referenced, and then purge".

This would normally be quite expensive, so it's done in a separate background thread to avoid significantly stalling the thread that originally allocated all the memory.

Once memory is copied out of Eden space and allocated using this more expensive scheme that can free individual chunks after an initial GC cycle, the objects move to a more persistent memory region. Those individual chunks are then freed in subsequent GC cycles if they cease to become referenced.

Speed

So, put crudely, the reason the Java GC might very well outperform C or C++ at straight heap allocation is because it's using the cheapest, totally degeneralized allocation strategy in the thread requesting to allocate memory. Then it saves the more expensive work that we would normally need to do when using a more general allocator like straight-up malloc for another thread.

So conceptually the GC actually has to do overall more work, but it's distributing that across threads so that the full cost is not paid upfront by a single thread. It allows the thread allocating memory to do it super cheap, and then deferring the true expense required to do things properly so that individual objects can actually be freed to another thread. In C or C++ when we malloc or call operator new, we have to pay the full cost upfront within the same thread.

This is the main difference, and why Java might very well outperform C or C++ using just naive calls to malloc or operator new to allocate a bunch of teeny chunks individually. Of course there is typically going to be some atomic operations and some potential locking when the GC cycle kicks in, but it's probably optimized quite a bit.

Basically the simple explanation boils down to paying a heavier cost in a single thread (malloc) vs. paying a cheaper cost in a single thread and then paying the heavier cost in another that can run in parallel (GC). As a downside doing things this way implies that you require two indirections to get from object reference to object as required to allow the allocator to copy/move the memory around without invalidating existing object references, and also you can lose spatial locality once object memory is moved out of "Eden" space.

Last but not least, the comparison is a bit unfair because C++ code doesn't normally allocate a boatload of objects individually on the heap. Decent C++ code tends to allocate memory for many elements in contiguous blocks or on the stack. If it allocates a boatload of tiny objects one at a time on the free store, the code is shite.

Answer 4

This is not a scientific claim. I am simply giving some food for thought on this issue.

One visual analogy is this: you are given an apartment (a residential unit) which is carpeted. The carpet is dirty. What is the fastest way (in terms of hours) to make the apartment's floor sparkling clean?

Answer: simply roll up the old carpet; throw away; and roll out a new carpet.

What are we neglecting here?

• The cost of moving out existing personal belongings and then moving in.
  • This is known as the "stop-the-world" cost of garbage collection.
• The cost of the new carpet.
  • Which, coincidentally for RAM, it is free.

Garbage collection is a huge topic and there are plenty of questions both in Programmers.SE and StackOverflow.

On a side issue, a C/C++ allocation manager known as TCMalloc together with object reference counting is theoretically able to meet the best performance claims of any GC system.

Answer 5

It all depends who measures the speed, what implementation's speed they measure, and what they want to prove. And what they compare.

If you just look at allocating / deallocating, in C++ you might have 1,000,000 calls to malloc, and 1,000,000 calls to free (). In Java, you would have 1,000,000 calls to new () and a garbage collector running in a loop finding 1,000,000 objects that it can free. The loop can be faster than the free () call.

On the other hand, malloc / free have improved other time, and typically malloc / free just sets one bit in a separate data structure, and is optimised for malloc / free happening in the same thread, so in a multithreaded environment no shared memory variables are used in many cases (and locking or shared memory variables are very expensive).

On the third hand, there are things like reference counting which you might need without garbage collection, and that doesn't come for free.