Compile-time garbage collection (was Re: Compiler writers will love this language)

Lex Spoon wrote:
>
> ericmuttta@email.com (Eric) writes:
>
> > mwotton@cse.unsw.edu.au (Mark Alexander Wotton) wrote
> >> On 5 Jun 2003 23:22:01 -0400, Eric posted:
> >> >
> >> > I am having difficulty imagining a type which is implemented using
> >> > pointers and ensures that null cant occur. This would imply that for a
> >> > variable of such a type, memory would be allocated and then never
> >> > released.
> >>
> >> Either that, or only released when all references to it have passed
> >> out of scope. This is how many modern garbage-collected language
> >> implementations work.
> >
> > I admit, reference-counting has its problems and I have been toying
> > around with an idea for what I call "compile-time
> > reference-counting". Basically, I am looking for a set of rules,
> > that will allow the compiler to figure out when to release memory
> > for an object, *without* having to allocate memory space for a
> > reference counter value. Instead, using these rules, the compiler
> > can analyse code at compile time and statically work out the
> > life-time of an object. Its a bit wishy washy at the moment but if
> > its at all possible, I will write a paper on it :)
>
> Be sure to look up existing work. I'm certain that people have worked
> on this kind of thing.


I've been looking around for something similar, the most I've found is
this paper:


Ran Shaham, Eran Yahav, Elliot K. Kolodner, and Mooly Sagiv,
Establishing Local Temporal Heap Safety Properties with Applications to
Compile-Time Memory Management. To appear in the 10th Annual
International Static Analysis Symposium (SAS '03) San Diego, California,
USA, June 2003.


Available from the author's web page at
http://www.math.tau.ac.il/~ransh/ (direct:
http://www.math.tau.ac.il/~rans/sas03-safety-mm.pdf )


This paper has some references, but its


Of course, if you think about it a little, you might expect that each
conditional test (in the run-time code) will follow the format:


for each live possible referencor X of Y:
      if Y is referenced by X, Y is still alive, otherwise Y can be freed.


The problem lies in determination of the list of referencors.


For data structures that are globally accessible, you might be able to
calloect a list of possible referencors for a given object by just
annotating each function input/output with escape information.


For local variables, you can pass along information about which objects
that will be checked by the called functions are (or are not) referenced
further up, and you'll only get into real trouble with recursive
functions, where the size of this information is possibly unbounded (and
possibly difficult to determine before they are called).


Brute force would eventually produce a program that runs with very good
memory use, even if it was very very slow. Once you have it working you
can starting improving.


Everything starts to crumble as soon as you consider adding threads to
the model, though. How can you account for the state of other threads
in your tests? Every idea so far falls apart -- suddenly you have to
have this referencing information stored globally somewhere -- maybe
with the object? Maybe reduced to a simple counter for performance?
Sigh....


If I had time I would implement the non-threaded version and see how bad
the performance really is... if its less than 100 times as slow, it
would be a useful tool for measuring the real memory overhead of GC. I
think you could even adapt the algorithms to ignore variables which can
never be used again, which is as close to optimal memory usage as you
can get. (I suppose with optimal memory usage you would predict which
objects _will_ never be used again -- which requires foreknowledge of
the external inputs that affect the program's behavior).

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