Path: utzoo!attcan!uunet!lll-winken!unixhub!shelby!neon!craig
From: craig@Neon.Stanford.EDU (Craig D. Chambers)
Newsgroups: comp.object
Subject: Re: Precise GC (was Re: Do we really need types in OOPL's?)
Message-ID: <1990Oct12.221032.20917@Neon.Stanford.EDU>
Date: 12 Oct 90 22:10:32 GMT
References: <1990Oct11.004854.11732@cbnewsc.att.com> <45571@apple.Apple.COM> <563@roo.UUCP>
Organization: Stanford University
Lines: 73

In article <563@roo.UUCP> boehm@parc.xerox.com (Hans Boehm) writes:
>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.)

The Self compiler does (5) (on the SPARC), using a compiler-generated
register mask word for each call site, identifying live registers.
All pointers are tagged, so the live registers mask includes all
registers that may contain a pointer.  And I have confidence in my
implementation, but I'd probably be hard pressed to convince you to
share my confidence!

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

The Self compiler is constrained to preserve the appearance of a naive
interpreter directly executing the source code, and to present a view
of the program at debug-time as if no optimizations had been
performed.  This implies that all user-visible variables (including
the "x" local variable above) may be viewed at debug time and so don't
die until the scope terminates.  This also implies that tail-recursion
elimination is practically impossible to perform without ruining the
user's view of the program (to get around this problem without
banishing loops Self includes a _Restart primitive which basically is
a tail-recursive call that the programmer explicit wants eliminated).
Under these constraints, the above program will run out of memory,
unless your debugger is smart enough to allocate a bunch of "x"
objects only when the debugger views the stack frames, and then you'll
only run out of memory at debug time.  Of course, if "x" were some
internal temporary expression that the user could not view at debug
time, the Self compiler would reclaim the storage (in fact, it would
optimize away the allocation entirely as a useless computation).

If this meets your definition of a "language definition that defines
accessibility of objects," then I'd have to disagree that this
overconstrains the compiler writer (i.e. me).  We're pretty happy with
our performance, which averages around 2x slower than optimized C,
depending on the benchmarks you use (1.5x slower for the Stanford
integer benchmarks), perhaps because we don't write programs that do
what you describe above.  We've found that this restictive debugging
model prevents very few optimizations. The only kinds of optimizations
forbidden that I can think of are the kinds where a variable that's
still in scope is treated as dead by the compiler (e.g. tail-recursion
elimination, dead assignment elimination, reusing registers of dead
variables).  The smarter the compiler and the debugger, the more
optimizations can be performed by the compiler and still dealt with by
the debugger.

-- Craig