Linux and GC

Scott L. Burson
Tue, 12 May 1998 14:04:11 -0700 (PDT)

   Date: Tue, 12 May 1998 15:21:53 -0400
   From: P T Withington <>
   On 4/28/98 18:17, Kragen wrote:

   Most snapshot-at-beginning implementations do not actually make a 
   snapshot of the whole image, but rather arrange a write barrier, so that 
   any changes to the image can be recorded and dealt with (e.g., by 
   recording every value that gets overwritten).
Well, if we're willing to call *that* a write barrier, then Al is right,
because that's exactly what has been proposed.
   What looks difficult in your idea is that the list of dead objects to be 
   communicated back to the mutator might be large.  In a collector that is 
   a co-routine, it is simple for the collector to pop those objects onto a 
   free list.  Where your collector is in a separate address space, some 
   form of IPC is needed to communicate them back to the mutator.

I had the same concern, but it's not a problem -- the two processes can just
map a big chunk of shared memory.

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.

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.

My concern about any freelist-based collector is that it does a component of
work that's proportional to the number of dead objects.  I generally prefer
copying schemes, in part because their cost is related only to the number of
live objects, which encourages a programmer not to worry about generating lots
of short-lived garbage; without that concern, one tends to write more elegant
code in many cases.  (There's also the locality issue, of course.)

Still, it's an intriguing idea.

-- Scott