Linux and GC

P T Withington
Tue, 12 May 1998 18:12:21 -0400

On 5/12/98 17:04, Scott L. Burson wrote:

>   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 
>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.

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 

>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.

>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 
>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.)

Agreed.  But there are places for freelist collectors...
>Still, it's an intriguing idea.
>-- Scott