[hayley-patton]

> Compacting GC needs additional memory to have a room to allocate from, and that amount of memory is substantial unless you want to do more GC than any useful work.

Not in the case of a mark-compact collector, which works entirely in place, or a mark-region collector such as Immix [0], which only copies a small fraction of the heap.

> Also it is not free from fragmentation most of the time - the heap is defragmented only at the moment right after compaction.

An improvement would be to to perform more frequent "partial" collections, such as in the Train algorithm [1]. But some collectors (such as Immix again) avoid compaction until fragmentation is considered bad enough, which seems like a fair compromise.

> And there is internal fragmentation caused by object headers needed to store marking flags for GC - which can consume a huge amount of memory if your data is divided into tiny chunks.

The description of Doug Lea's allocator [2] suggests there are also "object headers" of a sort on allocated data in dlmalloc. You could probably steal mark bits from those headers, but it is commmon to use a separate marking bit/bytemap which is separate to space where objects are allocated, and thus has none of the fragmentation you describe.

[0] https://www.cs.utexas.edu/users/speedway/DaCapo/papers/immix...

[1] https://beta.cs.au.dk/Papers/Train/train.html

[2] http://gee.cs.oswego.edu/dl/html/malloc.html

[pkolaczk]

> Not in the case of a mark-compact collector, which works entirely in place, or a mark-region collector such as Immix [0], which only copies a small fraction of the heap.

The mutator always allocates from a contiguous memory region. It can't allocate from the memory that was logically released, but not yet collected. So it needs more total memory than the amount of live memory in use at any time, unless you have an infinitely fast GC (which you don't have). In order to avoid too frequent GC cycles, or to allow it to run in the background, you need to make that additional amount of memory substantial.

JVM GCs typically try to keep low GC overhead (within single %), which often results in crazy high memory use, like 10x the size of the live memory set.

> but it is commmon to use a separate marking bit/bytemap

Sure, you can place it wherever you wish, but it still requires additional space.

[kaba0]

Your comparison would only be fair if the alternative (malloc/object pool) would not have more memory than strictly necessary either.

But malloc and friends usually do what a very basic GC would (make separate pools for differently sized “objects”).

While object pools also need much more memory unless it is full.

So all in all, GCs do trade off more memory for more efficient allocation/deallocation but that is a conscious (and sane) tradeoff to make for like 99% of applications as memory stored on RAM doesn’t consume much energy compared to doing GC cycles like a mad man. Also, it is quite configurable in case of JVM GCs.

[pkolaczk]

The only overhead memory used by a pool allocator is the rounding to the page size. The difference from a compacting GC is that a pool allocator can allocate from the freed memory immediately after the memory was freed. So the overhead does not depend on the allocation rate, it is just a tiny constant factor.

As for the energy efficiency, I seriously doubt that bringing all memory into cache once in a while, including memory that is not needed frequently by the application, only in order to find live vs dead memory is all that energy efficient. The allocation itself is indeed typically slightly faster but the marking and compaction is additional cost you don't have to pay in manual memory management.

[hayley-patton]

Hence why I'd suggest using partial GCs like the Train, as that would have better locality of reference almost all the time. A generational GC could have similar effects, but nurseries seem to be much larger than caches nowadays, with few exceptions.

[pkolaczk]

Partial, generational or region based GCs still need to scan the whole heap from time to time. By bringing stuff once a while into cache they also push stuff that's actively used out of cache. Those effects are typically not visible in tiny benchmarks that allocate temporary garbage in a loop, but can get pretty nasty in real apps. LRU-cache-like memory use patterns are particularly terrible for generational GCs - because the generational hypothesis does not hold (objects die old).

Also using generational algorithms does not remove the dependency of the memory overhead on the allocation rate. Those techniques improve the constant factor, but it is still an O(N) relationship, vs O(1) for a manual allocator. If the allocation rate is too high there are basically two solutions: (1) waste more memory (use very big nurseries, oversize the heap) or (2) slow down / pause the mutator.

The industry seems to prefer (1) so that probably explains why I never see Java apps using <100 MB of RAM, which is pretty standard for many C, C++ or Rust apps; and 50x-100x memory use differences between apps doing a similar thing are not that uncommon.

[kaba0]

> By bringing stuff once a while into cache they also push stuff that's actively used out of cache.

I may very well be wrong, but I don’t think it is any worse than the occasional OS scheduling/syscall, etc. GCs happen very rarely (unless of course someone trashes the GC by allocating in hot loops)

Also, while a destructor is indeed O(n) it is a cost that has to be paid on the given thread, while GCs can amortize it to a separate thread.

[hayley-patton]

> Sure, you can place it wherever you wish, but it still requires additional space.

I thought we were discussing fragmentation, i.e. where we put marking bits.