Re: Compile Time Garbage Collection impossible?

the.real.doctor.zoidberg@gmail.com writes:


> Why isn't Compile-Time-Garbage-Collection feasible?


The short answer is that while CTGC is possible, it can not collect
all the data that a run-time GC (RTGC) can (or, at least not as
early).


All automatic memory management rely on predicting when a value will
no longer be accessed. Even at run-time, such predictions are
imprecise -- exact prediction is equivalnet to solving the halting
problem. So you need a conservative approximation, conservative
meaning that if the prediction says a value won't ever be used, it had
better be right about it, whereas it is allowed to say that an object
may be used when in fact it will not.


Most RTGC methods use a simple prediction: If there is a path of
pointers from the current continuation (usually represented by the
call stack) to a value, it may be used, otherwise it won't. While
this isn't perfect, it is good enough for most purposes, and a good
programmer can help by zeroing out pointers that he knows will never
be followed.


At compile-time, you don't have access to the continuation, so you
need to approximate this, again conservatively. Hence, CTGC is by
nature less precise than RTGC. The question is if it can be precise
enough.


The work by Tofte et al. on region analysis (that Peter Lund and
others mentioned) indicates that it can -- at least for ML-like
languages -- but that the programmer may have to program with regions
in mind, sometimes doing things somewhat differently than he would
with RTGC. Region analysis does not work by approximating when a
value is reachable through a path of pointers, it is an approximation
of which pointers the continuation will actually follow. Hence, it
may in some cases collect values that RTGC will not. Furthermore,
implementations based on regions use fast (stack-like) deallocation,
making programs run faster than with RTGC.


You can also use CTGC in combination with RTGC (the ML kit with
regions allows this as an option). Besides region analysis, there are
other analyses that can be used to reduce the number of values that
must be collected by RTGC:


  - Escape analysis can predict if a pointer to a value can be returned
      from the function in which it is allocated. If not, the value can
      be allocated on the stack instead of in the heap.


  - Linear types or other linearity analyses can see when a value will
      be used exactly once, allowing it to de deallocated (or reused)
      immediately after it is used. You can call this a one-bit
      compile-time reference count. Some linearity analyses can predict
      the last of several uses.


Discounting CTGC methods like region analysis because they sometimes
need programmers to do things a bit differently to get optimal
behaviour is a bit like objecting to stack alloaction because you will
never deallocate if your program never returns from a sequence of
calls, so you have to rewrite it to do so. Most people don't complain
about the latter because they have been brought up with a program
style basd on stack allocation, but with proper "upbringing"
programmers may come to think of region-aware programming (or
something based on another RTGC method) as a natural style.


Torben

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