RFC: Pauseless Concurrent Garbage Collector


#1

So for about 3 months I’ve been mulling over an idea for how to create a garbage collection runtime in Rust. My first 1100 lines of Rust have been in prototyping parts and I finally feel that I have something worth discussing (and a decent handle on types and the borrow checker!)

A key reason we love Rust is that it doesn’t have a garbage collector that pauses execution ever, making it suitable for realtime applications. This proposed GC never pauses execution.

I invite you to read the RFC linked below and to discuss in the associated github issue.

Summary

Application threads maintain precise-rooted GC-managed pointers through smart pointers on the stack that write reference-count increments and decrements to a journal. The reference-count journal is read by a GC thread that maintains the actual reference count numbers in a cache of roots. When a reference count reaches zero, the GC thread moves the pointer to a heap cache data structure that is used by a tracing collector.

Because the GC thread has no synchronization between itself and the application threads besides the journal, all data structures that contain nested GC-managed pointers must be immutable in their GC-managed relationships: persistent data structures must be used to avoid data races.

I’m personally excited about this project and I appreciate any feedback and discussion!

~p


#2

Might want to also look at http://github.com/fitzgen/rajan-bacon-cc, which implements (plans to implement?) the Bacon algorithm.

The journaling channel is something we thought of using in rust-gc (pull request) but we never got around finishing it. Nice to see more efforts in this area!

Couple of questions:

  • How do you handle destructors? A destructor can potentially re-root an object, the ideal solution needs something like Java’s finalize() (not exactly guaranteed to run like a regular destructor).
  • How do you plan on handling internal mutability? Custom cell types for rootable objects, or does your planned design manage to log mutations as well?

#3

Interesting, it could work, although I think the immutability of all GC objects is far too restrictive in practice: you don’t even need GC with that restriction, since you won’t be able to create cycles! You’ll need to bound all GC objects by an unsafe trait which extends Send + Sync, as your requirements are a strict superset of those.

I also think the “buffer time” you descibed to prevent out-of-order dec/inc pairs is far too weak a guarantee for many situations. I’m not sure it’s even strictly necessary: channels preserve order for any given sender, so the only way out of order decs is a problem is if the count drops to zero on one thread, and then increases from zero on another: without weak references, there’s no way that can happen (you’d have to send a Gc<T> between the threads, but that gc pointer itself would ensure the reference count remains at least one). Even with weak references, it’s still not a problem, as the GC must have some way to track those references anyway, in order to clear them when the object is destroyed.

If you do allow mutability, there are a lot more problems to deal with. Firstly, destructors: in the case of a cycle there is no valid order in which to call destructors. You could solve this the same way Arc/Weak does, but having all mutable GC pointers act like Weak at destruction time, in that they may already be cleared - this also gives the programmer some control over the destruction order, which is normally completely undefined.

@Manishearth destructors are not a problem in the current formulation: as long as they don’t take a Gc<Self> param, they have no way to reroot themselves (at most they can move themselves, but that would count as a different object to the gc).


#4

Why can’t they reroot themselves?

If I have Root -> A -> B, Root -> B, and A goes out of scope, the GC will try to clear it up. But, if A's destructor does self.b.some_field.borrow_mut() = Some(self) then A would be cleaned up.

Oh, wait, the current formulation is immutable. Sure, that works, but for most interesting cases you at least need interior mutability, which complicates rooting (not too much) and destructors (a lot). Without mutability you can’t make cycles anyway, so a GC isn’t too useful (which is why I assumed it would be extended to be mutable)


#5

To address the question of cycles in immutable data structures, a form of lazy reference could be used to create cycles.

Regarding finalization, even with immutable data structures a custom drop() on an object can be written to try to dereference already freed pointers. I can’t think of a compile-time way to avoid this with the current Rust language feature set. @Manishearth I assume you have the same issue in rust-gc?

I described my thoughts on lazy references in more detail on the associated RFC issue. I’d appreciate any further thoughts on this.


#6

(Cross-posted to the reddit thread)

It looks like it’ll really help for me to explain my motives much more clearly (which should have been obvious in hindsight.)

My personal interest in this project is to build other programming languages on top of Rust. A lot of popular interpreted languages are built on C, require a GIL of some kind and allow global mutable state all too easily. Generally those languages have been written to solve the problem of needing an easy-to-program-in language or wanting a certain style of programming and much later projects such as pypy have come along later to attempt to address some of the shortfalls in some way.

I’m interested in taking the opposite approach: building a platform for other languages designed from the ground up to inherit or reproduce at least a subset of the safety guarantees Rust itself provides.

So immutable data structures with a GC that doesn’t need to STW (which feels GILish) seems like an excellent trade-off to me, especially for interpreted languages where you accept a degree of performance degradation already.

I’ve offered a possible solution to the impossibility of cycles in immutable data structures on the RFC discussion issue.

The immutability problem is restricted to GC-managed objects that reference other GC-managed objects. For a GcRoot<Vec<u64>> the Vec can still be mutable. Of course when sharing that mutably across threads, there would still be a need to resort to locking. Perhaps something like arc::get_mut could actually be safe though…

Clearly I haven’t thought everything through, which is why I wanted to reach out for feedback :smiley: I appreciate all the questions and comments, it’s all been very helpful so far.


#7

Writing a GC is hard, I never tried, but I know how hard .NET folks have been working on it (55k lines of code).

It’s slightly more complicated than counting references in a thread-safe manner. One thing to figure out for example, is how to handle circular references, which has always been the main limitation of smart-pointers. To resolve this, I don’t see any other solution but to maintain a graph of references between instances.

There must be a lot of other constraints that comes if you are not planning to alter the compiler. If you manage to build a proof of concept I’ll be happy to have a look.


#8

Having used garbage collected languages all my life and then discovering RAII, what do you need a garbage collector for that Rc/Weak and Arena won’t give you?


#9

Weak is fiddly to work with, and only works if you know what your directed graph of pointers is going to look like beforehand. This may not always be the case. Gc is a hassle-free way of managing complicated data. (quite useful for writing an interpreter for a GCd language, for example). One shouldn’t need to use it a lot, but when one does need it, it would be nice to have a couple of working GC libs.

It’s sufficient to traverse the existing graph of references; you don’t need to maintain a separate one.


#10

I don’t think that it suffices for a garbage collector not to pause execution.

Two behaviors that make GC languages intolerable for many system programming tasks are:

  1. Allowing an unconstrained amount of garbage to accumulate, killing performance where unused memory is needed by other programs (including other instances of the same program), or where some of memory is virtual, backed by slow (disk) storage. This is what makes browsers such bad citizens.

  2. Breaking cache locality by touching cache lines and pages not involved in the computation. Locality management is difficult enough already.

A dependence on GC would be an important determiner of whether a library would be usable in a program. I would not like to see library authors assuming GC was available.


#11

I agree that it would be a bummer for library authors to assume that GC is available.

On the other hand, I also think rust introduces some intriguing possibilities for more efficient and wholesome garbage collection. Specifically, the strong constraints it allows on references and lifetimes could be used to create a safe per-thread garbage collector. i.e. a given thread could have its own garbage collector (if in use) that only need track that thread’s data, and could probably even avoid scanning the stack with a bit of extra care (e.g. having each copy of a GC pointer register itself). Not that I care to work on this, but I do think that the possibility is there for something that is simultaneously easy to use, safe, and way more efficient on all parameters to GC in any other language.

One could even construct a per-data-structure garbage collector that could be used to write data structures that involve cycles (think graphs) without unsafe blocks, where the GC would only have to scan that single data structure, and one could put a smart control on how much data is allocated before cleaning up. And such a GC might be perfect for use in libraries!