High Performance Garbage Collection

Question

I am new to garbage collection but have been looking around. I have noticed that Reference Counting has a very bad reputation (PHP, Python), as well as Conservative GC (Ruby) under certain conditions. However, I have also seen papers describing Fast Conservative GC and Fast Reference Counting. I am wondering if in the modern day there are any standards for high-performance garbage collection (other than to not do it at all).

Answer 1

Different GC algorithms have different tradeoffs. Some optimize for high throughput, others for low latency. There is no single best algorithm, so platforms like the Hotspot JVM are very tunable and allow you to select a profile that fits your expected workload. A good GC algorithm will try to self-tune itself to the actual workload, but of course this only pays off for long-running processes. Modern GC algorithms will also often work in a separate thread in order to minimize pauses, but that involves higher CPU overhead.

Refcounting is not a particularly attractive solution when we look at the numbers. It is low-throughput, has unbounded pause times, and has a memory overhead per managed object. But unlike normal GC algorithms, it allows for deterministic destruction (i.e. patterns like RAII in C++). This makes it attractive when we also want to manage non-memory resources like file handles, without having to explicitly close them or having to use a special syntax like using (C#), try-with-resource (Java), or with (Python). It's also easy to retro-fit into an existing system, especially when we want to mix unmanaged with managed memory. Therefore, Objective-C (any object), C++ (std::shared_ptr), and Rust (Rc, Arc) allow you to (explicitly) opt-in to refcounting. Manual refcounting is a common pattern in C APIs. So it is a wonderful pattern that will not be displaced by other algorithms, but its performance is not competitive with state-of-the-art GC.

The paper you cite does show that RC can be competitive to tracing GC, but they do not seem to be using deterministic destruction. Under that relaxed constraint and with support of a JVM runtime, they are able to eke out significant optimizations. This is inapplicable in most scenarios where RC is currently being used.

Answer 2

A lot of the question depends on what you mean by 'high-performance'. As amon notes, there are various approaches with different costs and benefits. A lot of why people think GC is slow or otherwise problematic has to do with using, say, a setup optimized for throughput when low latency is required.

One common approach is to use generational collectors which use different algorithms in different generations. Hotspot (exclusing G1) uses a copy-collector for the young generation. Copy collectors are extremely fast at collecting dead objects but are inefficient in terms of memory. For example, my team has a caching server with an extremely large young generation. This allows for collections of multiple GB of dead objects in a fraction of a second. Over months, the total pause time for GC is less than a half a minute or so. In terms of speed, this is pretty high performance but in order to make that happen, we need nearly twice as much memory than available heap. In terms of memory, it's pretty low performance.

I highly recommend watching (and re-watching) this presentation if you want to understand the basics of garbage collection. I'd wager Gil Tene knows as much about GC as anyone on earth, if not more.

Answer 3

I am wondering if in the modern day there are any standards for high-performance garbage collection (other than to not do it at all).

There are many GCs optimised for different things.

The JVM and CLR GCs are highly regarded (person-centuries of development effort) and mostly optimised for imperative OOP languages Java and C#, respectively. The CLR has actually also been optimised for F# and purely functional data structures with extremely high allocation rates of tiny short-lived objects.

OCaml and Go are more specialized designs that both excel at low latency server and systems code.

My personal belief is that the combination of reified generics and value types (ala .NET) and a non-moving mark-region GC could give even better performance on modern programs primarily because the world is moving away from OOP to more data centric styles where it is comparatively easy to aggressively unbox leading to much lower allocation rates and vastly less short-lived garbage. With a mark-region GC short-lived garbage is more expensive but longer lived garbage is cheaper because survivors are not marked, copied and all references to them updated. I wrote a prototype mark region GC along these lines and got encouraging results: http://flyingfrogblog.blogspot.com/2010/12/towards-mark-region-gc-for-hlvm.html

Answer 4

Copying generational garbage collectors in practice performs usually well (read about Cheney's algorithm, then read the GC handbook), and favors quick allocation and en masse disposal of young, temporary, values.

Garbage collection is a mature topic (but still a research one). It is fairly well understood. The principles behind GC are quite simple, but implementing a good GC is a lot of work.

For a hobby project, I would suggest using some existing GC library (notably Boehm GC, or Ravenbrook MPS - which is complex but can be tuned to be very fast; see also this review of several existing GCs). Or write your own simple, mark&sweep, garbage collector (which would be much slower than most existing ones).

By personal experience (notably in my old GCC MELT project), writing and debugging a generational copying GC is a lot of work (even if the design principles are simple), and there is a strong coupling between such a GC and allocation or mutations of GC-ed values. In particular, the code using such a GC has to be in A-normal form.