Path: utzoo!attcan!uunet!wuarchive!zaphod.mps.ohio-state.edu!uwm.edu!bionet!arisia!roo!boehm
From: boehm@parc.xerox.com (Hans Boehm)
Newsgroups: comp.object
Subject: Precise GC (was Re: Do we really need types in OOPL's?)
Message-ID: <563@roo.UUCP>
Date: 12 Oct 90 19:24:31 GMT
References: <736@tetrauk.UUCP> <18261.27131385@qut.edu.au> <1990Oct11.004854.11732@cbnewsc.att.com> <45571@apple.Apple.COM>
Sender: news@parc.xerox.com
Lines: 63

>In article <1990Oct11.004854.11732@cbnewsc.att.com> lgm@cbnewsc.att.com (lawrence.g.mayka) writes:
>>b) Languages that essentially preclude precise (i.e., not
>>"conservative") garbage collection (Modula-3).
>Ah, seems to preclude C++ too.

"Precise" garbage collection is a rather imprecise concept and thus,
I would argue, a funny absolute criterion to use in language selection.
I know of many gradations of "conservativism" in garbage collection.
Here are some:

1) No structural information about heap objects, interior pointers valid.

2) No structural information in heap objects, no interior pointers.

3) Structural information on heap objects, conservative on stack and registers.
   (Recent collectors on Xerox D machines did this, as does Bartlett's
   collector and AKCL.)

4) Pointer location information maintained on stack and registers (i.e. tagged
   pointers or a compiler generated map of where pointers are at various
   programs points).  I believe Standard ML of NJ, and the original KCL
   fit here.

5) Same as (4), but also clears registers (or updates map) when their pointer
   values become known dead.  Some Lisps may do this.  (I wouldn't have much
   confidence in an implementation that claimed to do this, since its hard
   to test well.)

It is not always clear what kind of conservativism will hurt you.  For example,
it is my impression that on a SPARC (with its sparsely occupied stacks),
the step from (4) to (3) is likely to cause more spurious retention than going
from (3) to (2).  In most cases, even (1) will work fine.  But on a machine
with 16 bit pointer alignment (as in David Chase's bad experience with
hyperconservative collection) there is a good possibility that it won't.

Even (5) is not in any sense precise.  It depends both on the compilers dead
variable analysis, and on other choices made by the compiler writer.
For example, will the following program run out of heap space:

let
    f = function(n:integer)
           let
		x = new 100000 byte object
	   in
		/* drop x */; if n > 0 then f(n-1)

in
    f (10000);

If my compiler does tail recursion elimination, or does good dead variable
analysis, I'm in luck.  If it waits until x goes out of scope to clear its
register, and does not do tail recursion elimination, the garbage collector
won't be able to reclaim anything.  There is another illustration in Weiser's
and my SP&E paper.

To really define "precise" collection, you need a language definition that
defines accessibility of objects.  I know of no such language definition.
Even if you came up with one, I strongly suspect that it would overconstrain
the compiler writer to the point that you won't be happy with the performance.

Garbage collectors are never perfect.  But in my experience programmers
manually managing storage are much less perfect still.  And programmers
may also err in more disastrous ways.