Path: utzoo!attcan!uunet!wuarchive!sdd.hp.com!ucsd!dog.ee.lbl.gov!pasteur!agate!bionet!arisia!roo!boehm
From: boehm@parc.xerox.com (Hans Boehm)
Newsgroups: comp.object
Subject: Re: Precise GC (was Re: Do we really need types in OOPL's?)
Message-ID: <570@roo.UUCP>
Date: 16 Oct 90 21:35:47 GMT
References: <1990Oct11.004854.11732@cbnewsc.att.com> <45571@apple.Apple.COM> <563@roo.UUCP> <1990Oct12.221032.20917@Neon.Stanford.EDU>
Sender: news@parc.xerox.com
Lines: 75

In article <1990Oct12.221032.20917@Neon.Stanford.EDU> craig@Neon.Stanford.EDU (Craig D. Chambers) writes:

[Me:]
>>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.

[Craig:]
>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).

This comes closer to defining object accessibility than anything else
I've seen.  However I don't think it's quite sufficient, since I can
construct similar examples using debugger-inaccessible temporaries.
For example, consider the following code, where X is known to be a large
bignum.  (Similar examples can be constructed with lists, but they're a
bit less intuitive.)  I assume that bignum arithmetic dynamically allocates
space in the heap to hold results.

let
   y = X
in
   i := 0;
   while i < 10000 do
     i++;
     z := y * y + g(i);
     f(z);
   endwhile

I would certainly like my compiler to move "y * y" (or any such expression)
out of the loop.  But that isn't allowed, since doing so would preserve
the temporary across the procedure call.  If f ends up invoking the garbage
collector, I will fail to reclaim the storage used to hold y*y.  Thus some
conservativism would have crept back into my collector.

>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

Your factor of 2 presumably buys me all sorts of things, so I'm not quite
sure what to make of it.  For most applications, I would be very unhappy
if I had to pay a factor of 2 solely for "precise" collection. It would
be nice to know how those costs broke down.  I suspect that not being able
to reuse registers hurts a lot more on a '386 than a SPARC.

Hans