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).
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.
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 main 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 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
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 (