From: Charles Mills <cmills@...>
Date: 2006-06-12T14:47:29+09:00
Subject: New GC for Ruby

Hi,

I have been researching GC options for Ruby.  I would like to throw  
out some ideas.  Also, I wanted to check to see if anyone else is  
working on a new GC for Ruby.

Write Barrier
It sounds like Ruby 2.0 will (hopefully) use a generational GC.  In  
order to do this some way needs to be devised to track when objects  
are updated.  There are basically three ways to do this:
1) Hardware write barrier
2) Software write barrier
3) Mixed write barrier

The first way involves write protecting all memory in the old  
generation(s) which could contain a reference (VALUE) to an object.   
This is what the Boehm collector does.  It requires creating/using  
special allocation functions for malloc'ing memory that must be  
tracked by the GC -- any memory that contains object references.

The second type involves adding a function/macro to the GC API which  
notifies the GC when the references an object holds are updated.   
This puts the burden on the application developer to notify the GC  
when an object changes.  The GC generally must be notified  
immediately after the object is updated and before the GC is given a  
change to run.  This is discussed further below.

The third is some combination of the first two.  One example is to  
use write protected memory for objects (struct RArray, struct  
RString, etc) and a software write barrier for malloc'ed memory  
(containing object references) used by objects (e.g., the VALUE array  
used by Array objects).

I vote for using the 2nd approach or the mixed approach described  
above.  The 2nd approach would require significant changes to the  
Ruby Core.  The mixed approach would require less code changes, but  
probably will be slower and make the GC less portable.

Either way a function like the following would have to be added to  
the Ruby API.
void rb_gc_obj_dirty(VALUE v);
This function would notify the GC that the referenced held by the  
object _v_ has been modified, so that it now references a new object  
or references fewer objects.  It should be called immediately after  
the object has been updated.  For example in Array#unshift the new  
API would be used as follows:
VALUE
rb_ary_unshift(ary, item)
     VALUE ary, item;
{
     rb_ary_modify(ary);
     /* ... */

     /* sliding items */
     MEMMOVE(RARRAY(ary)->ptr + 1, RARRAY(ary)->ptr, VALUE, RARRAY 
(ary)->len);

     RARRAY(ary)->len++;
     RARRAY(ary)->ptr[0] = item;
     rb_gc_obj_dirty(ary); /* <-- */

     return ary;
}

The object referenced by _item_ will be safe from the GC since there  
is no opportunity for the GC to run between when _item_ is stored in  
the Array and when rb_gc_obj_dirty() is called.  In situations where  
there is an opportunity for the GC to be run before rb_gc_obj_dirty()  
is called, a reference to the newly stored objects must be held on  
the stack.

In the 2nd approach rb_gc_obj_dirty() must be called whenever the  
references held by an object are updated, while the mixed approach  
requires rb_gc_obj_dirty() to be called only when references held in  
malloc'ed memory used by an object are updated.

Incremental Collection
Another issue, is GC pause times.  I know of two feasible ways to  
reduce pause times in the Ruby GC.  They are:
1) Use an incremental mostly-concurrent (a.k.a. mostly-parallel) GC.
2) Use an incremental collector on the old generation, probably a  
Train collector.
3) ???

Both of these collectors are not trivial to implement.

It is only feasible to implement (1) in conjunction with a GC that  
use a hardware write barrier, unless extreme care is taken.   
Basically mostly-concurrent collectors suspend the process, mark the  
roots, resume the process, concurrently trace the heap, suspend the  
process and trace any objects modified by the process during the last  
step, and finally sweep.

(2) requires at-least a mostly-copying collector.  Adding Ruby  
support for a mostly-copying collector would require making all  
object references (VALUE) be indirect and actually point to a  
reference in a reference table.  This would allow all objects to be  
moved by updating the reference table and not updating heap  
references.  Any object referenced on the stack would be pinned (and  
logically moved to the youngest train -- by 'moving' the entire car/ 
page to the youngest train), since the stack may contain internal  
references to these objects.  Using indirect references would require  
changes to all the cast macros (RARRAY, RSTRING, etc) and to all the  
object allocation functions (ary_alloc, str_alloc, etc) at a minimum.

As mentioned train collectors can decrease pause times by having a  
small young generation and incrementally collecting the old  
generation.  Train collectors can remove large cycles of garbage  
efficiently by detecting if an entire train or car is unreachable.

I vote for (2) -- somewhat tentatively given the difficulty of  
implementing a train collector, but the payoff could be huge. :)

One thing I didn't mention is that a mostly-copying collector is  
possible without using indirect references, but it requires knowing  
about all memory containing references and having type information  
for all this memory.  This has been done for C++, see the MCC  
project.  Creating something like this for Ruby would require massive  
changes to the GC API and put a large burden on extension developers.

Backwards Compatibility
It should be possible to build a GC that tracks T_DATA types which  
use the existing GC API separately, if backwards compatibility is a  
big issue.  In most cases the references held by these objects would  
be treated like root (or stack) references and all T_DATA objects  
would be scanned at each invocation of the GC.

Comments, corrections?

Charlie