Re: Garbage collector necessary (for Ada access types)?

Re: Garbage collector necessary (for Ada access types)?

[cis.ohio-state.edu!news.sei.cmu.edu!bb3.andrew.cmu.edu!crabapple.srv.cs.c]

In article <aecolley.736460217@unix1.tcd.ie> aecolley@unix1.tcd.ie (Adrian Coll
ey) writes:
>I want to write an Ada-to-ANSI-C transpiler.   Most of this seems
>possible, if not straightforward (even tasks).  My problem is how
>to handle deallocation of memory objects.
>
>Reference counting is out: a ring of records each containing pointers
>to one another would each have positive refcounts, even when
>inaccessible.  Deallocating objects when the access type definition
>goes out of scope is another non-starter - most access types are
>declared with permanent lifetime (in package specifications as
>private types) so deallocation will never happen.
>
>Garbage collection seems to be an obvious way to solve it, but for
>the usual reasons (elegance, efficiency etc.) I want to avoid this
>if at all possible.

Ouch !
Just try to decide all this at compile-time, and look at your code.
I'm sure your notion of elegance will change :-)

(I won't insist on the efficiency argument. Just to say that GC
doesn't seem to require much more time than explicit deallocation)

>Is there any proven method of analysing a program to tell the "right
>time" to deallocate a value ?  Is this an instance of the halting
>problem or other impossible problem ?

What you want is called "compile-time GC". It is in general impossible
to do. What is meant by 'compile-time GC' in reality is to analyse the
code so as to determine what (and when) can be explicitely
deallocated. The rest will be handled by a run-time GC.

If you really don't want a real GC, I guess reference counting will
buy you more (for less work) than compile-time GC.

>Replies to me.  References to famous/obscure papers or reports welcome.
>A summary will follow if there's anything worth summarising.
>
>--Adrian.

If you don't want to spend too much time in your compiler just for the
GC problem (emitting code so that the GC knows what is a pointer andwhat
is not), you can use a conservative GC (you can even use 'ready-to-go'
ones for C: it replaces the malloc and the mfree becomes useless). But
beware its limitations: such GC is generally slower and doesn't guarantee
you won't have "memory leaks".


	Stefan

Re: Garbage collector necessary (for Ada access types)?

[Paul Johnson]

In article <C6L3wx.6wD.1@cs.cmu.edu> monnier+@cs.cmu.edu (Stefan Monnier) write
s:

>If you don't want to spend too much time in your compiler just for the
>GC problem (emitting code so that the GC knows what is a pointer andwhat
>is not), you can use a conservative GC (you can even use 'ready-to-go'
>ones for C: it replaces the malloc and the mfree becomes useless). But
>beware its limitations: such GC is generally slower and doesn't guarantee
>you won't have "memory leaks".

I have a paper by Ben Zorn of the U of Colorado at Boulder.  He
measured the performance of the Boehm conservative GC in half a dozen
programs and found that the slowdown was pretty trivial, although the
programs did need about twice as much memory.

The full report is CU-CS-573-92, April 1992, from Dept of Computer
Science, Campus box 430, University of Colorado, Boulder, Colorado
80309.

Of course, a well tuned GC that has structure information available
will do much better.  For a good survey of GC techniques, see
"Uniprocessor Garbage Collection Techniques" by Paul R. Wilson, U. of
Texas.  <wilson@cs.utexas.edu>.  This paper is available by FTP, so
try Archie before mailing Dr. Wilson.


Paul.
-- 
Paul Johnson (paj@gec-mrc.co.uk).	    | Tel: +44 245 73331 ext 3245
--------------------------------------------+----------------------------------
These ideas and others like them can be had | GEC-Marconi Research is not
for $0.02 each from any reputable idealist. | responsible for my opinions