This is the first in a series of posts will discuss why garbage collection is hard, especially for Rust, and brainstorm about solutions to the problems we face.
The relationship between garbage collection (GC) and the Rust programming language has been an interesting one.
GC was originally deeply integrated into the language, complete with
dedicated syntax (good old
@T …). Over time the team found ways to
lessen the dependency on GC, and then finally remove it from the
However, we still want to provide support for garbage collection.
To explain why, I need to define the actual problems we seek to solve. So let us explore the problem space.
… now you have two problems
The Problem Space
Now that we have reviewed what GC is and how it works, let us discuss what GC could mean to Rust.
I have identified two distinct kinds of support that we could provide: “GC” could describe a feature for pure Rust programs, or “GC” could mean a 3rd-party runtime interoperation feature. Let us discuss each in turn.
One GC shared by every crate
We could add a smart-pointer to
libstd, e.g. a
Gc<T> type, that
arbitrary library crates could use as they create or receive instances
T. The intention here would be similar to how
Rc<T> is used:
One does not want to track ownership precisely, but rather treat
ownership as shared amongst all users of a value, and let the runtime
system handle reclaiming the value.
So for example, we might want to write code that looks like this:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
(The above snippet assumes we have extended
box EXPR to an
overloaded operator in the manner similar to that described in
RFC 809, so that
let g: Gc<_> = box EXPR; works, and that
the type inference figures out that all the locals need to be
This results in a stack and heap modelled by this picture.
The GC would be allowed to collect the objects labelled “E”, “G”, and “H” in the picture, since they are not reachable from the roots. (However, the GC is not obligated to reclaim them at any particular time. Usually GC’s provide little guarantees about how soon objects will be reclaimed.)
This kind of feature could be useful in any Rust library.
Advantages of Gc
The main hypothesized advantages over
Copy, which makes it possible to construct types like
(It also has nicer programmer ergonomics in some cases; e.g. some programmers dislike having to write
x.clone()every time they want to make a copy of ref-counted
Gc<T>allows cyclic structure to be reclaimed (e.g. the objects “G” and “H” in the picture above.
Gc<T>might have less overhead than
Rc<T>: every time you clone an
Rc<T>it incurs reference-count overhead, while
Gc<T>just copies the reference.
(However, this stated advantage must be tempered by the realization that GC incurs its own separate overheads, as discussed in the background post.
Drawbacks of one GC for everyone
There are two immediate drawbacks with this kind of collector support.
First, adding it would require that the standard library either
provide a garbage collector (that all clients of
Gc<T> would have to
link in), or at least standardize a fixed API that third-party
collector implementations would have to satisfy to support
In particular, smart-pointers in Rust
require at least support for the
Deref trait, so
that dereferencing expressions like
gc_ref.method() are compiled into code that resolves the
&T reference (and then the subsequent field or method lookup is
performed with respect to that
As a reminder, the signature of the
deref method, before lifetime
fn deref<'a>(&'a self) -> &'a Self::Target (and the
Target type for
Gc<T> would be
T). Thus, the
compiler will ensure that the reference
&'a T we extract from the
gc_ref outlive the
gc_ref itself; this means that the
will be one (of potentially many) root keeping the object from being
reclaimed for the entirety of the lifetime
'a, and thus supporting
Deref trait design on a
Gc<T> could work seamlessly on an
entirely non-moving GC.
However, moving objects complicate
Deref support; now one needs to
ensure not only that the object remains alive, but also that the
&'a T consistently points to the same object that the
Gc<T> pointed to, and that references to substructure
within the object (e.g. a
&Left within a
Gc<(Left, Right)> that
has been deref'ed to
&(Left, Right)) also retain a consistent view
of the heap structure. Doing this at an acceptable cost is difficult;
I may discuss this more in a future post.
Second, it is difficult to provide the ergonomics that one expects
from a smart-pointer type analogous to
Okay, so that’s the outline of the tradeoffs of providing
a “GC for everyone” in
libstd. What about a more limited
GC feature, where the audience is not “every Rust crate”, but instead
just the crates linking to a managed runtime.
GC as Interoperation Feature
That post describes (unchecked) scenarios where one can end up with dangling pointers – that is, they invite unsoundness. Proper support for GC-interoperation in Rust could address this; I will discuss this further down in this post.
Critically, GC-interoperation does not require the same level of
Rc<T> provides. For example, in this context it is
Gc<T> to not support
(Furthermore, in this context, it may even be acceptable to require unchecked constraints like “the programmer must ensure the collector is not invoked during this extent”, or perhaps “the programmer must periodically invoke a call that tells the GC that this is an acceptable time to do collection work that could move objects.”)
Deref trait and with such unchecked requriements, such
interoperation might end up looking something like this:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
In this context, interoperation still requires defining a standard interface that the third-party collector implementation has to conform with.
In truth, even for a conservative collector like BDW,
one must do more than just “swap in a new
#[allocator]” to actually
integrate it properly; the current Rust standard library does not
provide a way to intercept thread spawns and register the new
stack associated with each new thread.
I only realized this only recently. In a simple world (e.g., a conservative collector designed to interoperate with C/C++, such as boehm-demers-weiser (BDW)), this standard interface could be nothing more than just “swap in a different #[allocator] crate that your GC provides.”
(The actual interface is unlikely to be so simple, but the point is, there is a wide design space to be explored here.)
Interoperation with a “black box” GC
One way to look at the difference between “GC for pure Rust programs” versus “GC for interoperation” is that in the former case, the GC feels deeply integrated with the language and standard library, while in the latter case, the GC is clearly the concern of some entity outside the language (and we are just trying to accommodate it as best we can).
An extreme instance of a GC that is definitely an entity outside the language is a case where the whole GC heap is treated like a black box, and the objects inside the heap are never directly exposed to the application code outside the box.
For example, one can imagine a virtual machine (VM) interface where the code outside the VM is never given addresses of objects on the heap. Instead, such foreign code only has handles that indirectly point to those objects.
In this setting, direct references to objects never escape the black box. Instead, by setting up a level of indirection, the management of the objects within the GC heap is completely abstracted away.
In a black box GC setting, one would not expose the data structure of the objects (since they can never be directly addressed anyway). Instead, one would define functions on handles that extract the fields and maps them to handles when necessary:
1 2 3 4 5 6 7 8 9 10 11 12 13
In case it isn’t clear, supporting interoperation with this kind of “black box” GC requires very little from the Rust side; potentially nothing at all. The object addresses are hidden, so the GC could move an object and update its address in the handle array.If the GC Heap is exposed to multiple threads, then there are complications even with the seemingly simple task of updating the handles array, since one must ensure that if two threads have consistent views of the heap object graph.
However, this so-called interoperation is also quite limited in
expressiveness. The defining property of the “black box” GC, the fact
that it does not expose the addresses of the objects held within, also
means that we cannot expose
&-references to the objects or the state
within them, which means we cannot use these objects with the large
number of Rust functions that operate on
&-references and slices.
Digression on limits of “black box” GC
In addition to the limits regarding exposure of
described above, another issue with “black box” GC is that
it is not clear whether client code hooking
into the “black box” GC would be able to instantiate the GC objects
with its own types.
For example, one might think that the objects in the GC heap could be
defined via type parameterization:
fn bbox_gc_alloc<T>(t: T) -> Handle;
would create an object on the heap, copy
t into it, and return a
handle to that object.
For this to work, the layout of the list cells in the GC heap above would need to look something like this:
1 2 3 4
Then constructing a list like the “X, Y, Z” in the heap diagrams above would look like:
1 2 3 4 5
But there are two (related) problems:
How does one instantiate values that unconditionally hold pointers to GC objects. (For example, how do we allocate an instance of
We have already established that the address in the GC Heap are not exposed outside of the heap, so the approach of passing in an
Tvalue that we used with
bbox_gc_allocabove will not work, because we cannot put our hands on a
GcPtrto use for the
How do we get from the
Consto the family of methods defined in terms of
Every occurrence of
GcPtrused for the struct (as seen from the point of view of the GC Heap) needs to be mapped to a
Handlein the functions exposed to the functions outside of GC Heap.
Also, the hidden object addresses may complicate client code trying to instantiate GC objects with its own types.
It could be that there is a solution to the problem lurking here. In any case, interoperation with a blackbox GC is not a primary goal, since the level of indirection and (perhaps more crucially) the maintenance of the handles array are not ideal.
Objectives and Requirements (oh no, now five problems)
The two (or perhaps three) kinds of support described above are distinct features; there is overlap between them, but trying to find a single solution that solves both problems completely may not be possible, and in any case we do not want to wait for that single solution to be discovered.
Rc<T> is already a workable solution for many (though not all)
use cases of
Gc<T>, the above idealized “one GC shared by every
crate” is not a main priority right now (and may never be added to the
Let us focus on GC as an interop feature, and dive into what we would want to get out of it.
There are a number of objectives for Rust/GC integration that are worth noting, which I will list here and then define and discuss below.
Safety with respect to GC
If a Rust crate does not use
unsafe constructs (
attributes or types with “unsafe” in their name, etc.), then linking
it with a sound set of crates that use GC must maintain soundness.
In other words, linking in a crate that uses no
should not inject any dereferences of dangling pointers, nor any data
By the way, we absolutely do need to provide criteria that says what
unsafe code is allowed to do when linked with a crate that uses
GC. I am going to assume for these initial posts that we will solve
that problem eventually, but not attempt to address it at the outset.
Modularity with respect to GC
A Rust program that uses GC should be able to link to a crate whose source code was authored without knowledge of GC.
For example, if I make a parsing library today that works on string
&str, you should be able to link that parsing library into a
program that uses GC, without having to worry about whether the
parsing library carries hidden requirements that invalidate
assumptions made by the GC.
Note: A crate being “authored without knowledge of GC” is a property of the source code, not the generated object code. Given such a crate, the Rust compiler may itself inject metadata related to GC, such as descriptions of object layout, or automatically-generated code that dictate how objects should traced by the collector.
Note: A crate being “authored without knowledge of GC” is entirely distinct a crate not supporting GC. That is, we may add well a way for a crate to declare that it is not compatible with GC. (This would count as having knowledge of GC; in fact, enough knowledge to know, or at least guess, that its presence would cause the GC to break, or vice versa.)
If we cannot satisfy this requirement, then the addition of GC will, at best, split the growing space of library crates (such as those available on crates.io) into two disjoint sub-communities: crates that support GC, and those that do not (since the latter were written without accounting for the potential presence of a GC).
An aside: I would really like to find a way to combine the descriptions of “modularity” and “safety”, since they seem to be attempted to express similar or related objectives.
A final note: There are some features available to crates, such as requiring a specific low-level allocator, that are likely to be incompatible with a program that uses GC. We need to define these caveats and incorporate them into the above definition of “modularity”, without weakening it to the point of uselessness. (However, I will not attempt to tackle that here.)
If you don’t use the GC feature (in whatever form it takes), your code should not pay for it.
This applies to the quality of the generated code (in execution time and code size), and also to the source code, with respect to difficulty in writing a program or library.
There are two forms of the zero-cost property relevant here:
Strongly zero-cost: A unit of code generation that does not use GC should not pay for it.
For example, in the above example of the string parsing module, ideally the code generated for parsing
&strvalues should have the same performance characteristics, regardless of whether it is linked into a program that uses GC or not.
Weakly zero-cost: A program that does not use GC should not pay for it.
(At worst, one can imagine ensuring this property by compiling two different versions of each code unit, and then linking to the appropriate one. Hopefully we will not need to resort to that.)
Strongly zero-cost implies weakly zero-cost, but not vice-versa.
One can use a reference to a gc-allocated object (call it a
as the field type in a
struct, store it into a
in general do anything with it that one can do with a normal Rust value.
Furthermore, one should be able to describe, via a Rust type
definition, the layout of a value allocated on the GC heap, allocate
such values there, and acquire a suitable
GcRef to the allocated
To be concrete about this, consider the following program,
which uses a hypothetical
make_gc_ref function to move
values into a newly-allocated spot on the GC heap, and returns
a reference to that spot. (In the future one will probably use
box syntax for this, and rely on type-context to inform
box that this is a GC-allocation.)
1 2 3 4 5 6 7 8 9
This results in the following diagram:
Here, I have made explicit the heap-allocated backing store
blue) for the vector that holds the references to
This shows that if we want GC to reasonably usable (i.e., allow GC references to be used like other Rust values), we need to support references out of the GC heap and into the Rust heap, and likewise references out of the Rust heap and into the GC heap.
It can sometimes be simpler (without necessarily eliminating the
fundamental problem) to just a
Box rather than a
The program to construct the above picture might look like this:
1 2 3 4 5 6 7 8 9
(The types in the demo program above assume certain features like
T: ?Sized, which may or may not be reasonable.)
The compositionality constraint may seem obvious (especially if one
starts by assuming that references to gc-allocated objects will be
values of type
Gc<T> for arbtrary
But using “black box” GC interop (as described above) would likely defeat compositionality. That is why I point out this objective explicitly.
A 100% precise GC is one that knows the type of every object and field that it encounters, in terms of being able to classify a word of memory as an integer or a pointer, and also classify whether a given word of memory is actually usable according to the type of the value the word is embedded within.
A space-efficient GC, in essence, is one that is eventually able to reclaim all garbage, without being subverted by particular details of the host program or the system state.
(Calling a language implementation space-efficient is a reference to the asymptotic space complexity of a language implementation. I am employing the term here because the objective I want to capture is more general than just precision.)
A conservative GC lacks precision. In other words, a precise GC is more space-efficient than a conservative GC: There exists a program that will exhibit worse (asymptotic) space performance atop a conservative GC than it would atop a precise GC.
We would like Rust to be able to interoperate with 100% precise collectors.
Ideally, we would also like to be able to interoperate with collectors that do not support pinning.
Finally, we would like to ensure that the heap patterns associated with Compositionality do not cause garbage to go unreclaimed.
- Note that a precise GC that treats all objects on the “Rust Heap” as roots is not very space-efficient: it will fail to collect cyclic garbage structure like the below.
In the above diagram, “C” and “O” are unreachable by the program itself (“O” is owned by the gc-allocated “C”), but if you treat all objects in the Rust Heap as roots, then it will classify “O” as a root, and “C” will never be reclaimed.
This is why compositionality can interact with space-efficiency. Allowing gc-allocated objects to own data allocated on the Rust heap, while also allowing references to gc-allocated objects to be stored in values on the Rust heap, then you will encounter cyclic structure like this. (This was the design bug that led me to withdraw my “Take II” allocator RFC.)
This post was dedicated to identifying criteria that we would like GC-integration with Rust to satisfy.
Next up: Why is it hard to satisfy the above criteria simultaneously?