Componentizing D's garbage collector

[Andrei Alexandrescu]

The GC comes up repeatedly in discussions around here. I've been 
thinking for a while about breaking it down into components, and now it 
seems the time is ripe.

The design at http://goo.gl/ZVCJeB seems to be a win. It works well, 
comprehends all major allocation tropes, someone implemented a subset of 
it in C++ and measured good results, and a coworker is considering 
adopting the design for a C++ project as well.

I've started with the next logical step - higher-level allocation that 
is aware of the type of the object being allocated, and realized that 
integrating a notion of tracing is appropriate at that level, and 
actually quite easy. So I'm thinking of just doing it.

A few highlights:

* The design will foster the small, composable components with 
required/optional primitives that worked for std.allocator.

* I plan to review and probably discard all of the pointers-to-functions 
nonsense in the current GC.

* At this point I won't worry about discovering roots; I assume druntime 
has the appropriate mechanisms in place. Instead I'll focus on 
primitives such as "given this root, mark all that transitively follows 
from it" (conservatively or not).

* I plan to rely on static introspection for the mark function, i.e:

void mark(T)(ref T obj);

would mark obj and everything transitively referred to by it. The 
function would probably take a second parameter that's the heap that obj 
is sitting in.

* I plan to segregate all objects that don't include references and 
pointers (e.g. int, int[], Tuple!(int, double) etc) into a completely 
different heap than the "interesting" objects. For the simpler objects 
there's no need to save detailed type information so they can be stored 
in a more compact, efficient manner.

* There will be no possibility to change the type of certain objects 
once allocated. An allocation for an immutable object cannot e.g. make 
it later a mutable one. (This is an essential issue with the current 
allocator, I think.)

* At this point I'm unclear on how generations can be componentized, but 
am cautiously optimistic. Will see once I get to it.

One thing that would be great now would be to make an effort to review 
and merge the current precise GC work. I'm sure it will be of great help 
with breaking into components.


Destroy.

Andrei