Linux and GC
Scott L. Burson
Tue, 12 May 1998 15:41:28 -0700 (PDT)
From: P T Withington <firstname.lastname@example.org>
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
>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
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.