[rust-dev] Incremental and generational GC
pwalton at mozilla.com
Wed Jul 10 11:32:08 PDT 2013
(Warning: GC pointy-headedness ahead.)
I've been thinking about what will be needed to support incremental and
generational GC in Rust. To be clear, I don't think we should block on
it now, but we should not make it unduly difficult for us to implement
in the future.
The hard parts of incremental and generational GC are the barriers.
There is a different write barrier regarded for both. (I'm assuming
incremental-update IGC, not snapshot-at-the-beginning, which is a harder
First, some terminology. Consider this picture:
A is the "referrer". Suppose that the mutator mutates it to this:
C is the "referent".
For IGC and GGC, we need some sort of barrier.
For incremental GC, we must maintain the tri-color invariant, which
means that a black object must never point to a white object. There are
two basic ways to do this: either a write barrier graying a white object
referent or graying a black object referrer. In Rust, the latter would
be the easiest to implement: whenever you borrow an `@mut` to `&mut`
(which is what you need to do to mutate) we can gray the object if it's
black. This does mean that we need to make sure that all contents of
`@mut` are Freeze; otherwise, we won't trip the barrier.
For generational GC, we must ensure that objects in the nursery pointed
to by the tenured generation are either added to a remembered set or
tenured. This is harder in Rust because we have to know both the
generation of the referrer and the referent simultaneously. I believe
that conservatively tenuring all objects that are mutated would be
overconservative and defeat much of the purpose of GGC.
The only thing that I can think of that would work is to use the MMU and
do the generational GC barriers on a per-page basis. I believe that this
is what Boehm does in its GGC mode. This to me seems the most risky part
of this; I'm not sure what the performance implications of this are.
Doing this will keep `Gc` and `GcMut` implicitly copyable without custom
copy constructors, which is nice. It is true that we will not be able to
perform the change that was agreed on to change `GcMut<T>` to
`Gc<Cell<T>>`, since `Cell<T>` is not `Freeze`.
More information about the Rust-dev