Re: Future GC, the free list, and POSIX threads

[Jim Blandy <jimb@red-bean.com>]

> Would this make it possible for one thread to GC at least its own cells
> independently from the other threads? If this is possible, it is a big help
> for writing GUI applications; one can often seperate out the GUI parts, which
> hopefully don't make too much garbage, from the calculation bits. If
> the calculator thread has to halt for GC from time to time then it is
> not such a big deal as a pause when typing or in an animation. In my
> ideal fantasy world, each thread could have its own GC tuning,
> the GUI doing frequent, (hopefully) small GCs, while the back-end is
> set for efficiency with few big collections. Is it possible to imagine
> rather than a generational collector, a tree-like one, which collects
> the young generations of each thread independently? Obviously, if you
> have a thread that plays with variables in the root thread, it makes
> root thread garbage and that has to be collected eventually. But it
> makes a lot sense if thread local garbage can be collected without 
> locking the other threads. I hope this is not deeply stupid.

The problem is that liveness is a global property.  Any pointer
anywhere could conceivably be keeping a given object alive.  If you
want to collect a subset of the heap, you need to somehow magically
know which objects in that set are pointed to by something outside;
they are live.  Since the whole damn heap is full of pointers,
tracking them can be hairy.

The insight behind generational GC is that there are indeed some
subsets of the heap where it's feasible to keep track of all pointers
from outside into the set.  First, note that, when you create an
object (a pair, say), it's the newest object around, so all its fields
must point to older objects.  Then, note that side effects are rare in
Scheme.  Thus, most objects point to older objects.

So, pick any object, and consider the set of all objects younger than
it.  There will be very few pointers into this set.  Any such pointers
will be created by assignments, so we can check each assignment to an
object field (assignments are rare, remember), and make a note if it
creates an old->young pointer.  Then we have all the information we
need to do a partial GC of this set.

If you could identify other subsets of the heap which have few
pointers into them, and where it's easy to detect and record such
pointers, then you could do other kinds of partial collection.