generational GC

[Michael Livshin <mlivshin at bigfoot dot com>]

[
  I thought this will be a long article, so it's written to be read in 
  outline mode.  sorry ;).
]

* introduction

** it was already discussed a number of times.  can't you shut up?

I believe that now is a very good time to discuss generational GC.
the main reason is that an overhaul of Guile API's is planned, and
that is an opportunity to introduce GenGC-safe interfaces.

also, the previous discussions were not all for naught.  several
people (most notably Greg Harvey) did a lot of thinking and
implementation work, and in particular many parts of Greg's work can
be used.  I'll get to details later.

** what is so hard about generational GC anyway?

technically, not a lot.  the hard part is the API management.

* things that don't really need any discussion

** cell representation

Greg Harvey has implemented a nice heap representation concept called
"chunklets".  a big benefit of chunklets, orthogonal to the
generational nature of the GC or lack thereof, is that the mark bits
are moved out of the cells and into chunklet headers.  this should
provide a slight marking speedup as well as reduced complexity of
dealing with cells (no need to mask out mark bits).

** explicit mark stack

this, again, is orthogonal to the generational nature of the GC.

* so what are the issues, anyway?

** write barrier

as Greg points out in his notes, relying on OS support for
write-barrier implementation is unwise.  he's, IMHO, absolutely
right.  the reasons are:

1.  page protection faults can be very expensive.
2.  the granularity is kind of unimpressive.
3.  some people apparently use Guile on embedded platforms, where
    there is no memory protection hardware at all.

so the write barrier has to be explicit and reflected in the API.
writing `SCM_VELTS(v, 0) = x;' will be not kosher at all anymore, and
that's a problem.

** but the debugging will be a nightmare!

not necessarily.  there can be a debugging mode in the collector, in
which it will:

1.  at the end of sweep, squirrel away the contents of all its memory
    somewhere, chunklet by chunklet.
2.  before the next marking, check that the contents of the supposedly
    untouched chunklets didn't change.  complain laudly about any
    unlawfully changed objects.

** but I've got all this code here, and I ain't going to rewrite it.

this can be taken care of by introducing the concept of "evergreen"
cells, i.e. cells (actually, chunklets) that just won't age.  by
defining a preprocessor flag, you'll make SCM_NEWCELL and friends
allocate only such cells.

* the immediate plans

I'll fold in the chunklets and the explicit mark stack in the near
future, unless there are complaints.

the rest (real generational collection) will require lots of changes
in Guile, and will come later.

just keep in mind that generational GC is not a blue-sky item anymore, 
so react.

-- 
Purely applicative languages are poorly applicable.
                -- Alan Perlis