Is there a garbage collection algorithm that meets these requirements?

Question

I am writing a compiler for a statically-typed object-oriented language. Currently I'm researching garbage collection algorithms to use. I'm wondering if there's a collector that is:

• Open source and documented, so that I can implement it.
• Acurrate
• Generational
• Global, i.e there is only one collector per process, as opposed to say one per thread.
• Incremental and/or concurrent, to avoid long pauses from major collections.
• Fits with this programming paradigm. An example of what doesn't would be a collector which becomes very slow in presence of destructive assignment.

Edit: To clarify, I was wondering if there's an implementable algorithm that does this, not if there's an off-the-shelf collector.

Answer 1

There's one not-at-all-experimental garbage collection algorithm that actually meets all your requirements: simple automatic refcounting. On the whole, refcounting really doesn't get enough credit as a viable option, but actually it works really nicely in many situations, there are never any big batch delays, and there's no need for complicated magic.

One concern is still cleaning up circular references, which you can at least leave to be done extremely rarely; app developers who care about speed can just explicitly break the loops when they need the objects to go away.

A little-appreciated feature of refcounting is that it's much more dcache-friendly than other forms of garbage collection. If you're running a loop that allocates some small temporary objects every time through the loop, a refcounting GC (or explicit memory management, of course) can reuse the same memory each time, avoiding unnecessary cache flushes. Any other kind of GC would only free up the objects periodically, resulting in a much bigger memory footprint and therefore slowness.

Refcounting is not very efficient for heavily multi-threaded systems, because you need to acquire locks every time you touch the refcount. But if you're designing a new language anyhow, there's one huge thing you can do to improve performance and reliability all over your language: prevent almost all objects from being shared between threads. ie. make sharing explicit. If you do that, you will know which objects are vs. aren't shared, and therefore which ones need to be locked when incrementing/decrementing the refcount and which can be left unlocked. When there isn't any locking, refcounting performance can be really excellent.