Re: Is the Writing on the Wall for Ada?

["Robert I. Eachus" <rieachus@comcast.net>]

Marin David Condic wrote:
> In all these cases, I've 
> never once felt even the slightest bit deprived by not having a compiler 
> that had GC. (Its possible one of them might have had it - I never 
> noticed.) Hence, I find it difficult to understand why people regularly 
> bring up GC as some sort of "significant shortcoming" of Ada.

Actually I may have stated things incorrectly.  Every Ada compiler you 
have used has garbage collection.  But what is required to implement the 
standard is that certain types that can be managed by some variation on 
reference counting be managed correctly.  In fact, the only such case in 
Ada 83 was objects of a task type.

And of course, it is exactly in the task type case that you can't use a 
"general" garbage collector with arbitrary collection times.  In Ada 95 
we added Ada.Strings.Unbounded.  Unbounded_Strings can't contain user 
defined pointers to other Unbounded_Strings, but it is required to be 
collected.  (Whether an Unbounded_String object contains other pointers
including pointers to other Unbounded_Strings is, of course, 
implementation defined.)

So it comes down to the fact that Ada provides a rich set (if you 
include Controlled types) of primitives for managing garbage, but no 
generalized garbage collection.

Now let me digress for a bit.  Anyone here who has studied compiler 
design knows that there is a tree, the abstract syntax tree (AST) that 
corresponds to a program being parsed.  This is then "decorated" with 
symantic information.  The symantic information creates lots of further 
nodes, and also creates lots of further links converting the parse tree 
into a directed graph.  Horrible garbage collection problem right? 
Wrong.  To be useful it has to be be possible to walk both the AST and 
the decorated tree visiting each node.  This is done by keeping 
structural relationships separate from semantic relationships.  When a 
new node is created, it has a parent, either the node that the compiler 
was looking at when it recognized new syntax structures (very generally 
speaking) or the parse node that the semantic information belongs to.

In fact on some parse tools I have used, you can set a debug mode which 
will instantly detect any loop in the AST.  (This is obviously an error, 
  and it is much easier to catch it immediately.)  I have never used 
that capability, since in that environment I was always doing the 
parsing, and someone else did the semantic analysis.  And since I was 
using a tool to build the parser, anything that would have caused a loop 
in the AST meant that my grammar wasn't going to get through the tool.

(End digression.)  So here we have an area that "looks like" it is 
perfect for full garbage collection, and any compiler group that writes 
their compiler in Ada is going to be putting a lot of effort into 
maintaining ASTs and decorating them.  So why don't they just use 
garbage collection?  It is way too damn slow.  I don't know if any Ada 
compilers are still using relocatable parse tree structures, I know 
Intermetrics and Verdix both did once upon a time.  So it is not the 
overhead of relocation that can occur in a compacting garbage collector 
that is the issue, it is garbage collection overhead itself.

The problem is that the parse tree in Ada is really a forest of trees 
for separate compilation units (or I think in the original DEC Ada 
compiler compilations).  When you compile a with clause, you need to 
bring a representation of the parse tree for that unit in from the 
library.  (Yes, I know that GNAT and the Intermetrics front-end now 
reparse package specs instead of loading the AST, but that is an 
optimization.) Think of the number of calls to malloc or the equivalent 
that would be required, and compiling with clauses will make the 
compiler crawl a lot slower than it does now.  So you grab chunks of 
memory, slice them up with internal pointers, and when you no longer 
need that tree you free the chunks--which have valid pointers all over 
the place, along with valid pointers in from other trees into them.  So 
a full garbage collect would fail, but a reference counting collector 
works just fine.

And that is the biggest problem with getting "full" garbage collection 
in most Ada compilers.  The compiler group knows that they need to 
protect their parse trees from the collector, or the compiler will run 
significantly slower with no real benefit to them or to the user.  So 
they install a switch.  The compiler runs significantly faster when 
compiled with the switch off, and surprise, so do most other programs as 
well.  Eventually someone runs out of memory, and say, "Ah, ha! Now I 
turn on GC."  But it doesn't work.  And no one wants to take the effort 
to figure out whether the garbage collection was just that slow when 
invoked, or if it was broken three compiler releases back.

You would think that "just" managing a particular storage pool would be 
a solution.  But you still have the distributed overhead in that the 
garbage collector has to manage (or identify) all pointers into the GC 
pool.  There is another attempt to add a usable version of a 
conservative collector to GNAT, we will see if it is successful.

Of course, if you have been following, you will realize that my 
definition of successful is become widely used and be supported.  The 
work to add a GC managed storage pool to Ada is about three days work 
for any particular hardware.  It probably takes a lot less to add a 
conservative collector for a second and subsequent ISA targets.  But 
supporting such a collector and maintaining it is probably call it 1/4 
of a full-time job.  Way too much for a hobbiest, and as we have seen 
there just isn't enough interest for a comiler vendor to do it.  At 
Symbolics, they had the "advantage" that supporting their garbage 
collector was already a full-time or more job for the OS department, and 
the Ada compiler could just use it along with the Lisp people.

-- 
                                      Robert I. Eachus

"Quality is the Buddha. Quality is scientific reality. Quality is the 
goal of Art. It remains to work these concepts into a practical, 
down-to-earth context, and for this there is nothing more practical or 
down-to-earth than what I have been talking about all along...the repair 
of an old motorcycle."  -- from Zen and the Art of Motorcycle 
Maintenance by Robert Pirsig