Linux and GC

[Scott L. Burson]

   From: P T Withington <ptw@pobox.com>
   Date: Tue, 12 May 1998 18:12:21 -0400

   On 5/12/98 17:04, Scott L. Burson wrote:
   >This scheme doesn't really make seem to make sense in the context of a 
   >copying
   >collector; since the mutator process still has to do all the copying, and has
   >to pause to do it, all the collector process has done is saved it some
   >scanning work.  Doesn't seem worth the trouble.

   Or use a read barrier:  an incremental copying collector uses a read 
   barrier to coordinate with the mutator by intercepting attempts by the 
   mutator to read references that may be changed by the GC.

If we accept the cost of a read barrier, then we hardly need to go to all this
trouble to avoid the (smaller) cost of a write barrier!

   You can use such a read barrier in a write-barrier GC to do compacting.  
   A read barrier can be simulated in software by an object table (i.e., 
   every object reference is double indirect).  This is how MacOS memory 
   works.

I'm familiar with that approach -- in fact I have half-built a fairly complex
multi-space collector integrated into a persistent object store, where the
basis of the design is the use of handle tables and the Brooks GC algorithm.

But the point stands -- if one has accepted the overhead of that indirection,
then the additional cost of a software write barrier might as well be paid
also.  This is how my collector works, and revamping it to use the
copy-on-write trick sounds like a lot of work for relatively little gain.

   >In a non-copying scheme, if the collector had a way to write the mutator's
   >memory, it could just go ahead and construct the freelist.  This sounds to me
   >like the best way to make use of this idea.

   It would still have to synchronize with the mutator, since the freelist 
   is a shared data structure.  This is what I meant by IPC.

Okay, but it's easy to make that cheap.  The mutator can use its own freelist
until the first time it fails to satisfy an allocation request; at that point
it synchronizes with the collector, transfers the collector's freelist
contents to its own freelist, and releases the lock.  This will happen rarely
enough that synchronization overhead won't be a problem.

-- Scott