This is the mail archive of the guile@sourceware.cygnus.com mailing list for the Guile project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Re: GC and threads (was Re: generational GC)


Jim Blandy <jimb@red-bean.com> writes:
> In this terminology, your strategy would be described as "allocate
> black."  That is, new nodes are assumed to be live, and are left alone
> until the next GC cycle begins, at which point everything is colored
> white.
> 
> The problem with allocating black is that the new cells can't be
> collected until the end of the *next* GC cycle, even though they're
> the most likely to die quickly.  So it's more efficient to use some
> kind of heuristic to color them grey or white.
> 
> For example, suppose we mark the global roots first, and leave
> scanning the threads' stacks at the very end.  When a thread allocates
> a new cell, we can color the new cell white if the thread's stack
> hasn't been scanned yet, or black if it has.  That way, if we can
> reach a good portion of the heap through the global roots, we can do
> most of our allocation white, and those cells can be reclaimed at the
> end of this GC cycle.

I don't think that's quite enough.  Consider:

   one thread calls a C routine
   c_routine creates objects o1 and o2, keeps references locally
   GC starts, scanning global roots
   GC scans binding of Scheme variable x containing a hash table
   c_routine creates o3, a pair containing o1 and #t
   c_routine sets cdr of o3 to o2
   c_routine stores o3 in hash table x
   c_routine discards references to o1, o2, o3
   GC finishes with global roots, starts scanning thread stacks

So, the scanner misses all three objects, even those created before
the GC pass started.

I think that async GC needs a hook into the write-barrier code -- if
you're storing a reference to a white object into a black object,
whether by creating or modifying, the white object becomes grey.
Perhaps there's a refinement possible using generation numbers;
there's probably published literature on it.

If you consider the thread to be black once its stack has been
scanned, the "allocate black if stack's been scanned" approach sort of
falls out of this automatically, at least conceptually.  (Allocate
everything white, and if the stack/thread is black, color the object
grey, and hey, while we're here, let's run the mark pass on this grey
object since it'll be quick.)

Ken

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]