[gclist] conservative vs. "precise" gc

Tyson Richard DOWD trd@mundil.cs.mu.OZ.AU
Mon, 26 Feb 1996 11:04:38 +1100 (EDT)


> 
> It may be worth emphasizing again that there are different possible
> degrees of conservativism with different tradeoffs.  The major possibilities
> are something like:
> 
> 1. Only scan the top activation record conservatively.  Generate stack layout
> descriptors for call sites.  This makes lots of sense to me even if you
> complete control over the compiler.  The main benefit
> is that it allow you to run with a conventional thread system
> (or UNIX signals) without adding
> safe points.  It can also easily be extended to give you better C
> intercallability.  There is some minimal risk of accidental retention.  But
> there are very few systems that don't already include much larger risks
> of this form.

This form of conservatism is quite attractive, but I'm not convinced it
buys you much by itself. Certainly, you don't have to conservatively
scan the rest of the root set. However, you won't know the types of
anything in the top activation record, so it could be that you to have
to scan the heap quite conservatively (if you find a pointer into the
heap in the top activation record). It's possible that the next 200
words on the heap could all be part of that object, or even the next
200000 words.

In a GC scheme with its own allocator, you would know this information, so
that's fine. 

If you don't know this information, I suppose you could mark the rest
of the root set (using stack layout descriptors), and then pointers you
find conservatively are either already marked (so you can ignore them),
or are bounded by {heap bottom, live data} -- {heap top, live data},
which should greatly reduce the amount of scanning to be done. It's
probably likely (no evidence) that the top activation record has
pointers to near the top of the heap, and near other live data, making
it resonably cheap normally.

Does this sound plausible? Am I missing something?

(I'm implementing the GC for Mercury, and we will eventually have a threaded
system, and presently C intercallability causes some headaches... this sounds
like a good scheme to add to the collector once the simple version is 
complete, so long as it doesn't end up making it mostly conservative.
We already use a perfectly good conservative collector ;-).

-- 
       Tyson Dowd           #          Another great idea from the 
			    #		 people who brought you
  trd@mundil.cs.mu.oz.au    #               Beer Milkshakes!
http://www.cs.mu.oz.au/~trd #	         Confidence --- Red Dwarf