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

boehm@parc.xerox.com (Hans Boehm) writes:
>1. Consider a language that allows general function closures.
>
>2. Consider a compiler that understands bignum arithmetic and understands
>that factorial is a pure function. Suppose I write
>
>x := log(fact(100000)); g(...); y := fact(100000); ...
>
>The compiler might eliminate the second call to fact as a common
>subexpression. But now fact(100000) is reachable during the call to g,
>and the garbage collector's notion of pointer reachability no longer
>reflects what the the programmer is likely to have had in mind.


Hans brings up some very good points and examples re defining 'live
roots'. Reachability from a 'live' root is actually a much more
interesting question than reachability from a more static definition of
'root', but one that is undecidable. However, compiler people have
worried about liveness for some time now, so they may as well worry about
it in the context of GC. The problem is that the compiler (usually) has
no idea about how large a structure might be held onto by a live root, so
it doesn't know how hard it should work to cut down on this sort of thing.


In the work I'm doing on 'linear logic/linear types', I can guarantee the
inductive assumption that there is always only _one_ path to any linear
object. This is one of the reasons why I'm quite concerned about losing
that 'last' path!! The function closure space optimizations 'fall out'
(as it were) automatically when function closures are linear objects
because any use of an element in the closure is by definition its last use.
--

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