Fil's Unbelievable Garbage Collector

Summary

Fil's Unbelievable Garbage Collector Fil-C uses a parallel concurrent on-the-fly grey-stack Dijkstra accurate non-moving garbage collector called FUGC (Fil's Unbelievable Garbage Collector). You can find the source code for the collector itself in fugc.c, though be warned, that code cannot possibly work without lots of support logic in the rest of the runtime and in the compiler. Let's break down FUGC's features: Parallel: marking and sweeping happen in multiple threads, in parallel. The more cores you have, the faster the collector finishes. Concurrent: marking and sweeping happen on some threads other than the mutator threads (i.e. your program's threads). Mutator threads don't have to stop and wait for the collector. The interaction between the collector thread and mutator threads is mostly non-blocking (locking is only used on allocation slow paths). On-the-fly: there is no global stop-the-world, but instead we use "soft handshakes" (aka "ragged safepoints"). This means that the GC may ask threads to do some work (like scan stack), but threads do this asynchronously, on their own time, without waiting for the collector or other threads. The only "pause" threads experience is the callback executed in response to the soft handshake, which does work bounded by that thread's stack height. That "pause" is usually shorter than the slowest path you might take through a typical malloc implementation. Grey-stack: the collector assumes it must rescan thread stacks to fixpoint. That is, GC starts with a soft handshake to scan stack, and then marks in a loop. If this loop runs out of work, then FUGC does another soft handshake. If that reveals more objects, then concurrent marking resumes. This prevents us from having a load barrier (no instrumentation runs when loading a pointer from the heap into a local variable). Only a store barrier is necessary, and that barrier is very simple. This fixpoint converges super quickly because all newly allocated objects during GC are pre...