Re: Better support for garbage collection

["Nick Roberts" <nickroberts@adaos.worldonline.co.uk>]

"Robert A Duff" <bobduff@world.std.com> wrote:

> If you're interested in garbage collection, you should get on the gc
> mailing list (gclist-digest@iecc.com).  You should also read Jones and
> Lins' excellent book called "Garbage Collection", if you haven't
> already.

Not another mailing list! I have visited the web site, and read much of
interest there. I haven't read Jones and Lins, but I have read up on the
subject.

> I too think it would be cool if GC for Ada were widely available.
> But I think youll have a hard time convincing others.  After all, any
> implementation is allowed to provide GC, but nobody has done so, except
> when the GC is unavoidable (the Ada 83 implementation on top of the
> Symbolics Lisp Machine, and the Ada 95 implementations on top of the
> JVM).  Why not?

Perhaps part of the reason is that no infrastructure for it has been
provided by the language standard. Anyway, I am proposing an optional
addition to the language; I don't expect many Ada vendors to support it, but
I feel a few might.

> Robert Dewar would argue that it's because nobody wants it (at least,
> nobody wants it enough to pay for it).  A more pessimistic take on this
> is that all the folks who understand the glorious benefits of GC have
> long since abandoned Ada in favor of "better" languages.

Don't you think it significant that so many other languages do incorporate
GC?

I must say, I get the impression, although I don't understand it, that
Robert, perhaps yourself, and a few others have an antipathy towards GC
which is not entirely objective or rational. It is not a sound argument to
say "Well, I don't want it, so nobody else does either."

The slowness of a GC environment can always be largely overcome, by using
techniques such a B-Tree's lumping data into blocks. The advantages of
having GC, especially from the point of view of software reliability, can be
very great. It is typical these days to hear advice such as "the best way to
maintain the efficiency of NT [the operating system] is to reboot it every
day". It is typical of application programs to leak memory like a sieve. I
suspect there are many Ada programs that commit the same sin, principally
because they do not have GC.

> You seem to be saying that the user provides the compaction phase, and
> the implementation provides the tracing phase.  But the tracing phase is
> the hard part.  So how does this make GC so easy to implement that
> implementers will do it when they haven't already?

If somebody refuses to dig a trench ten metres long, and I say, "Alright,
I'll dig one metre and you dig nine", they may still refuse, but then they
may not! I'm not saying my proposal will make the implementor's job
tremendously easy, just a little bit easier than it is now.

> Now to the technical points: I'm completely confused about what this
> proposal means.  I don't see how the user can write the Tidy routine.
> (Why not call it Compact?)  The Tidy routine needs to modify all the
> pointers to objects in the repositioning pool -- how is it supposed to
> find them?  It doesn't know the layout of all the records in the pool.
> Also, it can't find all the pointers from outside the pool to objects in
> the pool.

I agree with calling it "Compact" instead of "Tidy". The principle is that
this procedure does not need to modify any addresses pointing directly to
objects in the memory the pool controls. The implementation must ensure that
no pool element is ever in an unlocked state if and when Compact is (or
might be) called and moving the element is (or might be) unsafe, in that a
temporarily held address pointing into it may be used to read or write
within the (old position of the) element.

> A sample implementation of package Repositioning would help me
> understand.  Eg, what is the intended implementation of tokens?
> (Or at least one possible implementation?)

The difficult will take an hour. The impossible will take a little longer!
I'll try to cook up an example.

> Note that you can have pointers into the middle of objects -- these also
> need to be adjusted when objects move around in memory.  (Pointers to
> aliased components.  Renamings of components.  Components passed by
> reference.)

Again, it is the responsibility of the implementation to ensure that a pool
element is either locked or safely movable whenever Compact is (or might be)
called.

> Note that the tracing phase needs to trace the whole world (all stacks
> and storage pools) whenever *any* repositioning pool is collected,
> because you haven't proposed to restrict pointers from the outside.

Generally true (but not actually a problem). Perhaps I should rephrase my
proposal to make this clear.

> You didn't say when the compiler is supposed to generate calls to the
> Allocate and Deallocate routines (the ones with token parameter), so I
> don't understand the point of them.

A compiler which supports GC will use the ones with the Token parameter.
Compilers which do not support GC will (naturally) use the ones with the
Storage_Address parameter.

> Note that it is not always known at compile time whether a given access
> type's pool is a repositioning pool, so the code generated for "new" and
> "Unchecked_Deallocation" must be as in the RM (eg, these can't call the
> new Allocate).

In the unlikely case of an access type whose pool is specified by a dynamic
name, I think you are correct. The user would need to use a static name to
avoid this problem.

> > Each pool element has a 'lock count', of an unspecified integer (or
> > modular) subtype, whose range does not exceed that of Standard.Natural.
The
> > element is said to be 'locked' if its lock count is a value other than
0.
>
> Nonnegative, right?

As implied by the range being restricted by that of Standard.Natural, yes.

> > The overloading of the Allocate procedure with a Token parameter sets
the
> > lock count of the pool element it allocates to 0, reserves a block of
> > memory, and reserves a token for the element, whose value is passed out
to
> > the Token parameter.
>
> I don't see how it can reserve a block of memory, since it doesn't take
> size and alignment parameters.  I'm confused as to what this routine is
> for.

You are dead right. I missed these parameters out. Apologies. It should have
been:

      procedure Allocate(
         Pool : in out Repositioning_Storage_Pool;
         Token : out Object_Token;
         Size_in_Storage_Elements : in Storage_Elements.Storage_Count;
         Alignment : in Storage_Elements.Storage_Count) is abstract;

> > I suggest a recommendation (or perhaps a stipulation) that the maximum
lock
> > count is never less than 15. (Although this recommendation will apply to
> > the user rather than the implementation, except for
implementation-supplied
> > repositioning pools.)
>
> I don't see the point of such a recommendation.

The point is simply to prevent repositioning pools providing an inadequate
range, whilst not actually pinning them down to a specific, artificial,
figure.

> > The first stage of the garbage collection process is 'scavenging', the
> > recognition and deallocation of allocated objects which have become
> > 'unreachable' (inaccessible by any degree of indirection). This stage
needs
> > to be carried out by code specially generated by the compiler.
>
> But that's not really how many (most?) GC's work.  The don't recognize
> unreachable objects, and they don't deallocate them individually.  They
> find all the *reachable* objects, and whatever's left over is garbage.
> In a copying collector, the garbage need not be touched.

I didn't mean to give the impression that what I described is how many or
most garbage collectors work. All I meant was that what I described is how a
garbage collector would have to work to be compatible with my proposal.

> So the cost of
> GC is proportional to the amount of reachable data.  If you have to
> individually deallocate all the garbage objects, then it's proportional
> to the size of the heap, which seems bad.

I am assuming that implementors would implement a generational scheme that
would avoid the whole pool having to be scanned at each compaction. (I
suppose you'll want me to demonstrate this in my example too :-)

> >    subtype Disposability_Level is
> >       Integer range 0..implementation_defined;
>
> Why "implementation_defined"?  It seems like a useless non-portability.

Okay, what figure do you suggest?

> > and an attribute Disposability, which applies to any pool-specific
access
> > type, and has a static value of subtype Disposability_Level.
>
> This is the first attribute of a non-scalar type that is static.

Is this a problem?

> >... A value other
> > than 0 indicates that objects referenced by access values of this access
> > type are disposable.
>
> It makes no sense to talk about the objects "referenced by access values
> of this access type", because there can be many access values, of many
> different types, all pointing to the same object.  Perhaps you mean
> "allocated by allocators for this access type"?

What I said is perfectly logical, apart from using the wrong word ...

> (BTW, "designated" is the Ada jargon -- not "referenced".)

... Whoops! (Pardon me :-) ...

I really meant "all objects designated by access values of this type". It
doesn't matter if some of those objects (or any of their subcomponents) are
designated by access values of other types.

Perhaps I should add a specific note that if an object is designated by
several access values, of access types whose disposability levels are
different (but non-zero), the highest of those disposability levels applies.

> Deallocating a disposable object can leave dangling pointers (which is
> the whole point of GC to avoid).  Are you assuming the Finalize routine
> will track them all down and do something about them (eg null them out)?
> What happens if it doesn't.

I omitted to note that an object should only be disposed (deallocated
automatically by the implementation, even while being reachable) if it is
unlocked (or not in a repositioning pool). From the user's point of view, it
would be necessary for the Finalize procedure to signal to the rest of the
program that the object was no longer extant. I did toy with the idea of
providing a callback procedure to allow the program to be notified of
disposals.

> You didn't mention anything about finalization of normal
> (non-disposable) objects.  There are nasty interactions
> there.  Eg, can the finalization routine resurrect the object
> by creating a new pointer to it?  Java has an answer to this
> (not a very good one, IMHO).

I believe Java's 'answer' is a mess. My preference would be that
resurrection is simply disallowed (erroneous), thus the object is always
truly deallocated when Finalize returns.

> It seems like the compiler must generate a Lock before each call where a
> movable object is passed by reference (or a part of such an object).
> And it must remain locked throughout that call, because the called
> procedure doesn't know whether it has a pointer into a repositioning
> pool.  Doesn't sound very "frequent".

This is true, but if you look more closely at typical 'real-life'
situations, you will see that it actually causes very little problem in
practice.

> For that matter, it seems like it has to Lock even if the thing is
> passed by copy, because the address of the actual is presumably saved at
> the call site (at least in some cases).

Ditto.

> - Bob

I'm very grateful for your comments, Bob. Indeed, I'm grateful for the lack
of eerie silence that can attend my posts to this newsgroup sometimes.

The question that remains, to my mind, of what action for me to take next
reduces to three basic possibilities: (a) make the amendments suggested
herein, and send the proposal to the ARG (which e-mail address would be
best?); (b) continue discussing the proposal in this newsgroup (or
elsewhere?), and submit it later, after perhaps much refinement; (c) forget
it.

I MUST go now and get some sleep!

--
Nick Roberts
http://www.AdaOS.org
nickroberts@adaos.worldonline.co.uk

PS: Please note my correct email address above.