Re: 'conservative' GC == 'risky' GC

hbaker@netcom.com (Henry G. Baker)
Tue, 31 May 1994 00:12:09 GMT

          From comp.compilers

Related articles
[3 earlier articles]
Re: 'conservative' GC == 'risky' GC pardo@cs.washington.edu (1994-05-24)
Re: 'conservative' GC == 'risky' GC tmb@arolla.idiap.ch (1994-05-25)
Re: 'conservative' GC == 'risky' GC markt@harlequin.co.uk (1994-05-26)
Re: 'conservative' GC == 'risky' GC jgmorris+@cs.cmu.edu (1994-05-27)
Re: 'conservative' GC == 'risky' GC boehm@parc.xerox.com (1994-05-27)
Re: 'conservative' GC == 'risky' GC chase@Think.COM (1994-05-26)
Re: 'conservative' GC == 'risky' GC hbaker@netcom.com (1994-05-31)
Re: 'conservative' GC == 'risky' GC hbaker@netcom.com (1994-05-30)
Re: 'conservative' GC == 'risky' GC boehm@parc.xerox.com (1994-05-31)
Re: 'conservative' GC == 'risky' GC ok@cs.rmit.oz.au (1994-06-07)
Re: 'conservative' GC == 'risky' GC boehm@parc.xerox.com (1994-06-13)
| List of all articles for this month |

Newsgroups: comp.compilers
From: hbaker@netcom.com (Henry G. Baker)
Keywords: GC
Organization: Compilers Central
References: 94-05-084 94-05-124
Date: Tue, 31 May 1994 00:12:09 GMT

chase@Think.COM (David Chase) writes:
>4. There are a number of other ways that things can "go wrong" besides the
>hidden pointers.
[snip]
>Dead code problem number two comes with things like reference counting
>collectors and conservative collectors.


There is a heuristic that I use to keep myself from 'going wrong', and
perhaps someone can make this heuristic into a solid theory. The
heuristic is that one (and this includes compilers) should think about the
GC as a parallel process and/or coroutine, and both the application
program and the GC have certain requirements for cooperation. In most
GC's, the GC can 'be scheduled to run' only _during_ an allocation
(cons/malloc/new) operation, so it is imperative that the programmer and
compiler know when these operations can occur. Interestingly enough, most
sophisticated Lisp compilers have a 'typing' system that types certain
primitives (and the user functions that incorporate these primitives) as
having an 'allocation' property. (No, Gifford was not the first to do
this by a long shot.) In fact, my CACM78 RT GC can be seen as just such a
'parallel' GC in which all of the scheduling decisions have been
precompiled and optimized.


Of course, once the compiler is aware of the GC process, then it can start
to do the right things. (Notice that the user's 'debugging' is a similar
sort of parallel process, whose 'running' is 'scheduled' by the user
himself. The potential locations of such debugger scheduling can shed
light on the 'debugging of highly optimized programs' question.)


I tried to point the ML people in this 'typing' direction with my LFP90
paper, but no one seems to have picked up on this yet.


A nearly identical heuristic is good for guaranteeing recovery from a
crashed database. Just think of the _recovery program_ as a parallel
process which has really bizarre scheduling, and you should be able to see
what I am talking about. Once you see this, you may also be able to see
database recovery as 'rerooting' in a naming tree of contexts.


>I'm beginning to think that perhaps I should publish a little more on this
>front. Sigh.


Yes!!
--


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.