Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

["Robert I. Eachus" <rieachus@attbi.com>]

Larry Kilgallen wrote:

> Garbage collection is important to particular problem domains like AI.
> People who need it do not appear to be a significant portion of the
> Ada-using public.

This is just plain wrong.  There may be some portion of the general 
programming world that needs a generalized garbage collector.  But AI is 
not it.  I wrote a reference counting package in Ada for an AI project 
that thought they needed a garbage collector that would run in a 
background task so that their code was not subject to garbage collection 
delays at arbitrary places.  I showed that the requirements for the GC 
they were asking for couldn't be met that way but a one page package 
could do exactly what they needed via reference counts.

Yes, I know that "ordinary" reference counting can't deal with circular 
chains.  But  it turned out that for their data, there was an easy way 
to deal with that issue, using that low priority task they wanted.  This 
was a data fusion AI for a radar net.  In theory circular references 
could occur and result in garbage that required that background task to 
collect it.  But the system was nicely instrumented, and during the 
entire formal qualifaction period the background task collect zero 
objects. Several hundred million of course were dealt with in real-time 
with guaranteed behavior.

The system had I think, 20,000 potential objects in the pool (all were 
fixed size). The maximum reached during the qual testing was seven 
thousand something with a set of test data from the LA area.  Oh, and 
the code was around four pages, one for the package spec, two for the 
body, plus one for the background task.  The way it worked was that 
every every pointer object contained a level which was in some sense how 
far it was from the root pointer.

Every data object contained two values, the object's level, the count of 
pointers from objects at the next higher level.  If an object was 
pointed to by a new reference from a higher level object, its level was 
raised, and a treewalk was done by the background task to reset the 
levels of other objects.  If you think about it for a minute you will 
see that hoisting a object sets the count of pointers from higher levels 
to one.  If an object reached a reference count of zero, it was put on a 
list to be potentially discarded.  Well, actually there was a global 
flag. If it was set to false, there were no objects in the treewalk, and 
garbage could be discarded immediately.  If it was true, the backgound 
task was doing a treewalk, and objects had to be put on a potential 
holding list.

In practice, in this application the flag was almost never true. 
Setting it to true occured only during a rendezvous between the two 
tasks.  Setting it to false was not a synchronizing event.  It would 
probably be easier to recreate the code than describe it.

So to sum up:

1) In Ada, any thought that you need garbage collection indicates you 
should be using a container class.

2) Writing the container class in Ada is a pretty simple job, if one 
doesn't already exist.

3) No container class needs to have "full" garbage collection provided 
by the environment.

4) Unchecked_Deallocation means that the designer of the container class 
does the checking, and usually provides--if necessary--a Free operation 
that does the right thing. Whatever that may be.

5) For most programers, learning when to use Ada.Strings.Unbounded is 
the closest they will ever come to garbage collection.