Re: an idea to speed up GC

[Richard Henderson <rth at cygnus dot com>]

On Sat, Mar 11, 2000 at 12:00:07PM -0800, Zack Weinberg wrote:
> Suppose we add a second set of mark bits, call it the frozen set.  You
> can ask the garbage collector to mark some structure, or all of the
> roots, and then copy the mark bits to the frozen bits.  Then, instead
> of clearing all the mark bits at the start of a GC run, we copy the
> frozen bits to the mark bits.

As presented this scheme won't work due to reachability issues.

One way to do this sort of thing is called "generational garbage
collection".  It involves having each page in one of three states
or "colours" -- black (maybe collectible), grey (not collectible
but modified), or white (not collectible and clean).  At collection
time, a white page needs no processing at all.

After collection is complete, all remaining pages are reachable.
We mark all pages read-only and set their colour to white.  When
an object is modified, we mark the page read-write, change the
page's colour to grey.  We also iterate through all objects on
that page and mark all pages reachable from there as black.

There are two critical points to this scheme.  First, one must be
able to mark pages read-only (eg. mprotect) and then be able to
handle a fault to such a page and restart (segv handler that provides
the address of the write).  Second, one must know the type of each
object stored on a page -- at least far enough to call the appropriate
mark routine.

The first point requires a lot of system-specific hackery.  Look
at some of the code in bohem-gc and try not to vomit.  We're not
currently set up to handle the second point.  It would require 
modifying ggc_alloc_obj to provide extra information.

Also note that all pages that have GC roots must also be able to
be marked read-only.  This would not be feasable for us without
rearranging things.



r~