High-performance garbage collection for C++

> You don't need the absolute best GC's when your language doesn't create the same amount of GC-pressure.

Conversely, if you language (e.g. LISP) does create a huge amount of GC-pressure, it will lead to the development of the absolute best of GC technology.

Edit: no need to downvote this, it won't change the fact that both GC itself and generational GC in particular was invented specifically to make it possible to run LISP programs on the actual existing hardware in reasonable time.

Title misses a (2020)

One thing that people almost 100% of the time miss in the Java vs C# generics discussion, is that .NET was actually being designed with generics support, but they weren't ready on time for the 2001 launch, and there were some internal fighting of they should even be delivered, thus the work was only finalised on time for .NET 2.0.

This is documented by one of the authors, Don Syme of F#'s fame, on his blog posts and the F# HOPL paper.

Meanwhile Java went through Pizza and other alternative proposals until landing were it did.

However from my point of view both ecosystems could have been much better on version 1.0, had they taken the learnings from Cedar, Modula-3, Eiffel, Sather and Oberon, among other predecessors, regarding AOT compilation and value types, in GC enabled languages.

The C++ way is unique_ptr, which covers about 80% of the needs and in cases where it works it is probably better than a GC. Shared_ptr covers about 15% of the cases, but that still leaves 5% where you need a full better GC.

GC is another runtime dependency (or a really complex intrusive addition to your code), so if you don't absolutely need it I would avoid it in C++. A lot of C++ programs can avoid it with careful design.

If you need a better GC anyway, in the real world modern GC algorithms are likely more performant for your use case than shared_ptr. Thus shared_ptr should be thought of as the C++ answer only because a "real" GC is hard to implement, but if you implement a real GC anywhere just use it to replace shared_ptr as well. (I lean to use unique_ptr even when GC is available, but I reserve the right to change my mind if someone presents evidence)

I've spent the last few years on a library-only collector for C++ (SGCL, https://github.com/pebal/sgcl), also non-moving, so a few data points on the "can it compete" question. Disclosure up front: my project, and measured so far only on Apple Silicon/macOS, one machine, nothing tuned.

On the sweep: it's true that a non-moving collector's sweep is proportional to the number of dead objects, and a moving one's isn't. In practice that cost is small and parallel: the sweep walks per-page state bitmaps (about 1 ns per object), runs the destructors of the dead objects, and is spread over helper threads while the mutators keep running - nobody waits for it. What moving actually buys you is bump allocation and locality. Per-type pages with thread-local free bitmaps get allocation to about 5 ns per object on one thread and 9 ns on 24 threads, without a pause and without moving anything; ZGC does 3.6 ns and 26 ns on the same machine. On binary-trees at depth 21, ZGC is ahead on one thread (2.5 s vs 4.5 s) but with a 1.1 GB heap against 340 MB, and on four threads they tie (1.6 s each). Go, which is also non-moving, sits at 6.3 s / 219 MB there. So "non-moving" is not what decides it; the cost of the barrier, the marking and the sweep spread over cores decides it.

On destructors: they run on the collector's threads, in parallel, not on one thread, and the rule is the same as Oilpan's - a destructor must not touch other managed objects, because they may be dying in the same sweep. I don't have a Clang plugin to enforce it statically; there is a runtime check in debug builds and an explicit escape hatch (if_alive()) for the one legitimate case, a destructor asking whether a peer is still there. Oilpan's static verification is the nicer answer to that particular problem.

Where the approaches really differ is how the collector finds the pointers. Oilpan needs a Trace() method per class (or, as someone suggested above, reflection to generate them). SGCL builds a pointer map per type at runtime by elimination - a word that is ever found holding a value that isn't a managed address is data and leaves the map for good - so plain structs with tracked pointers in them just work, at the price of a couple of rules (no union of a pointer with data, stacks scanned conservatively). Different trade-off, not obviously worse.