Re: Compile Time Garbage Collection impossible?

On 22 Sep 2006 22:29:03 -0400, the.real.doctor.zoidberg@gmail.com wrote:
> Why isn't Compile-Time-Garbage-Collection feasible? Consider a Java
> compiler which produces assembly code for a specific target instead of
> Java's bytecode cenario. The objective is to use Java without the need
> for a GC or VM.
>
> I'm asking why it isn't possible because otherwise there would be at
> least one compiler to use that technique, instead of having to run a
> GC in the VM.


You can run a GC without a VM. Boehm's collector doesn't require a VM,
and it's used by GCJ, an ahead-of-time Java compiler producing native
code.


> what would be the
> problem in "freeing" objects after their scope, or even better, after
> the last reference in their scope?


Freeing an object after its "scope" doesn't make sense. The "scope"
is actually the scope of the variable referring to the object, and
there are most likely other references to it. Freeing it after the
last reference to it is GC - it is a reference counting garbage
collector.


There are many cases where allocated objects outlive the scope of the
variable referring to them. This is called "escaping" in the
literature. There are numerous good papers on escape analysis, esp. in
Java,:
    http://www.research.ibm.com/people/g/gupta/escape.ps
    http://www.stanford.edu/~jwhaley/papers/oopsla99.pdf


An object escapes in many circumstances:
  - When a global object (static class variable) may refer to it
  - When multiple threads may refer to it.
  - When it may be returned by a function
    - When it is passed to a function which we cannot analyse (in Java
this particularly occurs in code using JNI)
  - When it may be referred to be an exception


Note that I say "may refer to it". Obviously, there are paths where an
object doesn't escape. A paper by Sam Guyer in this year's PLDI added
memory deallocations on such paths, and leaves other objects to be
cleared up by the garbage collector.
http://www.cs.tufts.edu/~sguyer/free-pldi-2006.pdf


Although these examples show that you can remove up to 80% of garbage
collection overhead in some cases, it will still be required, except
in toy examples.


> [Local objects are usually stack allocated and freed at end of scope.


But not in Java, nor a whole rake of other languages, particularly
interpreted ones, in which the distinction between a local object and
a non-local object is not clear, and requires escape analysis.


Paul


--
Paul Biggar
paul.biggar@gmail.com

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