Is it possible to make GC a library?

Question

Motivation

Garbage collection is a critical component of memory management in many programming languages. Many languages have built-in garbage collectors tightly integrated into their runtime environments.

I'm thinking of a pluggable GC library, which can be embedded in different language runtimes, and managed by this library for objects with complex life cycles.

But I encountered a small problem, it is impossible to insert safepoint in the host language, and it would be too inefficient to insert a check call every time any gc object is accessed.

Question

So I wonder if there has been any attempts in the programming languages to separate the GC as a library.

Are there any existing efforts or research on developing a language-agnostic Garbage Collection library, and what are their successes or challenges?

Answer 1

It is indeed possible, and a few already exist

The canonical light-weight way to add some sort of automatic memory management to an environment that doesn't offer it is via reference counting (shared_ptr<T> in C++, Rc<T> and Arc<T> in Rust), but based on a comment you made below your answer you want a tracing collector. It's worth noting you can add code to make a reference counting system correctly clean up cycles like in CPython's garbage collector. Another answer here mentions Bacon and Rajan's paper on how to do this, which is worth a look.

The two that comes to mind that have seen actual use by major projects are Boehm-Demers-Weiser conservative collector (C) and the Oilpan garbage collector (C++).

Boehm

The Boehm-Demers-Weiser collector (normally called Boehm) is probably the closest to what I imagine you wanting here, as it does not require significant changes to what a normal C codebase might look like, aside from replacing malloc() calls to GC_malloc() (the library author suggest possibly using macros for replacing the usual C allocation functions, but I'm not sure if that wouldn't cause issues on some platforms).

It does this through conservative garbage collection, which involves treating word-sized values on the stack and in the Boehm-GC managed heap as roots, and then performing tracing on them. The disadvantage of that is that this will also treats non-pointer values as pointers, and if they happen to have the same bit-level representation as a pointer to a region of memory that does not have any other live references to it, it will keep that memory alive and not collect it (and in turn, potentially keep other objects that would be collected alive as well). A precise garbage collector (which most garbage collected systems use) would have a way of telling a pointer and non-pointer value apart (or whatever the equivalents would be), and not cause these sort of memory-leak-like situations.

However, to add more complex features like finalizers, you are going to be adding more complexity to your runtime regardless.

Oilpan

Oilpan was designed for collecting objects used by Chromium's web renderer not directly handled via the V8 Javascript engine, and has since been released as a standalone open source library. It performs a combination of conservative garbage collection on the stack with precise garbage collection on heap allocated objects that implement a specific interface via inheritance. Conservative collection on the stack is still a disadvantage, but you are less likely to see cycle of pointer-looking like integers that happen to keep together other live objects.

I'm not very familiar with it, but unlike Boehm it does require making changes to the objects you want to managed by the collector; this sample shows the general shape of it.

Is this worth it?

I think it is worth going over the negatives of pulling or creating a general purpose library for memory management instead of building a collector yourself or taking advantage another host runtime like the JVM or the CLR.

Since you probably have a much better understanding of what the particular contours of your language runtime, how it is used, expected performance characteristics and platforms, and what the object model looks like, you can create a collector that is more tuned and efficient for your purposes. This is the advantage of that level of tight integration with a language runtime that might make a particular GC implementation difficult to port to another language.

Oilpan happens to have some of these platform-specific optimizations -- Oilpan was built around being embedded in a browser with an event loop, and thus has a second optionally-triggerable collection cycle based on the assumption that no pointers to Oilpan objects are present on the C stack, and thus a fully precise collection cycle that only scans the heap can be performed.

On the other hand, if you are compiling or building a language for an existing runtime, you get the advantage of a garbage collector that has had thousands (if not millions) of engineer hours powered into it for multiple platforms, which is a pretty huge boon given the sort of complexity that goes into making efficient garbage collectors.

Other libraries

After posting this answer, I was informed of the existence of The Memory Management Toolkit (Rust, with bindings) that does provide hooks for inserting object write barriers and safe points, as well as the Ravenbrook MPS Library(C). I'm not very familiar with either of them, but I feel like I should add these after being informed of them as possible resources.

Answer 2

It can, but perhaps shouldn't be.

As I mentioned in a comment, it's fairly easy to make ARC as a library feature, such as C++ shared_ptr. However, this is asking about fully automatic GC, which doesn't require weak pointers.

It is possible to extend ARC to collect cycles as well; see this paper for one possible algorithm. In theory, this kind of garbage collection could also be done in a library; you just change what the implementation of shared_ptr::~shared_ptr looks like.

However, it comes with a drawback. With shared_ptr, you don't pass around a T& or T* directly; you must use shared_ptr<T> everywhere (or at least everywhere you want the reference counter to be aware of). This means that if there's no standard type, competing implementations may arise, and libraries will run into one of two problems:

1. Some libraries are incompatible due to the fact that they use different GC types.
2. Libraries that want to be usable by multiple systems will have to use templated code everywhere.

Solution (2) works with C++-style checked-at-usage templates, but not with Java-style checked-at-declaration generics: the latter would require all garbage collectors to inherit from the same interface, and we're back to needing a common type.

Answer 3

The Boehm–Demers–Weiser garbage collector is a conservative garbage collector that doesn't depend on much language support; in C, you simply include the header file and call GC_MALLOC() instead of malloc. As a conservative garbage collection, it considers any value that's a possible pointer an actual pointer, which means it can't move data (since it can't changes pointers) and if an integer would point into garbage space, that integer will prevent the Boehm garbage collector from collecting that garbage. It was used in GCJ's implementation of a Java compiler (ahead of time, to machine code.)

Official Website

Answer 4

A different approach from Boehm & Oilpan, and their conservative stack-scanning, is the one taken by piccolo, a Lua runtime implemented in Rust, for which the GC has been extracted into the gc-arena library.

piccolo structures its runtime in a stackless approach (think async/await) so that the stack is regularly "unwound" and control returned to the runtime.

During execution of the stackless coroutine, there may be pointers on the stack, calls into other languages (C, Rust, ...) making any GC task non-trivial as some pointers may be hiding in registers, or anywhere on the stack.

On the other hand, once control is returned to the runtime and the task suspended, the portion of the stack that belongs to the task -- not the runtime -- has been serialized into the task suspended state... where a single root pointer can exist, from which the GC can start tracing.

Advantages:

• Precise.
• Simple.
• Small.

Disadvantages:

• Single-threaded.
• Stackless requirement: a long-running task not surrendering control to the runtime may lead to OOM.

I personally find the approach interesting, and it works well in the context of piccolo which is single-threaded anyway.

Answer 5

There exists an SGCL library for the C++, which allows to create objects managed by a precise, tracking GC.

Answer 6

Is the language required to be able to implement its own runtimes and library?

If it is, then leaving aside the CS arguments and looking at it from an engineering viewpoint, then there has to be a level at which GC isn't used since otherwise it would be unable to implement GC: whether built into the runtime support or available as a library.

Hence for a language able to implement itself, without relying on a lower-level "systems" language like C, it must be possible to decouple GC to a sufficient extent that it could be put in a library.

Answer 7

Integrating a garbage collector into a language offers a number of significant advantages, especially if the implementation can "stop the world" at least momentarily, and/or managed entities include things that have value semantics. These advantages will be unavailable to a GC a language implementation doesn't "know about".

When using a robust GC library, it's necessary that every action which creates or destroys a reference adjust a counter or other data structure that can make it possible for the GC to determine whether any live references exist. In multi-threaded code, ensuring memory safety in the presence of potential data races would make it necessary that many such actions be synchronized between threads, making them expensive.

When running something a managed .NET program, by contrast, the machine code to copy a reference from a field one one object that's identified in a register, to a field in another object that's identified in a register, takes two instructions--a load and a store. This machine code would need to be accompanied with some metadata indicating that whichever register is used as a temporary might hold the only copy of the reference that exists anywhere in the universe between the time the load has finished and the store has executed, and the GC would need to parse that metadata if a GC cycle happens to be triggered between the load and the store, but during the time the when the program is is doing things other than running the GC, such metadata would just sit idle and not take any CPU cycles to "process" (i.e. ignore).

If thread safety isn't required, library-based approaches can be useful for managing references to shared immutable data structures, but approaches that work very well in single-threaded applications may not be very adaptable to multi-threaded ones.

Personally, I'm a big fan of scanning GCs because they offer a major advantage over other forms: they can maintain as an invariant--even in the presnece of race conditions--that every reference that will ever be observed will be a valid reference to some particular object at all times when it isn't null, and as a consequence of this they can guarantee that nothing which appears to be a reference to one object will ever appear to become a reference to a different object, unless the storage location holding the reference is changed. If one has a reference to an open File object and one closes it, any copies of that reference will now be a valid references to a closed file object, but the storage which records that their target is a File object will be retained as long as the reference exist in any form that might be observed.

If one is considering omitting GC support from a language on the basis that it could be made a library feature instead, I would suggest that one include within the language enough "hooks" to allow a GC library to offer the same semantic benefits as a built-in GC(*), even if the language implementation itself doesn't include everything that would be needed to make the GC functional.

(*) For example, a language might include a mechanism by which a type can indicate that the GC will need to know of what instances exist, and by which a GC can pass a callback to an implementation-supplied function which will invoke the callback with references to all objects of such types that are held in temporary storage the compiler knows about. The compiler wouldn't need to care about how the GC was going to make use of this information, and the GC wouldn't need to care about how the compiler produced it, but the two working together would accomplish what needs to be done.

Answer 8

a language-agnostic Garbage Collection library

It's important to realize that, in a system programming language like C, even if the GC lib is language-agnostic, any 3rd-party library used by the program may still conflict with the said GC lib - any 3rd-party library may have its own GC conventions.

For high-level languages that have its own GC, the GC is typically one of the overarch components of the language implementation, and most often, it's part of the language, just like the rest of the language such as type system, control transfer (async/await, etc.). This way, 3rd-party libraries can be written in the said language in a way agnostic to the garbage collector.

So instead of a GC library, I think a GC framework may be more useful. In such framework, GC operations are not fully implemented - they are functional, but need language/runtime-specific details filled in to be complete.

For example:

• A mark-and-clean subroutine may be provided with details such as implementation data structures of various types of objects allocated from heap to be "precise".

• An entry point may be provided for the language implementation to register lexical variables as starting points of the mark-and-clean subroutine.

• Another entry point can be provided for the language implementation to invoke to execute the garbage collection. It can happen whenever a brace block is exited, a function returns, or several times some (combinations) of these things happen.