Re: Compile Time Garbage Collection impossible?

russell kym horsell <kym@ukato.freeshell.org>
25 Sep 2006 01:13:41 -0400

          From comp.compilers

Related articles
Compile Time Garbage Collection impossible? the.real.doctor.zoidberg@gmail.com (2006-09-22)
Re: Compile Time Garbage Collection impossible? pjb@informatimago.com (Pascal Bourguignon) (2006-09-25)
Re: Compile Time Garbage Collection impossible? dido@imperium.ph (Rafael 'Dido' Sevilla) (2006-09-25)
Re: Compile Time Garbage Collection impossible? kym@ukato.freeshell.org (russell kym horsell) (2006-09-25)
Re: Compile Time Garbage Collection impossible? paul.biggar@gmail.com (Paul Biggar) (2006-09-25)
Re: Compile Time Garbage Collection impossible? firefly@diku.dk (Peter \Firefly\Lund) (2006-09-25)
Re: Compile Time Garbage Collection impossible? gneuner2@comcast.net (George Neuner) (2006-09-25)
Re: Compile Time Garbage Collection impossible? liekweg@ipd.info.uni-karlsruhe.de (Florian Liekweg) (2006-09-25)
Re: Compile Time Garbage Collection impossible? gah@ugcs.caltech.edu (glen herrmannsfeldt) (2006-09-25)
Re: Compile Time Garbage Collection impossible? torbenm@app-0.diku.dk (2006-09-25)
[10 later articles]
| List of all articles for this month |

From: russell kym horsell <kym@ukato.freeshell.org>
Newsgroups: comp.compilers
Date: 25 Sep 2006 01:13:41 -0400
Organization: Central Iowa (Model) Railroad, Plano, TX, USA
References: 06-09-119
Keywords: GC
Posted-Date: 25 Sep 2006 01:13:41 EDT

the.real.doctor.zoidberg@gmail.com wrote:
> Why isn't Compile-Time-Garbage-Collection feasible?
[...]


Obviously, it is. But equally obviously, it isn't complete. :)


It's quite possible for a compiler to maintain a reference count for
heap-allocated objects. When *the compiler can tell* the count reaches
zero (say at the end of blocks) it's possible to plant a "free()".


But down to things like the halting problem, it's impossible to have
this cover all cases. At some point any automatic system (even your
head :) will not be able to decide -- is this garbage now, or not?


On such occasions it's traditional to put the reference count INTO the
object, and use a decr and test. And this, too, could be planted by a
compiler.


But we again come to problems of decidability -- it would not be
possible to have such automatically-planted decr-and-test maintain the
smallest heap possible or remove garbage as soon as possible, etc.


I know Prolog (based on an abstract machine) goes to what I'd call
extra-ordinary lengths to maintain a small amount of memory usage.
Most of this is via objects allocated on a stack.


But the system also tries to decide whether objects *should* be
allocated on a stack or heap, or whether it can speculatively allocate
on a stack and later -- if it needs to -- plant a test that may copy
it to the heap (when it determines at least 1 more ref to the object
has been screated in the meantime).


The strategy usually also needs the help of a periodic
garbage-collection on heap objects.



Post a followup to this message

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