Garbage Collection in Ada

Garbage Collection in Ada

[Jonas Nygren]

Recently there has been some topics that has touched on the issue
of Garbage Collection, GC, in Ada. I peronally think it would be great to
have
GC in Ada and I am not sure why there is such resistance. I have a couple
of questions on this GC issue.

Many claim GC is not well suited for real-time applications - well if it is
possible at all to implement GC in Ada then it is just a question of making
the GC feature optional. This could be accomplished by compile-time
'switches' to turn GC on or off. Or one could use the same strategy as
for Ada.Finalization, e.g.:

package Garbage_Collection is
   type Collected is tagged private;
   ....
end Garbage_Collection;

Is there more to the real-time issue. Is it not sufficient to make GC
optional?

Probably the greatest obstacle is to implement GC. I have tried to study
some of the papers available and at times I believe I understand the
different approaches available but I soon lose clarity when I try to
understand
how one would go about to implement it. My understanding of compiler
technology and internals is way low.

So my second question: Is it at all possible to implement GC in Ada ?
(with a reasonable effort, whatever that is),

/jonas

Re: Garbage Collection in Ada

[Robert Dewar]

Jonas said

Recently there has been some topics that has touched on the issue
of Garbage Collection, GC, in Ada. I peronally think it would be great to
have GC in Ada and I am not sure why there is such resistance.
I have a couple of questions on this GC issue.

  I don't think anyone resists the idea that it would be attractive for
  Ada implementations to implement GC, although there always in the past
  has been opposition to the idea of requiring this feature. However,
  there does not seem to be any great commercial interest. No one seems
  interested enough so far to consider funding such a capability, and
  so far no Ada company has estimated that there is sufficient interest
  to warrant investing their own resources in such an implementation
  effort. Perhaps, as I have noted before, Java will change the landscape
  enough to change this state of affairs.

Many claim GC is not well suited for real-time applications - well if it is
possible at all to implement GC in Ada then it is just a question of making
the GC feature optional. This could be accomplished by compile-time
'switches' to turn GC on or off. Or one could use the same strategy as
for Ada.Finalization, e.g.:

  Obviously pragma Restrictions is the appropriate way to handle such
  a capability!

Probably the greatest obstacle is to implement GC. I have tried to study
some of the papers available and at times I believe I understand the
different approaches available but I soon lose clarity when I try to
understand how one would go about to implement it. My understanding of
compiler technology and internals is way low.

  That's the only obstacle. Obviously if it were easy to implement optional
  garbage collection, everyone would do it!

So my second question: Is it at all possible to implement GC in Ada ?
(with a reasonable effort, whatever that is),

  Yes, abosolutely it is possible. I am sure that any Ada company would be
  happy to give you a quotation on what it would take to implement this
  feature if you are seriously interested!

Re: Garbage Collection in Ada

[Lars Farm]

Jonas Nygren <ehsjony@ehs.ericsson.se> wrote:

> Recently there has been some topics that has touched on the issue of
> Garbage Collection, GC, in Ada. I peronally think it would be great to
> have GC in Ada and I am not sure why there is such resistance. 

Cultural bias or even prejudice is the most likely reason IMHO. Not
technical reasons. On and off the same discussion comes up in the C++
community. Those that control C++ and those that control Ada simply
don't want GC :-( Being in the C++ world, I can't speak about
technicalities in Ada, but the arguments from the GC detractors among
C++ and Ada users appear to be similar. They say that no one wants GC.
They say that GC is slow and that there are certain constructs in the
languages that make GC impossible or useless or that this or that
particular implementation of GC cant work and therefor any
implementation of GC is out of the question.

One particularly annoying argument goes like: "Memory is a resource, GC
manages memory so GC should be able to manage any resource. Since it
only manages memory it fails and is useless". This is nonsense because
managing memory is a particularly nasty problem and GC solves it almost
completely. That it leaves all other problems is an advantage, not a
liability. This is usually called good design, high coherence. GC does
one thing, one thing only and does it very well.

Another common nonsense argument against GC is real time behaviour. GC
is no different than ordinary allocators. They have no time constraints
either. If one needs absolutely predictable timing one has to manually
take over memory management for that section of code with GC and with
ordinary allocators anyway.

As for C++ the GC-dangerous constructs are very few and very obscure and
luckily rarely used and easily avoided. Using them usually invokes
"undefined behaviour" anyway (deliberately hiding pointers from the GC -
on disk or with various xor tricks,...). In practice GC (conservative
collector by Boehm) works very well with C++ and in my experience is
faster than ordinary new/delete. If one also uses the fact that one has
a GC in the design, things become faster still. Less need to copy
datastructures (there is a lot of redundant copying in C++ out of fear
that one wont know when to release memory otherwise). Granted, the speed
is not just because of GC, but also because Boehms GC (that I have used
in C++) is a much better allocator than the ones delivered with my dev
systems.

For Ada one of the technical obstacles mentioned is something called
"virtual origin". A block of memory held by a biased pointer that points
at some distance outside the block. Presumably a compiler optimizer
trick allowed by the language. That seems like a harder problem than the
problems in C++ and that in turn is ironic. Ada allows GC, C++ doesn't
even acknowledge its existence. One would have thought that the stricter
Ada would be easier to adapt to GC than the "sloppy" C++. 

None of the arguments above has convinced me that GC is a bad thing and
I'm perfectly willing to avoid some weird C++ language constructs if it
gives me GC. It would be interesting to hear what other arguments the
Ada vendors could come up with. It would be even more interesting if
they could say something like "Sure GC is possible, but you'd have to
sacrifice language feature this or that" and then leave the choice up to
the users.


-- 
Lars Farm, lars.farm@ite.mh.se

Re: Garbage Collection in Ada

[Robert Dewar]

Lars says

"Cultural bias or even prejudice is the most likely reason IMHO. Not
technical reasons. On and off the same discussion comes up in the C++
community. Those that control C++ and those that control Ada simply
don't want GC :-("

That's nonsense I think. It's just a matter of market supply and demand.
Some Ada compilers (not many) have GC, most do not. If most Ada programmers
want GC, more compilers will have it. The various bogus reasons you give
for worrying about GC seem irrelevant to me.

Just one point, virtual origins are not a problem at all in a proper
garbage collector, only in approximate "conservative" ones, which are
not so conservative and are happy to remove blocks in use if virtual
orgins around. The technique of using virtual origins can perfectly
well be used in C (see the sources of gigi for an example of this use).

Re: Garbage Collection in Ada

[Larry Kilgallen]

In article <199610132138291604607@dialup101-6-14.swipnet.se>, lars.farm@ite.mh.se (Lars Farm) writes:
> Jonas Nygren <ehsjony@ehs.ericsson.se> wrote:
> 
>> Recently there has been some topics that has touched on the issue of
>> Garbage Collection, GC, in Ada. I peronally think it would be great to
>> have GC in Ada and I am not sure why there is such resistance. 
> 
> Cultural bias or even prejudice is the most likely reason IMHO. Not
> technical reasons. On and off the same discussion comes up in the C++
> community. Those that control C++ and those that control Ada simply
> don't want GC :-( Being in the C++ world, I can't speak about
> technicalities in Ada, but the arguments from the GC detractors among
> C++ and Ada users appear to be similar. They say that no one wants GC.

Postings from just one individual disprove any "no one wants" claim,
but I think what you are actually hearing from Ada implementors is
"not enough paying customers want".  Ada has many virtues, but there
is not an endless supply of Ada compiler customers, so implementors
must direct their resources toward implementing the most "popular"
capabilities.

There may be cultural bias, but it originates with the customer base.
I think you will find that every customer for Ada compilers has a
wishlist, and garbage collection is not near the top of most.  Bias
toward the features most important for one's own needs is fully
reasonable.

Larry Kilgallen

Re: Garbage Collection in Ada

[Lars Farm]

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

> (Assuming you take "no one wants GC" to be just an exagerated way of
> saying "not enough people want GC".)

Yes.

> IMHO, the cultural bias against GC is fueled in part by GC zealots who
> claim that GC does more than it really does.

Yes, I hope I haven't added to that.

> And I *still* hold the opinion that GC is bad for some kinds of
> programs.

I don't think of GC as a Silver Bullet, just a very useful tool.

> >They say that GC is slow and that there are certain constructs in the
> >languages that make GC impossible or useless or that this or that
> >particular implementation of GC cant work and therefor any
> >implementation of GC is out of the question.
> 
> This may be true of C++, but GC is quite compatible with Ada.

For Ada I was thinking of virtual origins and conservative collectors,
but I realise there are other algorithms. For C++ I think the only
reasonable alternative is a conservative collector and figured the same
was true for Ada. OTOH I also disclaimed any expertise of Ada so perhaps
my error can be forgiven?

> >GC does one thing, one thing only and does it very well.
> 
> This might be a symptom of what I was saying above -- if zealots claim
> that GC solves all the worlds problems, then it's easy to disprove that,
> and therefore write it off.

Yes.

> >Another common nonsense argument against GC is real time behaviour. GC
> >is no different than ordinary allocators. They have no time constraints
> >either. If one needs absolutely predictable timing one has to manually
> >take over memory management for that section of code with GC and with
> >ordinary allocators anyway.
> 
> I don't understand what you mean by "ordinary allocators".  What you say
> is certainly true of off-the-shelf general-purpose allocators,

An ordinary allocator would be the one prescribed in the language spec
(operator new in C++ or its equivalent in Ada). No more suited for
realtime stuff than a collecting allocator.

> but it's
> easy to write an allocator with predictable timing if the objects are
> all of the same size, and that's exactly what some real-time programs
> do.

This is what I had in mind for "manually take over memory management".
Such allocators are staight forward to write in C++ and I assume in Ada
too.

> In Ada, this is true.  In C and C++, I don't believe it -- I've seen
> lots of code that uses pointers/arrays in a GC-unsafe way.  Perhaps it
> doesn't *need* to, but it does.

There are legal things that can break a conservative collector, but they
are few. I've seen lots of illegal code in C or C++ that happens to work
in this or that particular implementation. What can I say. Broken code
is broken. This is no argument against GC. The next version of the
standard operator new might break such code too or a new (legal)
compiler optimization or...

> >One would have thought that the stricter
> >Ada would be easier to adapt to GC than the "sloppy" C++. 

This is probably saying more about my knowledge of Ada than anything
else... (see above)

> To me, this sounds backwards.  Virtual origins are a useful
> optimization, and if they break your GC, then your GC is broken.

No, I didn't claim that Boehms collector worked in Ada. I said it works
nicely in C++ and it does! The Boehm GC is written for for C and C++
where such techniques are forbidden. A pointer can be NULL, can point at
or into an object or at the imaginary element directly after the last
element of an array. Anything else is illegal. So virtual origins are
definitely illegal in C++ and therefor not an issue for Boehms collector
used in C or C++. Boehms collector correctly handles the legal cases,
but AFAIK not pointers pointing at other seemingly unrelated offsets of
the block. Therefor Boehms GC isn't broken because of virtual origins,
but virtual origins prevents the use of that collector in Ada.


-- 
Lars Farm, lars.farm@ite.mh.se

Re: Garbage Collection in Ada

[Jon S Anthony]

In article <1996Oct13.194807.1@eisner> kilgallen@eisner.decus.org (Larry Kilgallen) writes:

> "not enough paying customers want".  Ada has many virtues, but there
> is not an endless supply of Ada compiler customers, so implementors
> must direct their resources toward implementing the most "popular"
> capabilities.
> 
> There may be cultural bias, but it originates with the customer base.
> I think you will find that every customer for Ada compilers has a
> wishlist, and garbage collection is not near the top of most.  Bias
> toward the features most important for one's own needs is fully
> reasonable.

A chicken or egg problem if there ever was one.  I certainly could use
GC in what I'm doing - I now have had to basically roll my own for the
particular application.  We don't have the $$ to actually fund such an
effort - say in GNAT by ACT.  Not alone that's for sure.  But I would
bet that there are quite a few such people out here who want it, but
can't fund such an effort alone.  I also know of many others that make
the claim that lack of GC is about the only thing that keeps them from
using Ada.  Chicken?  Or egg?

/Jon

-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com

Re: Garbage Collection in Ada

[Robert A Duff]

In article <199610132138291604607@dialup101-6-14.swipnet.se>,
Lars Farm <lars.farm@ite.mh.se> wrote:
>Jonas Nygren <ehsjony@ehs.ericsson.se> wrote:
>
>> Recently there has been some topics that has touched on the issue of
>> Garbage Collection, GC, in Ada. I peronally think it would be great to
>> have GC in Ada and I am not sure why there is such resistance. 
>
>Cultural bias or even prejudice is the most likely reason IMHO. Not
>technical reasons. On and off the same discussion comes up in the C++
>community. Those that control C++ and those that control Ada simply
>don't want GC :-( Being in the C++ world, I can't speak about
>technicalities in Ada, but the arguments from the GC detractors among
>C++ and Ada users appear to be similar. They say that no one wants GC.

Well, "GC is good" and "no one wants GC" are not contradictory.
(Assuming you take "no one wants GC" to be just an exagerated way of
saying "not enough people want GC".)  After all, in the PC world, I've
read several articles about how multi-tasking is useless from the user's
point of view.  Kind of like a driver who knows nothing about how cars
work, saying "Pistons are useless".  ;-)

IMHO, the cultural bias against GC is fueled in part by GC zealots who
claim that GC does more than it really does.  I know for a fact that I
myself took many years to come to the opinion that GC is good for many
(most?) programs, primarily because I didn't believe the zealous
claims.

And I *still* hold the opinion that GC is bad for some kinds of
programs.

>They say that GC is slow and that there are certain constructs in the
>languages that make GC impossible or useless or that this or that
>particular implementation of GC cant work and therefor any
>implementation of GC is out of the question.

This may be true of C++, but GC is quite compatible with Ada.

>One particularly annoying argument goes like: "Memory is a resource, GC
>manages memory so GC should be able to manage any resource. Since it
>only manages memory it fails and is useless". This is nonsense because
>managing memory is a particularly nasty problem and GC solves it almost
>completely. That it leaves all other problems is an advantage, not a
>liability. This is usually called good design, high coherence. GC does
>one thing, one thing only and does it very well.

This might be a symptom of what I was saying above -- if zealots claim
that GC solves all the worlds problems, then it's easy to disprove that,
and therefore write it off.

>Another common nonsense argument against GC is real time behaviour. GC
>is no different than ordinary allocators. They have no time constraints
>either. If one needs absolutely predictable timing one has to manually
>take over memory management for that section of code with GC and with
>ordinary allocators anyway.

I don't understand what you mean by "ordinary allocators".  What you say
is certainly true of off-the-shelf general-purpose allocators, but it's
easy to write an allocator with predictable timing if the objects are
all of the same size, and that's exactly what some real-time programs
do.  And some real-time programs avoid using the heap at all, so of
course GC is just a waste of implementer's time, for *those* programs.

I know about Henry Baker's papers on real-time GC, but I remain somewhat
skeptical.  (I suspect most real-time programmers have never heard of
real-time GC, and would scoff at it.)

>As for C++ the GC-dangerous constructs are very few and very obscure and
>luckily rarely used and easily avoided. Using them usually invokes
>"undefined behaviour" anyway (deliberately hiding pointers from the GC -
>on disk or with various xor tricks,...).

In Ada, this is true.  In C and C++, I don't believe it -- I've seen
lots of code that uses pointers/arrays in a GC-unsafe way.  Perhaps it
doesn't *need* to, but it does.

>... In practice GC (conservative
>collector by Boehm) works very well with C++ and in my experience is
>faster than ordinary new/delete. If one also uses the fact that one has
>a GC in the design, things become faster still. Less need to copy
>datastructures (there is a lot of redundant copying in C++ out of fear
>that one wont know when to release memory otherwise). Granted, the speed
>is not just because of GC, but also because Boehms GC (that I have used
>in C++) is a much better allocator than the ones delivered with my dev
>systems.
>
>For Ada one of the technical obstacles mentioned is something called
>"virtual origin". A block of memory held by a biased pointer that points
>at some distance outside the block. Presumably a compiler optimizer
>trick allowed by the language. That seems like a harder problem than the
>problems in C++ and that in turn is ironic. Ada allows GC, C++ doesn't
>even acknowledge its existence. One would have thought that the stricter
>Ada would be easier to adapt to GC than the "sloppy" C++. 

To me, this sounds backwards.  Virtual origins are a useful
optimization, and if they break your GC, then your GC is broken.  It's
not the compiler's fault.  It's certainly possible to implement a GC
that works in the presence of this optimization.  And there are many
other examples of optimizations that will break the typical
"conservative" GC, but a proper non-conservative GC can work properly.
The term "conservative" is bogus, IMHO, since if you do certain things
in your code, or your friendly compiler-writer does certain
optimizations, it makes the GC *liberal* -- that is, frees in-use data.
Avoiding certain things in my code is tolerable, but it makes me nervous
to think that the new version of a compiler, with a smarter optimizer,
might come along and break the conservative GC.

>None of the arguments above has convinced me that GC is a bad thing and
>I'm perfectly willing to avoid some weird C++ language constructs if it
>gives me GC. It would be interesting to hear what other arguments the
>Ada vendors could come up with.

No, Ada vendors are not typically part of the anti-GC crowd.  The
vendors tend to say, "GC is somewhat hard to implement, and we don't
have a lot of customers asking for it."  It's kind of unfortunate,
because there are probably quite a few people who *would* use Ada, if
Ada compilers with GC were commonly available.  Probably this situation
will change in the future.

>... It would be even more interesting if
>they could say something like "Sure GC is possible, but you'd have to
>sacrifice language feature this or that" and then leave the choice up to
>the users.

There's really not much you have to give up, unless you're dealing with
a so-called conservative GC.

By the way, the Intermetrics compiler that generates Java byte codes
supports GC (the non-conservative GC supported by Java), and I believe
somebody is working on a conservative GC for GNAT.

- Bob

Re: Garbage Collection in Ada

[John Howard]

On Sun, 13 Oct 1996, Lars Farm wrote:
[snip]
> managing memory is a particularly nasty problem and GC solves it almost
> completely.
[snip]

GC just provides *automatic* deallocation of "unreachable" dynamically
allocated objects.  GC is not cost-free.  Ada 95 flexibly provides a
programmer with capable mechanisms to manually manage memory.  Plus the
safeguards of Ada help minimize creating slop to clean up and so the
deallocation can likely be managed easily enough manually.  I am not 
against using GC if its reliability is guaranteed and it saves me some 
money.  Otherwise I prefer to manually control the deallocation.

> Another common nonsense argument against GC is real time behaviour. GC
> is no different than ordinary allocators. They have no time constraints
> either. If one needs absolutely predictable timing one has to manually
> take over memory management for that section of code with GC and with
> ordinary allocators anyway.
>
> As for C++ the GC-dangerous constructs are very few and very obscure and
> luckily rarely used and easily avoided. Using them usually invokes
> "undefined behaviour" anyway (deliberately hiding pointers from the GC -
> on disk or with various xor tricks,...). In practice GC (conservative
> collector by Boehm) works very well with C++ and in my experience is
> faster than ordinary new/delete. If one also uses the fact that one has
> a GC in the design, things become faster still. Less need to copy
> datastructures (there is a lot of redundant copying in C++ out of fear
> that one wont know when to release memory otherwise). Granted, the speed
> is not just because of GC, but also because Boehms GC (that I have used
> in C++) is a much better allocator than the ones delivered with my dev
> systems.

You argue that GC is already worthwhile for the culture of C++ 
programming.  Perhaps it is most cost-effective if an operating system
does GC instead of having several programs doing their own GC.  That seems
to be a goal of the Java Virtual Machine.

[snip]
> Ada allows GC, C++ doesn't even acknowledge its existence.  One would
> have thought that the stricter Ada would be easier to adapt to GC than
> the "sloppy" C++.
[snip]
> Lars Farm, lars.farm@ite.mh.se

I argue that GC is far less worthwhile for the culture of Ada programming.
(Similarly Ada spared us from needing an equivalent C Lint program to 
clean up code).

From "Ada as a Second Language" (2nd ed.) by Norman Cohen, ISBN
0-07-011607-5, McGraw-Hill:
Section 8.2 p. 328
"
  The rules of Ada also allow "garbage collection"---automatic
  deallocation of dynamically allocated objects that are no longer
  pointed to by any other variables in the program, that are pointed
  to only by other dynamically allocated objects that are themselves
  no longer pointed to, and so forth.  Such objects are said to be
  unreachable because there is no way to refer to them. [...] Some
  implementations of garbage collection continually slow down a
  program's ordinary computations; other implementations are not
  invoked until the program needs more storage, at which point all
  ordinary computations are momentarily halted while the garbage
  collector does its work.  Either behavior is usually unacceptable
  in a real-time program.  Therefore, Ada provides a pragma allowing
  you to ensure---in the unlikely event that your compiler supports
  garbage collection---that the garbage collector will not get
  invoked.  The pragma Controlled ( access-type-name ); ensures that
  objects created by allocators for the named access type will not
  be garbage-collected. [...]

  There are many possible data structures and algorithms for managing
  the storage to be used for dynamic allocation and deallocation.
  One scheme may use up more space but take less time than another.
  The performance of some schemes may depend on the patterns of
  allocations and deallocations requested by your program.  [...]
  But certain highly tuned programs may require special
  storage-management schemes tailored to the application.
  Section 19.5.1 will describe advanced mechanisms for specifying
  programmer-defined subprograms to be invoked by the evaluation of
  an allocator or a call on an instance of Ada.Unchecked_Deallocation.
"
-- John Howard <jhoward@sky.net>               -- Team Ada  Team OS/2 --

Re: Garbage Collection in Ada

[Lars Farm]

John Howard <jhoward@sky.net> wrote:

> GC just provides *automatic* deallocation of "unreachable" dynamically
> allocated objects.  GC is not cost-free.  Ada 95 flexibly provides a
> programmer with capable mechanisms to manually manage memory.  Plus the
> safeguards of Ada help minimize creating slop to clean up and so the
> deallocation can likely be managed easily enough manually.

With GC the problem of "clean up" of memory is defined away. There is no
way to be "sloppy" about deallocating memory with GC. There is no
problem, pure and simple. That this is hard to accept is IMHO a clear
indication that this really is a hard problem (without GC). We are so
afraid of memory leaks that we find it very hard to accept an automatic
solution. Note: this doesn't mean that GC solves every conceivable
memory related problem, but knowing when to release memory is solved so
the result is not "slop to clean up".

>   But certain highly tuned programs may require special
>   storage-management schemes tailored to the application.
>   Section 19.5.1 will describe advanced mechanisms for specifying
>   programmer-defined subprograms to be invoked by the evaluation of
>   an allocator or a call on an instance of Ada.Unchecked_Deallocation.

Sure, if a solution solves a majority of problems and leaves some to
traditional techniques, is that not better than a solution that solves
none?


-- 
Lars Farm, lars.farm@ite.mh.se

Re: Garbage Collection in Ada

[Robert Dewar]

Lars said

"With GC the problem of "clean up" of memory is defined away. There is no
way to be "sloppy" about deallocating memory with GC. There is no
problem, pure and simple. That this is hard to accept is IMHO a clear
indication that this really is a hard problem (without GC). We are so
afraid of memory leaks that we find it very hard to accept an automatic
solution. Note: this doesn't mean that GC solves every conceivable
memory related problem, but knowing when to release memory is solved so
the result is not "slop to clean up"."


Hmmm! I am surprised anyone would write this if they had used GC languages.
The problem of cleanup is not define away at all, and indeed, in some
respects can be trickier, because you don't think about it up front as you
have to in a system where you use finalization for freeing things, or even
more manual techniques.

The problem is that it is all too easy to have a global variable around
that accidentally holds on to a giant structure. Or for example, depending
on your implementation, taking the 'Access of one field of one record in
some big structure may end up holding on to an entire subgraph that you
do not need.

You may in practice need to be just as careful about adding

   Junk := null;

statements to your program as you are now about adding

   Free (Junk);

statements to your program now. 

GC is certainly a magic bullet solution to the problem of accidentally
freeing storage that should not be freed, but it is NOT a magic bullet
with respect to not freeing things that should be freed. People who 
approach a GC language environment with this expectation will be
disappointed!

Re: Garbage Collection in Ada

[Robert A Duff]

In article <19961014235451303023@dialup118-1-7.swipnet.se>,
Lars Farm <lars.farm@ite.mh.se> wrote:
>I don't think of GC as a Silver Bullet, just a very useful tool.

Agreed.

>For Ada I was thinking of virtual origins and conservative collectors,
>but I realise there are other algorithms. For C++ I think the only
>reasonable alternative is a conservative collector and figured the same
>was true for Ada.

Not at all -- a non-conservative GC is quite compatible with Ada.  Of
course, a non-conservative GC (in any language) requires a well-defined
interface between the compiler's generated code, and the GC.

>... OTOH I also disclaimed any expertise of Ada so perhaps
>my error can be forgiven?

Of course.  :-)

>No, I didn't claim that Boehms collector worked in Ada. I said it works
>nicely in C++ and it does! The Boehm GC is written for for C and C++
>where such techniques are forbidden. A pointer can be NULL, can point at
>or into an object or at the imaginary element directly after the last
>element of an array....

Ah, but nothing requires the compiler to represent a pointer to one of
those legal places as the address of that place.  A C or C++ compiler
could play games similar to the virtual origin trick, and then the Boehm
GC might not work.  In other words, the Boehm GC, or any other
conservative GC, depends on the lack of certain optimizations, which
makes me a bit uneasy.  In practise, maybe it's not such a big problem.

- Bob

Re: Garbage Collection in Ada

[Robert I. Eachus]

In article <dewar.845386292@merv> dewar@merv.cs.nyu.edu (Robert Dewar) writes:

  > I am a little dubious about mixing GC with full Ada 95 (e.g. GC and
  > unchecked conversion between integers and pointers are not friends),
  > but certainly GC with a slightly restricted Ada 95 semantics is perfectly
  > practical, and you can add me to the people who would like to see it (but
  > are not willing to sign a big check for it!)

   Adding support for a storage pool that supports GC would probably
be EXTREMELY low cost.  Doesn't GCC already use "fat" pointers under
some circumstances?  All that would be needed is a pragma that
indicates that a certain storage pool uses fat pointers.

   There may be some other way to do it, but I have never needed to
pay the price.  Much easier, when I need it, is to pass "handles" not
pointers, a sleight syntactic misfeature.  So don't add it on my
account.

   However, any Ada compiler that doesn't deallocate memory when you
call Unchecked_Deallocation is junk.  (Well, not really, which is why
the permission is there.  Any compiler that doesn't deallocation
memory that was allocated with `new' when you call....)

--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...

Re: Garbage Collection in Ada

[Robert Dewar]

Jon Anthony says

"A chicken or egg problem if there ever was one.  I certainly could use
GC in what I'm doing - I now have had to basically roll my own for the
particular application.  We don't have the $$ to actually fund such an
effort - say in GNAT by ACT.  Not alone that's for sure.  But I would
bet that there are quite a few such people out here who want it, but
can't fund such an effort alone.  I also know of many others that make
the claim that lack of GC is about the only thing that keeps them from
using Ada."

Many people claim many things. One thing to be careful of is that people
often justify not using Ada because Ada lacks xxx, and then rush off and
use some other language that lacks xxx.

In the case of GC, there are not many languages that in practice compete
with Ada that supply GC, so I doubt these claims. If and when Java becomes
a pratical vehicle for the kind of applications that might otherwise be
written in Ada, this situation may change, but I suspect the claim above
is valid.

In particular, our experience is often that people making such claims don't
even want to pay for *any* support, what they want is a version of GNAT they
can use free that has the feature they want. That's a perfectly reasonable
thing to want, but wanting does not make it so!

Clearly any Ada company will fund developments that it thinks might 
interest potential customers. So far, we don't buy the argument that
investing $x in implementing GC will increase our support income by
$x (not to mention more than $x), so it's not on our list of priorities.
There are many other items where we make the opposite judgment. Recent
examples are the production of a PCS for distributed applications, and
the full support of machine code insertions -- there are many others.

You have to remember here that I am an enthusiastic supporter of the notion
of garbage collection (see for example my paper in 1977 on an interesting
new garbage collection algorithm used in the Macro-SPITBOL compilers in
SOftware Practice and Experience). 

I am a little dubious about mixing GC with full Ada 95 (e.g. GC and
unchecked conversion between integers and pointers are not friends),
but certainly GC with a slightly restricted Ada 95 semantics is perfectly
practical, and you can add me to the people who would like to see it (but
are not willing to sign a big check for it!)

Robert Dewar

Re: Garbage Collection in Ada

[Hannes Haug]

bobduff@world.std.com (Robert A Duff) writes:

> is certainly true of off-the-shelf general-purpose allocators, but it's
> easy to write an allocator with predictable timing if the objects are
> all of the same size, and that's exactly what some real-time programs
> do.  And some real-time programs avoid using the heap at all, so of
> course GC is just a waste of implementer's time, for *those* programs.

like the off-the-shelf general-purpose allocators

> I know about Henry Baker's papers on real-time GC, but I remain somewhat
> skeptical.  (I suspect most real-time programmers have never heard of
> real-time GC, and would scoff at it.)

I think the commercial grand circle gc is quite similar to baker's
gc for ada. Paul wilson did some work on real-time gc, too.

 -hannes

Re: Garbage Collection in Ada

[Robert A Duff]

In article <19961015122319668722@dialup98-6-12.swipnet.se>,
Lars Farm <lars.farm@ite.mh.se> wrote:
>With GC the problem of "clean up" of memory is defined away. There is no
>way to be "sloppy" about deallocating memory with GC. There is no
>problem, pure and simple. That this is hard to accept is IMHO a clear
>indication that this really is a hard problem (without GC). 

It's hard to accept because it's not true.  ;-)

I've seen storage leaks in Lisp and Smalltalk programs.  All you have to
do is forget to nil-out a pointer to something that will never be used
again, and then the GC will not notice that this thing is really
garbage.

True example from a Smalltalk program: User can do something that pops
up a window on the screen, and later close it, getting rid of it.
However, there was a bug: there was a linked list of all windows, and
the system was failing to unlink windows from that list when they were
no longer needed.  After a day or two of using the system, it would run
out of memory.  That's a memory leak, and the GC didn't prevent it.

So, GC doesn't eliminate storage leaks -- it just eliminates *most*
storage leaks.  That's a good thing, but I think it's important to
remember that it's not perfect.

Conservative GC's are even worse -- it is possible to not free an object
even when there are no pointers to it, because the GC doesn't know the
difference between an integer and a pointer.

Note that the following is also possible:  Suppose I have a program with
explicit Free operations, with no storage leaks.  Suppose I erase all
the calls to Free, and insert a non-conservative GC.  It is quite
possible that the program will now leak storage.

>Sure, if a solution solves a majority of problems and leaves some to
>traditional techniques, is that not better than a solution that solves
>none?

Agreed.

- Bob

Re: Garbage Collection in Ada

[Hans-Juergen Boehm]

Robert Dewar wrote:

> The problem is that it is all too easy to have a global variable around
> that accidentally holds on to a giant structure. Or for example, depending
> on your implementation, taking the 'Access of one field of one record in
> some big structure may end up holding on to an entire subgraph that you
> do not need.
> 
> You may in practice need to be just as careful about adding
> 
>    Junk := null;
> 
> statements to your program as you are now about adding
> 
>    Free (Junk);
> 
> statements to your program now.
> 
> GC is certainly a magic bullet solution to the problem of accidentally
> freeing storage that should not be freed, but it is NOT a magic bullet
> with respect to not freeing things that should be freed. People who
> approach a GC language environment with this expectation will be
> disappointed!

That's certainly all true.  But it's important to remember that there
are 2 important differences between inserting 

Junk := null;

and

Free (Junk);

1.  The first asserts only that the pointer Junk is no longer needed.
It makes no claims about any other uses of the object referenced by
Junk.  If another thread is still accessing it through another variable
that's fine.  In the second you may well get a very hard-to-debug memory
smash in another module.  Free asserts there are no other uses of the
referenced object, a much stronger assertion that generally requires
much more global knowledge.  Clearing variables rarely requires
additional complexity in intrfaces.  Fully manual memory management
often does, since you need to talk about ownership etc.

2.  If Junk is really a global variable, then not clearing it usually
introduces a BOUNDED leak.  The memory will only be retained until the
next assignement to Junk.  Forgetting the Free in an uncollected system
is much more disastrous.  (There are cases in which not clearing a
variable introduces an unbounded leak.  But they're much less common.)

-- 
Hans-Juergen Boehm
boehm@mti.sgi.com

Re: Garbage Collection in Ada

[Keith Thompson]

It occurs to me that we may be approaching the whole question of garbage
collection in Ada from the wrong direction.

I think we've established the following:

1. The Ada language definition allows but does not require GC.  In fact,
   the designers of the language went to considerable pains to make sure
   that it does allow GC, even to the point of having a language-defined
   pragma to control it (pragma Controlled).

2. Implementing GC in Ada would be a substantial amount of work, but it's
   by no means impossible.

3. Few, if any, Ada vendors have actually implemented GC simply because
   few, if any, paying customers have asked for it.  It simply hasn't
   been a high priority.

Nevertheless, there's been a great deal of discussion here and
elsewhere to the effect that GC is A Good Thing.  Several other language
implementations provide GC, and many of their users don't know how they
could get along without it.

Maybe the real problem is that there's a market out there that we aren't
reaching.

-- 
Keith Thompson (The_Other_Keith) kst@thomsoft.com <*>
TeleSoft^H^H^H^H^H^H^H^H Alsys^H^H^H^H^H Thomson Software Products
10251 Vista Sorrento Parkway, Suite 300, San Diego, CA, USA, 92121-2706
FIJAGDWOL

Re: Garbage Collection in Ada

[Robert Dewar]

"   Adding support for a storage pool that supports GC would probably
be EXTREMELY low cost.  Doesn't GCC already use "fat" pointers under
some circumstances?  All that would be needed is a pragma that
indicates that a certain storage pool uses fat pointers.
"


I am not sure what your shouted EXTREMELY is about here. We have looked into
this partial solution, and it is not at all easy to implement for all sorts
of reasons, remember that you have to identify the roots. So that seems to
mean that the pointers must be controlled, but even so, there are many
details to this. Cyrille Comar has looked at these issues in detail, and if
it was EXTREMELY easy to implement, it would have been done a long time ago!

Re: Garbage Collection in Ada

[Hans-Juergen Boehm]

Robert A Duff wrote:

> To me, this sounds backwards.  Virtual origins are a useful
> optimization, and if they break your GC, then your GC is broken.  It's
> not the compiler's fault.  It's certainly possible to implement a GC
> that works in the presence of this optimization.  And there are many
> other examples of optimizations that will break the typical
> "conservative" GC, but a proper non-conservative GC can work properly.
> The term "conservative" is bogus, IMHO, since if you do certain things
> in your code, or your friendly compiler-writer does certain
> optimizations, it makes the GC *liberal* -- that is, frees in-use data.

I think it's important to distinguish 2 kinds of "conservative" garbage
collection:

1. A garbage collector that doesn't have perfect pointer identification
information, but can identify a superset of the valid pointers.  In the
long run this is the only kind of conservative GC that makes sense.  Our
collector can be used in this way with some C compilers (e.g. lcc, gcc
with the preprocessor from my PLDI 96 paper, most compilers in debugging
mode).  Assuming minimal and mostly checkable restrictions on the input,
this cannot result in freeing of in-use data.  (Note that the GC-unsafe
use of virtual origins in C SOURCE code is a BUG according to the ANSI C
standard.  See my PLDI 96 paper or the standard for details.)  There are
sometimes performance reasons for using such an approach even when exact
pointer-identification information could be made available.

2. Use of the same collector as above with a compiler that does not
ensure that pointers are maintained in recognizable form at run-time.
This is a hack that happens to work 99.99% of the time, and happens to
be useful at present.  The strongest correctness argument one can make
is that at present it appears to be at least as reliable as as many
compiler optimizers themselves.  The downside is that it works well
enough that there is little incentive for more GC-friendly optimizers.

> Avoiding certain things in my code is tolerable, but it makes me nervous
> to think that the new version of a compiler, with a smarter optimizer,
> might come along and break the conservative GC.

In the past "smarter" optimizers have often broken the ANSI-conforming
parts of our collector, too.  (These were not released SGI compilers.
Some of the were released "production" compilers from other vendors.)


-- 
Standard disclaimer ...
Hans-Juergen Boehm
boehm@mti.sgi.com

Re: Garbage Collection in Ada

[Lars Farm]

Robert Dewar <dewar@merv.cs.nyu.edu> wrote:

> Hmmm! I am surprised anyone would write this if they 
> had used GC languages.
...
> You may in practice need to be just as careful about adding
>
>   Junk := null;

Further down in the same post I also said: "if a solution solves a
majority of problems and leaves some to traditional techniques, is that
not better than a solution that solves none?" 

Granted, p = null; is different from Free(p); but the effect and intent
is the same and Free() is a traditional technique. There are also other
cases when one has to interfere.

In other posts to this thread I have said: "I don't think of GC as a
Silver Bullet, just a very useful tool." and "GC does one thing, one
thing only and does it very well."

> People who approach a GC language environment with
> this expectation will be disappointed!

I don't. This is Usenet, not an academic thesis. The wording doesn't get
much time and polish. If that offends you, I apologize. If you find that
surprising, then we have failed to communicate and I'm sorry.

I trust that you are able to interpret what I said, should you want to.


-- 
Lars Farm, lars.farm@ite.mh.se

Re: Garbage Collection in Ada

[Hans-Juergen Boehm]

Robert Dewar wrote:

> Personally, although these kind of conservative collectors are a partial
> solution useful in some circumstances, I don't find them acceptable for
> serious solution of the GC problem. If you count on  a conservative
> collector to free storage, you have a very unreliable program, since
> you could find on some particular run that you were just unlucky and
> a junk integer value held a critical large block in memory, causing
> the program to crash and burn.
> 
> If you don't mind a program with this kind of unreliability, then this
> approach may work, but for me, the only really viable approach, and the
> only one worth putting real effort into in the Ada context is a proper
> full GC that know what is a pointer and what is not.
> 

Let's compare the options here:

1. Traditional manual memory management
- No guarantees about space usage, since the language definition makes
  no guarantees.
- Space usage may be unexpectedly large on certain inputs due to
  fragmentation effects.  The worst-case space usage of any general
  purpose allocator is at least N logN, where N is the amount of live
  heap data.  If this occurred in practice, the customer would probably
  be unhappy.  And many commonly used allocators have much worse
  worst-case performance than that.

2. Conservative garbage collection
- No guarantees about space usage, since the language definition makes
  no guarantees.
- Space usage may be unexpectedly large on certain inputs due to
  fragmentation effects or due to misidentified pointers.

3. Nonconservative garbage collection
- No guarantees about space usage, since the language definition makes
  no guarantees.
- If you use a compacting collector, you can bound heap size to a
  constant factor times live data size (which is not true for
  either of the above), but you'll pay for it in other ways.

Thus I would claim that if you really need hard space bounds your
options are severely limited (e.g. no general purpose dynamic memory
allocation or perhaps a compacting collector + platform specific tools
to bound stack use, etc.)



-- 
Standard disclaimer ...
Hans-Juergen Boehm
boehm@mti.sgi.com

Re: Garbage Collection in Ada

[Lars Farm]

Robert Dewar <dewar@merv.cs.nyu.edu> wrote:

> Well if your requirements here are so weak that you find that these
> kind of conservative GC's are acceptable, then what's your problem, 

"works" is not sufficient. Among C++ people the first reaction to GC
usually is: -"impossible" for one technical reason or other. Not unlike
what I experienced here. In practice it works. Unused memory is
reclaimed and reused, heapsize will not grow and it is fast. It works.
Currently this has to be qualified with "Using compiler A, version B and
library C version D" and that is a problem.

With standard sanction the potential problems you and others (optimizer
tricks that might trip off the collector) would also be under control.
If there is GC it is controlled by the same people that control the
optimizer. With sanctioned GC there would be restrictions on what
optimizer tricks would be allowed.

To be useful in a world (C++/Ada) where GC is optional one needs *some*
language support. At least enough to portably determine if GC is
available at compiletime. A progam designed for GC should not compile on
a compiler that doesn't support GC. C++ (currently) fails here, how
about Ada?

Also, using GC would be "allright" if it was part of the language, even
if optional.


-- 
Lars Farm, lars.farm@ite.mh.se

Re: Garbage Collection in Ada

[Jon S Anthony]

In article <dewar.845386292@merv> dewar@merv.cs.nyu.edu (Robert Dewar) writes:

> Many people claim many things. One thing to be careful of is that people
> often justify not using Ada because Ada lacks xxx, and then rush off and
> use some other language that lacks xxx.

Yes, that's certainly true.  But of the cases I have in mind that is
not true.


> In the case of GC, there are not many languages that in practice compete
> with Ada that supply GC, so I doubt these claims. If and when Java becomes
> a pratical vehicle for the kind of applications that might otherwise be
> written in Ada, this situation may change, but I suspect the claim above
> is valid.

Depends on what you mean by "compete".  Does Eiffel?  Does SmallTalk?
Probably.  But they are not the big market either (though SmallTalk
may be getting there...)  OTOH, if you wait for Java to take the lead,
then there is no reason to believe that any good will come of this for
Ada users.


> In particular, our experience is often that people making such claims don't
> even want to pay for *any* support, what they want is a version of GNAT they
> can use free that has the feature they want. That's a perfectly reasonable
> thing to want, but wanting does not make it so!

You're not actually suggesting that I'm not paying, are you????!!  I
can give you my customer # if you are...


> Clearly any Ada company will fund developments that it thinks might 
> interest potential customers. So far, we don't buy the argument that
> investing $x in implementing GC will increase our support income by
> $x (not to mention more than $x), so it's not on our list of priorities.

Fair enough.  But then, I find it hard to believe that implmementing
all the annexes had that level of payback either.  Except for the fact
that you can claim to fully support the entire RM (another good reason
why GC annex may have been nice :-).  Think about it, for example, the
DSA is a fine and wonderful thing but I can get everything it offers
in commercially available CORBA based ORBs supporting Ada95.  Not so a
GC...)


> You have to remember here that I am an enthusiastic supporter of the notion
> of garbage collection (see for example my paper in 1977 on an interesting
> new garbage collection algorithm used in the Macro-SPITBOL compilers in
> SOftware Practice and Experience). 

Yes, I believe this entirely.


> I am a little dubious about mixing GC with full Ada 95 (e.g. GC and
> unchecked conversion between integers and pointers are not friends),

Agreed, but these sorts of things could be requirements on when GC is
available.  Just like the various requirements for other special needs
aspects.


> but certainly GC with a slightly restricted Ada 95 semantics is perfectly
> practical, and you can add me to the people who would like to see it (but
> are not willing to sign a big check for it!)

I hear ya!  I wonder if there is enough _small_ folk out there who
_together_ could fund such an effort?  What sort of $$ are we talking
about?

/Jon
-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com

Re: Garbage Collection in Ada

[Robert Dewar]

"Yes, but is this really a problem? What you really want to avoid is
the program gobbling up ever-increasing amounts of memory over
time. If you have global variables around pointing to objects, it is
possibly just because you need to avoid egtting your structure
deallocated! When I learned Simula after having programmed in Fortran
for some time, it took some time to adjust to the new environment, but
I experienced GC as a clear advantage. But then I didn't do real-time
systems in Simula...."


Absolutely, it is definitely a problem. I have seen it in my own code, and
in the code of many SPITBOL users. A typical problem is that you are 
accumulating stuff because for example you main a cross-reference list, 
and you don't need to reference dead stuff any more, but you forget
that this list is still holding on to it. 

\

Re: Garbage Collection in Ada

[Jon S Anthony]

In article <Pine.GSO.3.93.961014050707.23547A-100000@sky.net> John Howard <jhoward@sky.net> writes:

> GC just provides *automatic* deallocation of "unreachable" dynamically
> allocated objects.  GC is not cost-free.  Ada 95 flexibly provides a
> programmer with capable mechanisms to manually manage memory.  Plus the

In many cases these are not really sufficient without herculian
efforts.  I've been there.


> safeguards of Ada help minimize creating slop to clean up and so the
> deallocation can likely be managed easily enough manually.  I am not 
> against using GC if its reliability is guaranteed and it saves me some 
> money.  Otherwise I prefer to manually control the deallocation.

Fine.  Then just don't use it.


> You argue that GC is already worthwhile for the culture of C++ 
> programming.  Perhaps it is most cost-effective if an operating system
> does GC instead of having several programs doing their own GC.  That seems
> to be a goal of the Java Virtual Machine.

A worthy goal.  But not something any viable OS is going to provide
anytime soon.

> > Lars Farm, lars.farm@ite.mh.se:
> > Ada allows GC, C++ doesn't even acknowledge its existence.  One would
> > have thought that the stricter Ada would be easier to adapt to GC than
> > the "sloppy" C++.

Lars, what on Earth (or anywhere else) makes you think otherwise??


> I argue that GC is far less worthwhile for the culture of Ada programming.
> (Similarly Ada spared us from needing an equivalent C Lint program to 
> clean up code).

Come on.  While it is less useful in several cases, it is still
extremely useful in many typical cases.  Unless you so narrowly define
Ada programming as to exclued all those application areas.  I sure
don't want to do this.


/Jon
-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com

Re: Garbage Collection in Ada

[Jon S Anthony]

In article <19961014115513529729@dialup105-2-16.swipnet.se> lars.farm@ite.mh.se (Lars Farm) writes:

> Fortunately it is very easy to get GC in C++ if one is willing to
> sacrifice portability. All it takes is to link Boehms allocator and it
> works beautifully without any other changes. In spite of its
> unportability label it works on a large number of operating systems and
> on many different development systems, right off the net. Is using a
> good GC that simple in Ada dev systems too?

Well, using the Boehm collector should be.  But, while I am pro-GC in
Ada, I am not a fan of the use of a conservative collector for Ada.
I'm not convinced it would be worth it.

/Jon
-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com

Re: Garbage Collection in Ada

[Jon S Anthony]

In article <DzAuKH.82J@thomsoft.com> kst@thomsoft.com (Keith Thompson) writes:

> It occurs to me that we may be approaching the whole question of garbage
> collection in Ada from the wrong direction.
> 
> I think we've established the following:
> 
> 1. The Ada language definition allows but does not require GC.  In fact,
>    the designers of the language went to considerable pains to make sure
>    that it does allow GC, even to the point of having a language-defined
>    pragma to control it (pragma Controlled).
> 
> 2. Implementing GC in Ada would be a substantial amount of work, but it's
>    by no means impossible.
> 
> 3. Few, if any, Ada vendors have actually implemented GC simply because
>    few, if any, paying customers have asked for it.  It simply hasn't
>    been a high priority.
> 
> Nevertheless, there's been a great deal of discussion here and
> elsewhere to the effect that GC is A Good Thing.  Several other language
> implementations provide GC, and many of their users don't know how they
> could get along without it.
> 
> Maybe the real problem is that there's a market out there that we aren't
> reaching.

You have hit the nail on the head, IMO.

/Jon
-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com

Re: Garbage Collection in Ada

[Robert Dewar]

Hans-Juergen said

"1. Traditional manual memory management
- No guarantees about space usage, since the language definition makes
  no guarantees.
- Space usage may be unexpectedly large on certain inputs due to
  fragmentation effects.  The worst-case space usage of any general
  purpose allocator is at least N logN, where N is the amount of live
  heap data.  If this occurred in practice, the customer would probably
  be unhappy.  And many commonly used allocators have much worse
  worst-case performance than that.
"

No, there are general purpose allocators with much better performance. 
Just consider a simple binary allocator, at worst you waste half the
space, i.e. a factor of 2. But perhaps I don't understand your point.

Also, there are many programs which use storage only of a certain
limited range of sizes, and it is quite easy to make general purpose
allocators that handle this situation MUCH more efficiently. In the
limiting case consider the case where a program uses ONLY blocks
of a fixed size. You have zero fragmentation there, but a conservative
GC can still hold on to an arbitrary number of blocks, so you cannot
put a bound on the effective overuse of storage.

It is quite easy to bound the fragmentation effect for a given
application. It is almost impossible to bound the accidental
holding-onto-storage effect of a conservative allocator, since
for example, the particular floating-point values in use can
result in holding onto storage one day, and not the next day,
depending on where your program loads in memory.

Finally, there is one disadvantage of a conservative collector
that you did not mention, namely the possibility that it will
unexpectedly collect blocks that are in use. This can result
from either compiler optimizations, or code that cheats with
poitners (code which may exist in practice, and which in
particular typically exists in the conservative allocator
itself!

Re: Garbage Collection in Ada

[Robert Dewar]

Lars says

"
With standard sanction the potential problems you and others (optimizer
tricks that might trip off the collector) would also be under control.
If there is GC it is controlled by the same people that control the
optimizer. With sanctioned GC there would be restrictions on what
optimizer tricks would be allowed.
"


No, you are confused, if a language expects GC, and if a proper GC is
incorporated, there is no respect in which the presence of GC inhibits
optimizations. Where did you get this idea?

It is true that a conservative collector depends on assuming the absence of
no optimization, but there is no way that a language definition could
somehow "sanction" a conservative collector.

At best it could say something like "An implementation is free to remove
blocks  from memory that cannot be further referenced", but that does not
say no use of virtual origins.

You can't have something in a language standard that says "the implementation
must work correctly with a conservative collector that works as follows" !

At least I *trust* that no one would suggest such a statement in a language
standard, but really I know better, people suggest all sorts of incredible
things.

Re: Garbage Collection in Ada

[Hans-Juergen Boehm]

Robert Dewar wrote:
> 

> No, there are general purpose allocators with much better performance.
> Just consider a simple binary allocator, at worst you waste half the
> space, i.e. a factor of 2. But perhaps I don't understand your point.
> 
N log K, where N is the size of live data and K is the size ratio
between largest and smallest bound is the best worst-case bound
acheivable by a general purpose nonmoving allocator.  This is an old
result due to Robson, cited in Knuth  (I don't have the reference
handy).  This means a binary buddy system without
coalescing is asymptotically optimal for the worst case.  It does poorly
if your program allocates 1MB of 5 byte objects, deallocates them, then
allocates 1MB of 9 byte objects, deallocates them, allocates 17 byte
objects, etc.  (It's also less space efficient in the typical case
tah other algorithms with worse worst-case behavior.)

> Also, there are many programs which use storage only of a certain
> limited range of sizes, and it is quite easy to make general purpose
> allocators that handle this situation MUCH more efficiently.
Yes, to a point.  But many of them do not.  The language spec gives me
no guarantees.  And most allocator implementations don't even bother
to document such behaviour.  And most of my programs allocate a wide
variety of sizes.

> In the
> limiting case consider the case where a program uses ONLY blocks
> of a fixed size. You have zero fragmentation there, but a conservative
> GC can still hold on to an arbitrary number of blocks, so you cannot
> put a bound on the effective overuse of storage.
Yes, but my programs don't behave that way.
> 
> It is quite easy to bound the fragmentation effect for a given
> application.
Only if I understand the allocator.  For some commonly used allocators
it's not clear anyone understands it well enough.
> It is almost impossible to bound the accidental
> holding-onto-storage effect of a conservative allocator, since
> for example, the particular floating-point values in use can
> result in holding onto storage one day, and not the next day,
> depending on where your program loads in memory.
But there are techniques that can bound the impact of such accidental
retention by ensuring that such a value causes at most a fixed, one-time
leak.
> 
> Finally, there is one disadvantage of a conservative collector
> that you did not mention, namely the possibility that it will
> unexpectedly collect blocks that are in use. This can result
> from either compiler optimizations, or code that cheats with
> poitners (code which may exist in practice, and which in
> particular typically exists in the conservative allocator
> itself!

I addressed this in an earlier message that may have been lost.
It is easy to define a minimally restricted subset of even C for
which this can't happen with the right compiler (e.g. lcc or gcc
with a suitable preprocessor).  Details are in my PLDI 96 paper.

(See http://reality.sgi.com/employees/boehm_mti/papers/pldi96.ps.gz)

Standard disclaimer ...
Hans-Juergen Boehm
boehm@mti.sgi.com

Re: Garbage Collection in Ada

[Hans-Juergen Boehm]

Robert Dewar wrote:
> 
> No, you are confused, if a language expects GC, and if a proper GC is
> incorporated, there is no respect in which the presence of GC inhibits
> optimizations. Where did you get this idea?

For systems I've seen it does inhibit some optimizations, ar least to
the extent that proper use of a conservative collector inhibits
optimizations.  Especially in multithreaded systems, there must be a
recognizable pointer to every accessible object at every program point
at which a GC might occur.  Often this is between every pair of
instructions.  In a nonconservative system you could generate
arbitrarily complex tables to allow reconstruction of those pointers.
But in practice this seems to be limited by engineering considerations
and table size.  This effect is minor (perhaps a few percent, see
e.g. my PLDI 96 paper), but it's not completely negligible.  (Of
course write-barriers and especially read-barriers can have a
moresubstantial effect on the generated code, if they're needed.)
> 
> It is true that a conservative collector depends on assuming the absence of
> no optimization, but there is no way that a language definition could
> somehow "sanction" a conservative collector.
> 
It could require the existence of a collector, and a (partially)
conservative collector may well be the most viable implementation
strategy.


-- 
Standard disclaimer ...
Hans-Juergen Boehm
boehm@mti.sgi.com

Re: Garbage Collection in Ada

[Ole-Hjalmar Kristensen FOU.TD/DELAB]

In article <dewar.845388021@merv> dewar@merv.cs.nyu.edu (Robert Dewar) writes:

   Lines: 40
   References: <01bbb910$f1e73f60$829d6482@joy.ericsson.se> <199610132138291604607@dialup101-6-14.swipnet.se> <Pine.GSO.3.93.961014050707.23547A-100000@sky.net> <19961015122319668722@dialup98-6-12.swipnet.se>
   NNTP-Posting-Host: merv.cs.nyu.edu
   X-Newsreader: NN version 6.5.0 (NOV)

   Lars said

   "With GC the problem of "clean up" of memory is defined away. There is no
   way to be "sloppy" about deallocating memory with GC. There is no
   problem, pure and simple. That this is hard to accept is IMHO a clear
   indication that this really is a hard problem (without GC). We are so
   afraid of memory leaks that we find it very hard to accept an automatic
   solution. Note: this doesn't mean that GC solves every conceivable
   memory related problem, but knowing when to release memory is solved so
   the result is not "slop to clean up"."


   Hmmm! I am surprised anyone would write this if they had used GC languages.
   The problem of cleanup is not define away at all, and indeed, in some
   respects can be trickier, because you don't think about it up front as you
   have to in a system where you use finalization for freeing things, or even
   more manual techniques.

   The problem is that it is all too easy to have a global variable around
   that accidentally holds on to a giant structure. Or for example, depending
   on your implementation, taking the 'Access of one field of one record in
   some big structure may end up holding on to an entire subgraph that you
   do not need.

Yes, but is this really a problem? What you really want to avoid is
the program gobbling up ever-increasing amounts of memory over
time. If you have global variables around pointing to objects, it is
possibly just because you need to avoid egtting your structure
deallocated! When I learned Simula after having programmed in Fortran
for some time, it took some time to adjust to the new environment, but
I experienced GC as a clear advantage. But then I didn't do real-time
systems in Simula....

   You may in practice need to be just as careful about adding

      Junk := null;

   statements to your program as you are now about adding

      Free (Junk);

   statements to your program now. 

Yes, if you have the habit of using lots of global variables,
otherwise it will be deallocated some time after the variable goes out of
scope. (As I am 100 percent sure that you know)

   GC is certainly a magic bullet solution to the problem of accidentally
   freeing storage that should not be freed, but it is NOT a magic bullet
   with respect to not freeing things that should be freed. People who 
   approach a GC language environment with this expectation will be
   disappointed!

In theory you are right, but it is strange I have never heard
complaints about this problem from the Lisp hackers next door.

Re: Garbage Collection in Ada

[Lars Farm]

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

> Ah, but nothing requires the compiler to represent a pointer to one of
> those legal places as the address of that place.  A C or C++ compiler
> could play games similar to the virtual origin trick, and then the Boehm
> GC might not work.

There is the "as if" rule. As long as the program behaves "as if" the
pointer requirements are met, such an optimization is probably ok. That
is, as long as no program can detect that it's there. A conservative
collector might detect that and report its findings through a premature
reuse of memory so it's not allowed;-) OTOH a conservative collector
(written in C or C++) must play games with pointers that are in
principle unportable too to detect the optimizer-bug so some might
perhaps say that this doesn't count.


-- 
Lars Farm, lars.farm@ite.mh.se

Re: Garbage Collection in Ada

[whiting_ms@corning.com (Matt Whiting)]

In article <EACHUS.96Oct15143310@spectre.mitre.org>, eachus@spectre.mitre.org (Robert I. Eachus) writes:
> 
>    Adding support for a storage pool that supports GC would probably
> be EXTREMELY low cost.  Doesn't GCC already use "fat" pointers under
> some circumstances?  All that would be needed is a pragma that
> indicates that a certain storage pool uses fat pointers.

Time to admit my ignorance (and hopefully remove it!).  What is a "fat"
pointer?  From the context, sounds like it might be a data structure that not
only references memory, but also provides the size of the memory being
reference (kind of like a VMS descriptor, if memory serves).

Matt

Re: Garbage Collection in Ada

[Robert Dewar]

Lars said

"There is the "as if" rule. As long as the program behaves "as if" the
pointer requirements are met, such an optimization is probably ok. That
is, as long as no program can detect that it's there. A conservative
collector might detect that and report its findings through a premature
reuse of memory so it's not allowed;-) OTOH a conservative collector
(written in C or C++) must play games with pointers that are in
principle unportable too to detect the optimizer-bug so some might
perhaps say that this doesn't count."


Such optimization is definitely OK, the fact that incorrect programs,
such as any conservative collector, can detect that the optimization
is in place is irrelevant, and it is not just that "some may say this",
it is absolutely clear.

You can't have it both ways. Either you think in terms of the C that people
actually write, that in practice works even if the standard does not
sanction it. This is the kind of semantics required to write a conservative
collector.

OR

You are a strict ANSI C person who will not tolerate such code.

In the first case, user code can then play games no worse than your
conservative collector and defeat it.

In the second case, the conservative collector itself violates the rules.

In practice, you can get along with the conservative collector pretty well.
In practice it works even though it violates the rules
In practice, user code does not happen to do things that defeat it
  (though please for example do not try to use the Boehm collector
    with the gigi code in GNAT, it will likely not work, although
    actually I think it is probably OK, even though this code uses
    virtual origins, I think the "real" pointers are still around.

Re: Garbage Collection in Ada

[Robert Dewar]

Lars says

"I doubt that I will get proper sanction for GC in a language spec.
Fortunately it is very easy to get GC in C++ if one is willing to
sacrifice portability. All it takes is to link Boehms allocator and it
works beautifully without any other changes."

Well if your requirements here are so weak that you find that these
kind of conservative GC's are acceptable, then what's your problem, 
the same approach will work in typical Ada compilers as well as it
does in typical C compilers (probably better, because it is far harder
to play games at the user level with pointers in Ada than in C or C++)

If you have somehow got the impression that this is not the case, and
that Ada is somehow hjarder to deal with in this repsect than C or C++,
you have confused yourself or misinterpreted something that has been said.

Personally, although these kind of conservative collectors are a partial
solution useful in some circumstances, I don't find them acceptable for
serious solution of the GC problem. If you count on  a conservative
collector to free storage, you have a very unreliable program, since 
you could find on some particular run that you were just unlucky and
a junk integer value held a critical large block in memory, causing
the program to crash and burn. 

If you don't mind a program with this kind of unreliability, then this
approach may work, but for me, the only really viable approach, and the
only one worth putting real effort into in the Ada context is a proper
full GC that know what is a pointer and what is not.

I don't like the confusion between these two techniqes, they are very
different.
n

Re: Garbage Collection in Ada

[Robert Dewar]

Matt said

"Time to admit my ignorance (and hopefully remove it!).  What is a "fat"
pointer?  From the context, sounds like it might be a data structure that not
only references memory, but also provides the size of the memory being
reference (kind of like a VMS descriptor, if memory serves)."


Well I would not call it ignorance, since this is certainly not a recognized
technical term. In fact I can't even remember if GNAT invented it or not,
I suspect we did.

We use it simply to mean, as you say, a pointer with other information.
For example, in GNAT, the default (but overridable) form of pointers to
unconstrained arrays is a structure with two pointers, one to the data
(which could be, but is not yet, a virtual origin), and one a pointer
to a record containing the array bounds.

Re: Garbage Collection in Ada

[Rick Hudson]

bobduff@world.std.com (Robert A Duff) writes:
> 
> In article <3265BD97.41C6@mti.sgi.com>,
> Hans-Juergen Boehm  <boehm@mti.sgi.com> wrote:
> >For systems I've seen it does inhibit some optimizations, ar least to
> >the extent that proper use of a conservative collector inhibits
> >optimizations.  Especially in multithreaded systems, there must be a
> >recognizable pointer to every accessible object at every program point
> >at which a GC might occur.  Often this is between every pair of
> >instructions.  In a nonconservative system you could generate
> >arbitrarily complex tables to allow reconstruction of those pointers.

You could but you don't have to. If GC is triggered only by an allocate then
one could roll forward the threads to a 'gc' point. This greatly reduces the
amount of table information needed.

> 
> I would think it would be simpler and more efficient to represent this
> information as executable code.  That is, the compiler generates a
> procedure for each type, and for each stack frame, that knows how to
> find all the pointers.  It could take the PC as a parameter, so it could
> deal with optimizations where, for example, register R1 contains a
> pointer sometimes, and an integer other times.

We thought about this when we hacked the gcc backend to do accurate GC (see
Diwan, Moss, Hudson PLDI '92.) Our feeling at the time was that the table size
would be a lot smaller than the code size and the chances of being clever and
reducing table size was high, we didn't have that confidence about the code
route. In any case, if you count the 'out of cache' memory fetches, both code
and data, the tables won since with tables your code is in the cache.

> 
> >But in practice this seems to be limited by engineering considerations
> >and table size.
> 
> I agree.  (Except I'd say engineering considerations and code size.)
> 
> Another effect might be that in a GC'ed environment, an optimizer might
> cause objects to be reachable for longer than they should be.
> Alternatively, the compiler might try to insert "X := null" in order to
> allow garbage to be collected earlier.  Probably these are minor
> effects, but there *is* some interaction between an optimizer and a
> (nonconservative) gc.
> 
> >It could require the existence of a collector, and a (partially)
> >conservative collector may well be the most viable implementation
> >strategy.
> 
> Well, you can write "The implementation shall do garbage collection." in
> a language definition, and this statement might have the desired effect
> on compiler writers, but I don't know what it means in any *formal*
> sense.
> 
> Anyway, I don't understand why you would want a conservative collector,
> unless you're dealing with an uncooperative language/compiler (like C).
> If the language "requires" gc, then there's every opportunity to have a
> well-defined interface between generated code and gc, so why be
> conservative?

Interoperability with C is the big win for conservative collectors.

> 
> By the way, has anybody tried Boehm's conservative GC with GNAT?  If it
> works for gcc, it ought to work for GNAT, I would think.
> 
> - Bob

- Rick Hudson

Re: Garbage Collection in Ada

[Hans-Juergen Boehm]

Rick Hudson wrote:
> 
> bobduff@world.std.com (Robert A Duff) writes:
> >
> > In article <3265BD97.41C6@mti.sgi.com>,
> > Hans-Juergen Boehm  <boehm@mti.sgi.com> wrote:
> > >For systems I've seen it does inhibit some optimizations, ar least to
> > >the extent that proper use of a conservative collector inhibits
> > >optimizations.  Especially in multithreaded systems, there must be a
> > >recognizable pointer to every accessible object at every program point
> > >at which a GC might occur.  Often this is between every pair of
> > >instructions.  In a nonconservative system you could generate
> > >arbitrarily complex tables to allow reconstruction of those pointers.
> 
> You could but you don't have to. If GC is triggered only by an allocate then
> one could roll forward the threads to a 'gc' point. This greatly reduces the
> amount of table information needed.
> 

This works well if you can reliably and reasonably quickly advance
threads to the next GC point without forcing them to execute code at the
GC point when they don't need to stop.  In some systems that's easy.  In
some that's hard.  The thread systems I've used can't easily do that.

-- 
Hans-Juergen Boehm
boehm@mti.sgi.com

Re: Garbage Collection in Ada

[Hans-Juergen Boehm]

Robert Dewar wrote:
> 
> The essence of the binary storage allocator is that it DOES coalesce
> on return, and that for a given maximum block size, the time to coalesce
> is bounded by a constant, as is the time to allocate.
I believe the version with full coalescing has worst-case allocation
time log N, where N is the heap size.  Consider a heap with only one
large empty block and repeated requests to alternately allocate and
deallocate a 1 byte block.  (I'm referring to the algorithm in Knuth,
vol. 1, 2nd edition, starting at page 442.  Knuth credits it to
Markowitz and Knowlton.)

I mentioned the algorithm without coalescing, since it seems to be
commonly implemented.  Allocation and deallocation is a bit faster, and
worst-case space usage is only worse by a constant (see below).

> And in such a system
> it is obvious that you cannot be worse than a factor of 2 inefficient
> in use of storage (the worst case occcurs if all your allocations are for
> one size of block, that is a power of 2 plus one in size).

You can do considerably worse than that.  Consider allocating size 1MB
os size 1 blocks.  Deallocate most of them, so that only ever 16th
remains.  Repeat with size 16 blocks.  They will need to go into a new
region of memory.  Leave every 16th.  Repeat with sizes 256, 4096 and
64K.  At most 1.25MB were live at any point.  But 5MB were needed.  This
is in addition to the factor of 2 you get with non-power-of 2 sizes.  So
we have something like a factor of 8.  And this isn't quite the worst
case.  See also exercise 41 on page 455 in Knuth V. 1.

Knuth states (Vol 1, 2nd ed., bottom of page 451):

"J.M. Robson has shown [JACM 18 (1971), pp. 416-423] that dynamic
storage allocation strategies that never reallocate reserved blocks
cannot possibly be guaranteed to use memory efficiently; there will
always be pathological circumstances in which the method breaks down."

He gives details and bounds in the exercises.

-- 
Hans-Juergen Boehm
boehm@mti.sgi.com

Re: Garbage Collection in Ada

[Richard Kenner]

In article <dewar.845559320@merv> dewar@merv.cs.nyu.edu (Robert Dewar) writes:
>We follow the GCC model of trampolines (remember that GNU-C already has
>nested procedures, using a static chain). The trampoline is a small bit
>of code in the stack frame that loads the right static link and jumps
>to the right place.

I should add to this that not all systems need a trampoline.  For example,
on some systems (e.g., Alpha/VMS and RS/6000) a pointer to a function is
actually a pointer to a descriptor for the function.  This discriptor
contains space for a static chain.  On those systems, what gets put
on the stack and pointed to is a copy of the descriptor, not executable code.

Re: Garbage Collection in Ada

[Hans-Juergen Boehm]

Robert Dewar wrote:
> 
> HJB says
> 
> "It could require the existence of a collector, and a (partially)
> conservative collector may well be the most viable implementation
> strategy."
> 
> What would it mean to sanction the existence of a collector. As I noted
> earlier, at most it could mean that you provide for the possibility of
> unreachable blocks disappearing, but there are several problems here:
> 
> 1. Since you only *allow* such collection, completely ignoring the requirement
> is a valid semantic interpretation.
> 
> 2. Since you can only collect unreachable blocks, the removal of them has
> null semantics in any case, unless you allow finalization to happen at
> unpredictable points, a nasty thought!
> 
> 3. You cannot require blocks to disappear, since if you have conservative
> collectors in mind they do not guarantee to free even a single block in
> a given program.
> 
> Conservative collectors are a clever idea, and are a clever response to
> dealing with wanting GC in an implementation that does not otherwise
> provide GC, but I don't see that the concept has any relevance in language
> design.

This is an interesting issue.  Language specs generally do not say
anything specific about space usage.  Hence you can't formally define
what it means to have a garbage collector (except possibly for
asynchronous finalization, which is a different issue).  This is
independent of whether you have a conservative or traditional collector
in mind.  Nonetheless, I think language specs should contain informal
statements about whether GC is expected, since you can't reasonably
program without such an understanding.

The use of a conservative versus traditional collector is mainly an
implementation, and not a language design issue.  It does have some
minimal impact, since it makes it possible to garbage collect a language
with C style unions and an address-of operator as in C.  I don't know of
any other feasible techniques.

-- 
Hans-Juergen Boehm
boehm@mti.sgi.com

Re: Garbage Collection in Ada

[John Howard]

On 15 Oct 1996, R.I.E. wrote:
>    Adding support for a storage pool that supports GC would probably
> be EXTREMELY low cost.  Doesn't GCC already use "fat" pointers under
> some circumstances?  All that would be needed is a pragma that
> indicates that a certain storage pool uses fat pointers.
[snip]

pragma Cess_Pool(storage_pool_type) ;)
[Sorry about the stupid pun but it seems almost appropriate]

Designating storage pools for a conservative GC is how I'd want to enable 
GC.  I think a task should be programmer controlled to periodically manage
a Cess_Pool that implements a conservative GC.  The priority of GC could
be changed to suit the application.  Routines for a conservative GC model
might be instantiated from a generic package.

This model would not be as useful to implement non-conservative GC's
because they are highly compiler specific and most likely transparent if 
enabled.  Programs written for a non-conservative GC are brittle.  They
leak memory if you disable GC and they cause trouble for porting to 
another compiler.

The most portable option is to disable GC via pragma Controlled and code
presuming no GC will be available.  Adopting a Cess_Pool model for such a
program would cause minimal conflict and it would offer a less brittle
solution.  ... if only somebody could find the time...

-- John Howard <jhoward@sky.net>               -- Team Ada  Team OS/2 --

Re: Garbage Collection in Ada

[Robert Dewar]

Thomas said

"
Yes, but one difference is: you may write "Junk := null;" as often as you like,
but beware of calling "Free (Junk);" more than once (with any aliases of "Junk")"


You lost the thread :-)

The issue was whether or not you could completely ignore the issue of freeing
memory. Lars claimed that GC allowed you to completely ignore this issue.

The point of pointing out that Junk := null may be necessary was to refute
this incorrect point. Your response is a general note that GC is more
convenient when it comes to freeing memory. Yes, of course, no one disputes
this! And no one did in this thread.

Re: Garbage Collection in Ada

[Robert Dewar]

"I believe the version with full coalescing has worst-case allocation
time log N, where N is the heap size.  Consider a heap with only one
large empty block and repeated requests to alternately allocate and
deallocate a 1 byte block.  (I'm referring to the algorithm in Knuth,
vol. 1, 2nd edition, starting at page 442.  Knuth credits it to
Markowitz and Knowlton.)"

Yes, sure, if the largest block size is the size of the heap, but this is
not the normal scenario for the binary storage allocator. But yes, you are
quite right about the fragmentation, I was thinking of something else when
I answered, and yes, indeed the fragmentation can be much worse than a
factor of 2. Indeed the only way to avoid fragmentation that is pretty
much arbitrarily bad is to implement a proper compacting garbage collector.

My feeling is that if you are going to go beyond the simple conservative
allocators, you really want to go all the way to a fully compacting
collector. This is more practical with Ada than with C++.

Re: Garbage Collection in Ada

[Robert Dewar]

John Howard said

"This model would not be as useful to implement non-conservative GC's
because they are highly compiler specific and most likely transparent if
enabled.  Programs written for a non-conservative GC are brittle.  They
leak memory if you disable GC and they cause trouble for porting to
another compiler."


How odd, this seems exactly the wrong way round, assuming you mean by
brittle, breaking easily, I would make exactly the opposite judgment.
A program that uses a conservative GC either counts on storage being
freed or it does not. If it does not, then it really need not bother
with GC at all. if it does, then there is always a possibility, perhaps
small, that it will not get what it counts on.

Are there really programs that count on conservative GC working? Well
perhaps so. For example, Microsoft Word, at least the version I use,
sometimes leaks memory, and just possibly this is a data dependent
effect if it uses conservative GC, since it could be that if certain
words are in your document, you are unlucky and some storage does
not get freed.

Similarly you can imagine a command interpretor which works most of the
time, except when a certain person logs on, because their password
causes a critical section of storage not to be freed.

I suppose if you are in an environment, e.g. virtual memory spilled to disk,
where not freeing storage is only a performance issue, then CGC makes sense.
But otherwise I can't see relying on the technique

Proper GC seems quite the opposite. Well yes, of course if you turn it off,
the program breaks, what a pointless point! That's like saying, I find
floating-point arithmetic unreliable, if I disable my floating-point
on the processor, the program fails. Or, I find tasking unreliable, because
if I tell the OS to disable tasking the program fails.

As to porting to a non-GC version of the compiler, this of course arises
only for languages where GC is not universal, and is a consideration of
portability, but in practice most programs place restrictions on 
implementations that are not universally supported. Hands up those who
use 32 bit integers in your programs! Is that brittle simply because some
Ada compilers don't have 32 bit integers? I don't think so!

Re: Garbage Collection in Ada

[Lars Farm]

Robert Dewar <dewar@merv.cs.nyu.edu> wrote:

> No, you are confused, if a language expects GC, and if a proper GC is
> incorporated, there is no respect in which the presence of GC inhibits
> optimizations. Where did you get this idea?

From you, <dewar.845470588@merv> about compiler optimization vs
collectors. Since virtual origin is new to me may well be confused. You
said (about C++, conservative GC and virtual origin):
> Such optimization is definitely OK, the fact that incorrect programs,
> such as any conservative collector, can detect that the optimization
> is in place is irrelevant, and it is not just that "some may say this",
> it is absolutely clear.


-- 
Lars Farm, lars.farm@ite.mh.se

Re: Garbage Collection in Ada

[Robert I. Eachus]

In article <dewar.845470908@merv> dewar@merv.cs.nyu.edu (Robert Dewar) writes:

  > Well I would not call it ignorance, since this is certainly not a
  > recognized technical term. In fact I can't even remember if GNAT
  > invented it or not, I suspect we did.

   You may have, but every PL/I compiler implementor I know has come
up with the same term or a similar one.  In PL/I you have to support
pointers to subprograms, which have to designate the code, the
environment/stack and the location of associated static local data.
Some compilers use three word pointers, at Stratus we used two by
having a static pointer and code pointer pair for each subprogram in
global memory, so a fat pointer designated the stack frame and this
vector.

   > We use it simply to mean, as you say, a pointer with other
   > information.  For example, in GNAT, the default (but overridable)
   > form of pointers to unconstrained arrays is a structure with two
   > pointers, one to the data (which could be, but is not yet, a
   > virtual origin), and one a pointer to a record containing the
   > array bounds.

   Just out of curiousity, how do you implement access to subprogram
types in GNAT?  Do you use a pair of addresses or stick the code
pointer in the stack frame?  Or does this vary from target to target?






--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...

Re: Garbage Collection in Ada

[Robert A Duff]

In article <dewar.845470588@merv>, Robert Dewar <dewar@merv.cs.nyu.edu> wrote:
>  (though please for example do not try to use the Boehm collector
>    with the gigi code in GNAT, it will likely not work, although
>    actually I think it is probably OK, even though this code uses
>    virtual origins, I think the "real" pointers are still around.

What does it mean to use virtual origins in C, given that all arrays
start at zero?

- Bob

Re: Garbage Collection in Ada

[Thomas Kendelbacher]

In article <dewar.845388021@merv>, dewar@merv.cs.nyu.edu (Robert Dewar) writes:
>The problem is that it is all too easy to have a global variable around
>that accidentally holds on to a giant structure. Or for example, depending
>on your implementation, taking the 'Access of one field of one record in
>some big structure may end up holding on to an entire subgraph that you
>do not need.
>
>You may in practice need to be just as careful about adding
>
>   Junk := null;
>
>statements to your program as you are now about adding
>
>   Free (Junk);
>
>statements to your program now. 

Yes, but one difference is: you may write "Junk := null;" as often as you like,
but beware of calling "Free (Junk);" more than once (with any aliases of "Junk"),
or when the value of "Junk" may have been achieved using 'Access.
Handling proper deallocation is much easier with GC, IMHO, which leads to simpler
designs and easier-to-read program code.

To my experience with dynamic memory handling, not freeing things that should be
freed is certainly an important problem, but freeing something too often or too
early, accidentally, is much more dangerous because it usually leads to a creeping
corruption of data structures, without warning, which can be hard to detect (the
program starts to act "strange" at some point) and hard/expensive to debug.
With a memory leak, OTOH, at least your program will behave as it should, as long
as its heap memory lasts. Automatic GC avoids the former (the more expensive/
dangerous problem) entirely, and helps avoid memory leaks very well, with
minimal precautions by the programmer:

To continue your example, the solution to the cited problem is simply "avoid
global variables." It's as simple and common-sense as that; don't we do that
anyway, as far as possible? And it's simple to make a design such that it does
take care of the few that remain. (Of course, one has to be aware of the
potential problem; but if you are, it's really easy to avoid it. And if there's
still a memory problem, you know *exactly* where to look.)

P.S. The second problem, a record field accessed from the outside via 'Access,
locking the entire record from GC until the outside access is gone, is simple to
solve, too. If you plan to "share" a record field in this way, you could decouple
the shared object from the record by storing in the record field itself an access
to it, and pass this access value around as you like. With automatic GC,
you don't have to worry when to deallocate it.

-- 
Thomas Kendelbacher   |   email : Thomas.Kendelbacher@erno.de (preferred)
DASA RI / Abt. RIT14  |   voice : +49 421 539 5492 (working hours)
Postfach 28 61 56     |      or : +49 421 576 9670 (any other time)
D-28361 Bremen        |     fax : +49 421 539 4529 (any time)
Germany

Re: Garbage Collection in Ada

[Robert A Duff]

In article <3265BD97.41C6@mti.sgi.com>,
Hans-Juergen Boehm  <boehm@mti.sgi.com> wrote:
>For systems I've seen it does inhibit some optimizations, ar least to
>the extent that proper use of a conservative collector inhibits
>optimizations.  Especially in multithreaded systems, there must be a
>recognizable pointer to every accessible object at every program point
>at which a GC might occur.  Often this is between every pair of
>instructions.  In a nonconservative system you could generate
>arbitrarily complex tables to allow reconstruction of those pointers.

I would think it would be simpler and more efficient to represent this
information as executable code.  That is, the compiler generates a
procedure for each type, and for each stack frame, that knows how to
find all the pointers.  It could take the PC as a parameter, so it could
deal with optimizations where, for example, register R1 contains a
pointer sometimes, and an integer other times.

>But in practice this seems to be limited by engineering considerations
>and table size.

I agree.  (Except I'd say engineering considerations and code size.)

Another effect might be that in a GC'ed environment, an optimizer might
cause objects to be reachable for longer than they should be.
Alternatively, the compiler might try to insert "X := null" in order to
allow garbage to be collected earlier.  Probably these are minor
effects, but there *is* some interaction between an optimizer and a
(nonconservative) gc.

>It could require the existence of a collector, and a (partially)
>conservative collector may well be the most viable implementation
>strategy.

Well, you can write "The implementation shall do garbage collection." in
a language definition, and this statement might have the desired effect
on compiler writers, but I don't know what it means in any *formal*
sense.

Anyway, I don't understand why you would want a conservative collector,
unless you're dealing with an uncooperative language/compiler (like C).
If the language "requires" gc, then there's every opportunity to have a
well-defined interface between generated code and gc, so why be
conservative?

By the way, has anybody tried Boehm's conservative GC with GNAT?  If it
works for gcc, it ought to work for GNAT, I would think.

- Bob

Re: Garbage Collection in Ada

[Larry Kilgallen]

In article <DzFA2u.Aw@world.std.com>, bobduff@world.std.com (Robert A Duff) writes:

> Well, you can write "The implementation shall do garbage collection." in
> a language definition, and this statement might have the desired effect
> on compiler writers, but I don't know what it means in any *formal*
> sense.

For a problematic example one can look at the Macintosh Resource
Manager system calls, where ownership of a block of memory and
rules regarding who should dispose of it change merrily back
and forth between program and OS depending on the semantics
of what might seem like unrelated system calls.

Larry Kilgallen

Re: Garbage Collection in Ada

[Hans-Juergen Boehm]

Robert A Duff wrote:
> 
> In article <3265BD97.41C6@mti.sgi.com>,
> Hans-Juergen Boehm  <boehm@mti.sgi.com> wrote:
> >For systems I've seen it does inhibit some optimizations, ar least to
> >the extent that proper use of a conservative collector inhibits
> >optimizations.  Especially in multithreaded systems, there must be a
> >recognizable pointer to every accessible object at every program point
> >at which a GC might occur.  Often this is between every pair of
> >instructions.  In a nonconservative system you could generate
> >arbitrarily complex tables to allow reconstruction of those pointers.
> 
> I would think it would be simpler and more efficient to represent this
> information as executable code.  That is, the compiler generates a
> procedure for each type, and for each stack frame, that knows how to
> find all the pointers.  It could take the PC as a parameter, so it could
> deal with optimizations where, for example, register R1 contains a
> pointer sometimes, and an integer other times.
> 
That seems to be the consensus.  Whether or not it's right probably
depends on the context.  There appear to be systems around that lose performance
by generating code instead of tables.  There are at least 2 reasons it may be
undesirable:

1. Code size.  Even generating traversal procedures for user-defined data
structures is not free.  (The SRC Modula 3 implementation does this, so it
should even be possible to quantify the effect.)  Things get much worse if
you have to generate a traversal procedure for every client procedure frame,
and if the result of that procedure depends on the PC value.  Even table sizes
for code with limited GC interruption points are nontrivial (see the paper by
Diwan, Moss, and Hudson in PLDI 92).  I would guess that generating such code
for really arbitrary interruption points with full optimization would more
than double code size.  (Actually this is impossible in a few odd cases.  See the
above paper.)

2. Too much procedure call overhead, especially for structures composed of many
small user-defined types.  How much of an issue this is depends on the details
of the compilation system.  But it's usually easier to optimize tables with
whole program information than code.  Since table interpretation can be
cheap, this may dominate.

> Anyway, I don't understand why you would want a conservative collector,
> unless you're dealing with an uncooperative language/compiler (like C).
> If the language "requires" gc, then there's every opportunity to have a
> well-defined interface between generated code and gc, so why be
> conservative?
> 

There are several reasons to go with a collector that acts conservatively by
default, but can make use of type information:

1. C intercallability.
2. The compiler-collector interface is much simpler, at least for the fall-back case.
You might get code compiled by one compiler to link against code compiled by another.
3. You can scan the top stack frame conservatively.  Then you only need to have
pointer location information at call sites, potentially reducing table (or traversal
code) size substantially.
4. You don'y have to get the type information right for hand-coded routines in the
runtime.  In my experience, this is a significant source of persistent GC bugs.  It
also makes it easier to debug other type descriptor problems.


-- 
Standard disclaimer ...
Hans-Juergen Boehm
boehm@mti.sgi.com

Re: Garbage Collection in Ada

[Robert Dewar]

HJB says

"N log K, where N is the size of live data and K is the size ratio
between largest and smallest bound is the best worst-case bound
acheivable by a general purpose nonmoving allocator.  This is an old
result due to Robson, cited in Knuth  (I don't have the reference
handy).  This means a binary buddy system without
coalescing is asymptotically optimal for the worst case.  It does poorly
if your program allocates 1MB of 5 byte objects, deallocates them, then
allocates 1MB of 9 byte objects, deallocates them, allocates 17 byte
objects, etc.  (It's also less space efficient in the typical case
tah other algorithms with worse worst-case behavior.)"


When I say binary storage allocator, I am referring to the Knowlton paper
(note that Knuth did not invent the algorith, just the term buddy system,
and Knuth is concerned to give the right credit as always!)

The essence of the binary storage allocator is that it DOES coalesce
on return, and that for a given maximum block size, the time to coalesce
is bounded by a constant, as is the time to allocate. And in such a system
it is obvious that you cannot be worse than a factor of 2 inefficient
in use of storage (the worst case occcurs if all your allocations are for
one size of block, that is a power of 2 plus one in size).

Re: Garbage Collection in Ada

[Robert Dewar]

HJB says

"It could require the existence of a collector, and a (partially)
conservative collector may well be the most viable implementation
strategy."

What would it mean to sanction the existence of a collector. As I noted
earlier, at most it could mean that you provide for the possibility of
unreachable blocks disappearing, but there are several problems here:


1. Since you only *allow* such collection, completely ignoring the requirement
is a valid semantic interpretation.

2. Since you can only collect unreachable blocks, the removal of them has
null semantics in any case, unless you allow finalization to happen at
unpredictable points, a nasty thought!

3. You cannot require blocks to disappear, since if you have conservative
collectors in mind they do not guarantee to free even a single block in
a given program.

Conservative collectors are a clever idea, and are a clever response to 
dealing with wanting GC in an implementation that does not otherwise
provide GC, but I don't see that the concept has any relevance in language
design.

Re: Garbage Collection in Ada

[Robert Dewar]

"Fair enough.  But then, I find it hard to believe that implmementing
all the annexes had that level of payback either.  Except for the fact
that you can claim to fully support the entire RM (another good reason
why GC annex may have been nice :-).  Think about it, for example, the
DSA is a fine and wonderful thing but I can get everything it offers
in commercially available CORBA based ORBs supporting Ada95.  Not so a
GC...)"

Nope, that is wrong, we see clear evidence (real $$ coming in!) of 
significant commercial interest in the distribution annex. We are not
implementing it for our own amusement, or because we hope people might
be interested. The original work was kicked off by a large company
providing resources, and since then, other serious big customers have
been very interested (interest = $$$, not CLA posts) in this feature!

P.S. Jon is definitely a customer, my comment about it often being the
case that people are looking for something they can use free was not
meant to imply otherwise :-) Of course he is NOT an example of someone
not using Ada because it does not have GC. Now if Jon said he were
switching all his development from Ada to Java solely because Java 
had GC, that would be interesting, or at least it would be interesting
if it were a trend!

Re: Garbage Collection in Ada

[Robert Dewar]

Robert Eachus says

"   Just out of curiousity, how do you implement access to subprogram
types in GNAT?  Do you use a pair of addresses or stick the code
pointer in the stack frame?  Or does this vary from target to target?
"

We follow the GCC model of trampolines (remember that GNU-C already has
nested procedures, using a static chain). The trampoline is a small bit
of code in the stack frame that loads the right static link and jumps
to the right place.

This is done in GNU-C because of a feeling that C programmers expect all
pointers to be the same size. In fact it is a poor choice for Ada, whre
a fat pointer would be better, since there is no similar expectation.
The trouble with trampolines is that on some systems it rquires a system
call to flush the cache on a Harvard architecture processor, and this can
mean that the elaboration of nested procedures is expensive.

Re: Garbage Collection in Ada

[Thomas Kendelbacher]

In article <dewar.845247229@merv>, dewar@merv.cs.nyu.edu (Robert Dewar) writes:
>Lars says
>
>"Cultural bias or even prejudice is the most likely reason IMHO. Not
>technical reasons. On and off the same discussion comes up in the C++
>community. Those that control C++ and those that control Ada simply
>don't want GC :-("
>
>That's nonsense I think. [...]

No, it isn't. In the aerospace industry (probably the most faithful
of Ada's followers that are around) it's the decisive factor.

With so many technical managers and senior engineers who went into
management 10-15 years ago ... I won't say much more here. It just makes
for a good amount of technical conservatism: In those days, the common
belief in this community was that GC is a Bad Thing. Period.

-- 
Thomas Kendelbacher   |   email : Thomas.Kendelbacher@erno.de (preferred)
DASA RI / Abt. RIT14  |   voice : +49 421 539 5492 (working hours)
Postfach 28 61 56     |      or : +49 421 576 9670 (any other time)
D-28361 Bremen        |     fax : +49 421 539 4529 (any time)
Germany

Re: Garbage Collection in Ada

[Rick Hudson]

Hans-Juergen Boehm <boehm@mti.sgi.com> writes:
> 
> Rick Hudson wrote:
> > 
> > If GC is triggered only by an allocate then
> > one could roll forward the threads to a 'gc' point. This greatly 
> > reduces the amount of table information needed.
> > 
> 
> This works well if you can reliably and reasonably quickly advance
> threads to the next GC point without forcing them to execute code at the
> GC point when they don't need to stop.  In some systems that's easy.  In
> some that's hard.  The thread systems I've used can't easily do that.


The slickest idea I've heard of, I think it was from Greg Nelson, was to have
a routine that clones the code from where the thread stopped to the gc safe
point. The routine would execute the cloned code instead of the original code
and then halt at the gc safe point. The thread would be resumed in the normal
code. This technique will give you no normal execution overhead.

- Rick Hudson

Re: Garbage Collection in Ada

[Jon S Anthony]

In article <dewar.845559025@merv> dewar@merv.cs.nyu.edu (Robert Dewar) writes:

> "Fair enough.  But then, I find it hard to believe that implmementing
> all the annexes had that level of payback either.  Except for the fact
> that you can claim to fully support the entire RM (another good reason
> why GC annex may have been nice :-).  Think about it, for example, the
> DSA is a fine and wonderful thing but I can get everything it offers
> in commercially available CORBA based ORBs supporting Ada95.  Not so a
> GC...)"
> 
> Nope, that is wrong, we see clear evidence (real $$ coming in!) of 
> significant commercial interest in the distribution annex. We are not
> implementing it for our own amusement, or because we hope people might
> be interested. The original work was kicked off by a large company
> providing resources, and since then, other serious big customers have
> been very interested (interest = $$$, not CLA posts) in this feature!

You're being sloppy - you mean I may be part wrong in claiming that
implementing all the annexes may not have had "that level of payback".
I am clearly not wrong in claiming Orbix/Ada offers functionally
everything (and more) than the DSA.  I can guarantee that.  I had the
choice and have opted for the ORB.  Further, I am not wrong in stating
that I don't have this sort of option for GC.


> P.S. Jon is definitely a customer, my comment about it often being the
> case that people are looking for something they can use free was not
> meant to imply otherwise :-)

Check!

> Of course he is NOT an example of someone not using Ada because it
> does not have GC. Now if Jon said he were switching all his
> development from Ada to Java solely because Java had GC, that would
> be interesting, or at least it would be interesting if it were a
> trend!

It would indeed.  Mostly because it would make no sense as I have
pointed out in many other posts.  Now, I _could_ sensibly claim that I
am switching to Eiffel or SmallTalk because they are expected to have
GC (and all available impls do) and Ada impls typically don't.  But
I'm not, because while GC is (IMO) very important it is not important
enough to offset all the other advantages of Ada over those two.  Not
by quite a bit.  For example, in general (and for us in particular) a
solid high level portable tasking model is far more important.

/Jon
-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com

Re: Garbage Collection in Ada

[Jon S Anthony]

In article <dewar.845559025@merv> dewar@merv.cs.nyu.edu (Robert Dewar) writes:

> Nope, that is wrong, we see clear evidence (real $$ coming in!) of 
> significant commercial interest in the distribution annex. We are not
> implementing it for our own amusement, or because we hope people might
> be interested. The original work was kicked off by a large company

Ooops, forgot this part, :-)

Robert.  Sometimes you amaze me.  What makes you think any such
interest would be there if the DSA had NOT BEEN INCLUDED????
Hmmmm????

/Jon

-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com

Re: Garbage Collection in Ada

[Hans-Juergen Boehm]

Robert Dewar wrote:
> 
> Are there really programs that count on conservative GC working? Well
> perhaps so. For example, Microsoft Word, at least the version I use,
> sometimes leaks memory, and just possibly this is a data dependent
> effect if it uses conservative GC, since it could be that if certain
> words are in your document, you are unlucky and some storage does
> not get freed.
> 
I'm quite sure that Microsoft Word does NOT use a conservative GC.  If
it did, you might not have this problem.

There are a number of systems that do count on conservative GC to
various extents, e.g. the Xerox PARC Cedar programming environment, some
Xerox printers, every Modula-3 program, every Sather program, etc.  I
believe the standard Sun Java run-time also uses a partially
conservative GC  (see the recent discussion in comp.lang.java.tech).

In general, my experience has been that such applications are much more
reliable than manually memory managed code, for the obvious reasons:
reasons:

1. No memory leaks of the traditional kind.
2. Users are less afraid to use robust data structures that require
dynamic memory allocation and shared substructures.

During my last several years at Xerox, I don't believe that I had to
ever restart my Cedar environment due to conservative GC leakage, and it
routinely stayed up for weeks.

I know of only a few anecdotes in which significant leaks were observed
with a conservative collector.  These were all repeatable and easily
fixed by supplying a small amount of type information in one or two
places.  (I believe that in all cases in which the program was written
for GC, even the leaky program actually remained usable.  The really bad
cases occurred with custom allocation hacks designed to get around a
slow noncollecting allocator, which was then replaced by a collector.)

-- 
Standrard disclaimer ...
Hans-Juergen Boehm
boehm@mti.sgi.com

Re: Garbage Collection in Ada

[Lars Farm]

Robert Dewar <dewar@merv.cs.nyu.edu> wrote:

> Are there really programs that count on conservative GC working?

Ok, you don't like conservative collectors. Could you please explain in
a bit more detail why conservative collectors are so bad.

I don't have the expertise needed to confirm or refute your statements.
It seems to me that for a conservative collector to falsely retain a
block of memory there has to be a bitpattern somewhere in the root set
(stack, globals, registers, currently allocated blocks,(?)) that can be
interpreted as (1) a pointer to one of the currently allocated blocks
that is (2) unreachable from the root set (no longer any user pointers
to it) (3) not yet reused by the collector.

Your dislike (apparently shared by other Ada people) for conservative
collectors has raised a couple of questions that I can not answer. I
would like to get some feel for how bad this really is. 

- How large is the probability that this occurs?
- How large is the probability that this state persists?
- How large fraction of allocated memory will typically be
  falsely retained?
- Is the set of retained blocks growing over time or will it 
  level out at some point in time? If so where?
- other?

This leads to larger memory consumption. This may or may not be a
problem. To put the problem into perspective one could perhaps compare
to other common engineering compromises in computing. How likely is it
that Quicksort will crash due to stack overrun? How likely that a
Skiplist will behave in a non optimal fashion? How likely that a binary
tree turns linear? How likely that a compiler has a bug that will make
your program fail one way or another? How much RAM is wasted because one
makes redundant copies of a datastructures just to know when to release
RAM without GC instead of sharing the datastructure with GC? and many,
many other similar hazards that a program is exposed to.

I believe, perhaps wrongly, that the "problems" of a conservative GC is
on or even below that scale. Is it? or is it much worse? The impression
I get from your posts is that you would place the problems of a
conservative collector way over the common problems we face daily.


-- 
Lars Farm, lars.farm@ite.mh.se

Re: Garbage Collection in Ada

[Lars Farm]

Robert Dewar <dewar@merv.cs.nyu.edu> wrote:

> Hands up those who
> use 32 bit integers in your programs! Is that brittle simply because some
> Ada compilers don't have 32 bit integers? I don't think so!

Yes. Same situation in C++. Brittle enough for me to do this if I need
32-bit ints:

  class X {
    struct assert_ { char intsize[ sizeof(int) >= 4 ? 1 : 0 ]; };
    ...

The point is related to GC. There should be some portable way to detect
the presence of GC at compiletime. Ada has optional GC. I don't know Ada
enough so I ask: Is there a portable way to detect at compiletime
whether the implementation supports GC or is there not?


-- 
Lars Farm, lars.farm@ite.mh.se

Re: Garbage Collection in Ada

[Robert Dewar]

Jon said

"Robert.  Sometimes you amaze me.  What makes you think any such
interest would be there if the DSA had NOT BEEN INCLUDED????
Hmmmm????"


Sorry, I am not sure I understand, included in what?


Included in GNAT? Well it certainly was not at first!

Included in  Ada 95? The best answer there is Corba, there is at least
as much interest in using Corba as a distribution mechanism as there is
in using the Annex E facilities, so inclusion in the RM is not the key!

The interest in these things comes from application requirements!

Re: Garbage Collection in Ada

[Richard Kenner]

In article <DzEC1x.34J@world.std.com> bobduff@world.std.com (Robert A Duff) writes:
>What does it mean to use virtual origins in C, given that all arrays
>start at zero?

The corresponding array on the Ada size *doesn't* start from zero, but
instead some large positive number.  We use the same index in C and Ada
by subtracting the lower bound from a pointer to the array in C.

This exactly corresponds to the use of virtual origins in C (and yes, it
isn't a legal ANSI C program).

Re: Garbage Collection in Ada

[Robert Dewar]

Bob Duff says

"What does it mean to use virtual origins in C, given that all arrays
start at zero?"

Two answers. At the programmers level, the logical bounds of an array
may not start at zero, but at something else, so your subscripts run
from say 10..100. In this situation, the normal requirement is to
subtract 10 from the subscript on each reference. However, you can
at the C level use virtual origins in this situation. As has been
pointed out, this is not strictly correct code, but in the absence
of a conservative garbage collector running around and deleting
unrefrenced blocks (:-) will in fact work on any imaginable C
compiler, and certainly works on GCC. For an example of this, see
Gigi coding (note incidentally that Gigi is expected to be compiled
using GNU C, so if ever there was some other C compiler that did NOT
accept this senmantics, it won't affect Gigi coding).

The second answer is that in optimizing code, all sorts of transformations
can occur, especially if you start doing high level optimization that
can cause non-zero based arrays to appear as part of the transformations.
This is the situation in which a compiler may end up fiddling with pointers
in a way that is incompatible with a conservative GC. 

The use of a conservative GC system is, like the virtual origin coding
in Gigi, something that probably works OK, even though it is requires
some dubious fiddling (in particular the assumption that type casts
from integer to pointer leave bits unchanged, something that the ANSI
C specification could not require even if it wanted to). Lots of C
programs depend on such ANSI-standard-dubious fiddling, so there is good
company here, although it is interesting to note that the mixture of
two such fiddles can sometimes go astray (as is the case with conservative
GC, and manual virtual origin mucking).

Re: Garbage Collection in Ada

[Robert Dewar]

Lars asks

I don't have the expertise needed to confirm or refute your statements.
It seems to me that for a conservative collector to falsely retain a
block of memory there has to be a bitpattern somewhere in the root set
(stack, globals, registers, currently allocated blocks,(?)) that can be
interpreted as (1) a pointer to one of the currently allocated blocks
that is (2) unreachable from the root set (no longer any user pointers
to it) (3) not yet reused by the collector.

- How large is the probability that this occurs?

   very hard to tell, but a program that relies on this not happening is
   inherently unreliable.

- How large is the probability that this state persists?

   unknown

- How large fraction of allocated memory will typically be
  falsely retained?

   unknown

- Is the set of retained blocks growing over time or will it
  level out at some point in time? If so where?

   could grow over time certainly

- other?

   other than the small possibility of freeing in-use blocks, and the
   consequent necessity to make sure you know what your compiler is
   doing and what your program is doing, I don't see any. 

How likely is it that Quicksort will crash due to stack overrun?

   This has zero probability in a properly written version. Only incompetent
   student implementations of Quicksort could fail with a stack overrun that
   was data dependent. You should know the technique (anyone should), you
   simply sort the small half first. This is an absolutely standard divide
   and conquer trick for keeping stack usage to logN.

How likely that a Skiplist will behave in a non optimal fashion?

   Any program depending on it NOT so behaving has a bug

How likely that a binary tree turns linear?

   Any program depending on this has chosen a wrong data structure!

How likely that a compiler has a bug that will make
your program fail one way or another?

   Well possible, but data dependent bugs are somewhat rarer, but certainly
   this is possible in a non-certified program.

How much RAM is wasted because one makes redundant copies of a datastructures
just to know when to release RAM without GC instead of sharing the
datastructure with GC?

   Again, a program that depends on this without proper analysis has a bug

and many, many other similar hazards that a program is exposed to.

   Well programs can be "exposed" to many problems caused by incompetent
   engineering decisions. I would say that relying on a conservative
   garbage collector NOT to get unlucky is something that you can afford
   to do in one-off programs that don't need to be reliable, and perhaps
   even in typical PC software (so what if the word processor crashes once
   a week - that seems to be what people expect anyway).

   But, as in my original point, I don't see that many high reliability
   programs could rely on conservative GC for correctness, though possibly
   they could rely on it for average case performance requirements.

P.S. does lack of expertise mean you have no experience with conservative
collectors? For someone with no experience, you sure are an enthusiast :-)
I will admit I have no experience with them either, because I have never
had occasion to need or want unreliable garbage collection in any program
I have written. I have OFTEN relied on reliable garbage collection, and
consider this a very valuable feature for a very large range of programs.

Re: Garbage Collection in Ada

[Lars Farm]

Robert Dewar <dewar@merv.cs.nyu.edu> wrote:

> it is interesting to note that the mixture of
> two such fiddles can sometimes go astray (as is the case with conservative
> GC, and manual virtual origin mucking)

If you were someone other than Prof. Dewar I'd be tempted to say: "No,
you are confused " ;-) User code is not the same thing as the runtime
system provided by the implementation. The GC should be provided by the
impementation. 

The language specs imposes no restrictions on the language the runtime
system is written in. The runtime system is there in part to encapsulate
unportable tricks and hide them from the user.

The restrictions imposed by a language spec concerns user code only.
Consequently manual virtual origin at the user level is definitly not
valid C++. Such code is broken. No matter how popular. Even if it by
accident happens to work with this or that compiler on some systems.

A conservative collector provided by the implementation as part of the
runtime system does not break the rules even if it was written in
something that looked like C or C++. It could be written in any
language. Including an unportable C-like language only available to the
compiler implementors.

I assume (but do not know) that the Ada runtime system would be very
hard to implement fully in entirely conforming Ada too.


-- 
Lars Farm, lars.farm@ite.mh.se

Re: Garbage Collection in Ada

[Robert Dewar]

Lars replies to me

"
> it is interesting to note that the mixture of
> two such fiddles can sometimes go astray (as is the case with conservative
> GC, and manual virtual origin mucking)

If you were someone other than Prof. Dewar I'd be tempted to say: "No,
you are confused " ;-) User code is not the same thing as the runtime
system provided by the implementation. The GC should be provided by the
impementation."


I reply to the reply:

But this is, so far, a fantasy. The only kind of GC provided by standard
implementations, at least in my experience, is proper accurate GC, that is
of course embedded into the compiler or operating system or both.

You can certainly imagine a system that provides conservative garbage
collection as a standard part of a compiler, or even just a standard
system library. But I don't know of any such commercial products, do you?

So in practice, a conservative garbage collector is just a bit of application
code which you get from somewhere and include in your application. It also
happens to be application code that is fiddling with C semantics. Hence my
comment definitely does apply!

Actually, as I have noted before, I am dubious about real applications
depending on conservative GC, so I can't see it being an integral part
of a language implementation. For example, I can see putting a conservative
collector interface into some user library for GNAT, but not into the main
language library.

Actually I think that Geert is indeed working on interfacing the HJB 
CGC to GNAT (that's why he complained about the possibility of us moving
to use virtual origins, something we definitely intend to do at some point,
so presumably this conservative GC would stop working if we did that, unless
it got more clever (more clever is possible here, but difficult, i.e. the
scan of memory could recognize in addition to simple direct pointers, possible
instances of virtual origin descriptors, they have a perfetly well defined
format.

Re: Garbage Collection in Ada

[Robert A Duff]

In article <199610182314423204049@dialup122-4-9.swipnet.se>,
Lars Farm <lars.farm@ite.mh.se> wrote:
>...Ada has optional GC. I don't know Ada
>enough so I ask: Is there a portable way to detect at compiletime
>whether the implementation supports GC or is there not?

There is not.

- Bob

Re: Garbage Collection in Ada

[Robert A Duff]

In article <199610181934142408603@dialup101-3-15.swipnet.se>,
Lars Farm <lars.farm@ite.mh.se> wrote:
>- How large is the probability that this occurs?

(Where "this" = "conservative GC fails to collect some garbage".)

I don't see any way of assigning a numeric probability to it.  That's
the main thing that makes *me* nervous about it.  I mean, there's
nothing under the programmer's control that can let you know if or when
this sort of bug might happen.

You do have a point, though.  For example, many compilers use hash
tables, which are intolerably slow in the worst case.  And the compiler
designer often doesn't do any analysis to determine the probability of
that happening.  Just wait until somebody complains, and then fix it.

But I still don't want to trust a conservative GC, at least not for any
program that is supposed to be reliable.

- Bob

Re: Garbage Collection in Ada

[Robert A Duff]

In article <dewar.845732059@merv>, Robert Dewar <dewar@merv.cs.nyu.edu> wrote:
>...As has been
>pointed out, this is not strictly correct code, but in the absence
>of a conservative garbage collector running around and deleting
>unrefrenced blocks (:-) will in fact work on any imaginable C
>compiler, ...

Not *quite* true -- there *are* C compilers that try to detect
non-ANSI-compliant use of pointers (for debugging purposes only, since
it's extremely inefficient), and you presumably would not be able to run
GIGI on such a compiler.  Of course GIGI is a special case -- when one
is committed to doing a bootstrapped compiler, one has a lot of freedom
to play games.  For example, I'm sure the GNAT front end would not
compile on any Ada compiler other than GNAT.  In fact, in some cases,
one version of the GNAT compiler won't compile under a different
(earlier or later) version of GNAT.

>The second answer is that in optimizing code, all sorts of transformations
>can occur, especially if you start doing high level optimization that
>can cause non-zero based arrays to appear as part of the transformations.
>This is the situation in which a compiler may end up fiddling with pointers
>in a way that is incompatible with a conservative GC. 

Oh, OK.  I didn't think that's exactly what "virtual origins" meant -- I
would call that "using algebraic transformations to represent pointers",
or "virtual-origin-like optimizations".  I guess it amounts to the same
thing.

>The use of a conservative GC system is, like the virtual origin coding
>in Gigi, something that probably works OK, even though it is requires
>some dubious fiddling (in particular the assumption that type casts
>from integer to pointer leave bits unchanged, something that the ANSI
>C specification could not require even if it wanted to).

They could have required that type casts of that nature don't lose
information, so they're reversible.  If they had wanted to, which they
didn't.

- Bob

Re: Garbage Collection in Ada

[Robert A Duff]

In article <dewar.845809398@merv>, Robert Dewar <dewar@merv.cs.nyu.edu> wrote:
>But this is, so far, a fantasy. The only kind of GC provided by standard
>implementations, at least in my experience, is proper accurate GC, that is
>of course embedded into the compiler or operating system or both.

There are some counter-examples.  Hans Boehm pointed out one case in
this thread -- a GC that conservatively scans the stack (or the top-most
stack frame) for each thread/task, which is an integral part of the
compiler system.  This is done for efficiency and/or for ease of
implementation -- given the fact that it is very difficult to do garbage
collection if you have lots of tasks that can be interrupted between any
two instructions.  If the GC can happen at any time, the GC doesn't know
much about the consistency of things on the stack.  Or in registers.

But I still share your (Robert's) nervousness about relying on
conservative GC's.  And if I were implementing a GC for a GC-friendly
language and compiler, I would probably not make it conservative.

- Bob

Re: Garbage Collection in Ada

[Robert Dewar]

Robert Duff said

"You do have a point, though.  For example, many compilers use hash
tables, which are intolerably slow in the worst case.  And the compiler
designer often doesn't do any analysis to determine the probability of
that happening.  Just wait until somebody complains, and then fix it."

Well not so intolerable, there is a big difference btween compiling one
program slower by a relatively small linear factor, and blowing up in
an application at runtime because you ran out of memory. As I said
before, if the only consequnece of not collecting garbage is to slow
things down (e.g. by using more virtual memory swapping), then the two
cases are indeed comparable.

Re: Garbage Collection in Ada

[Robert Dewar]

Bob Duff said

Not *quite* true -- there *are* C compilers that try to detect
non-ANSI-compliant use of pointers (for debugging purposes only, since
it's extremely inefficient), and you presumably would not be able to run
GIGI on such a compiler.  Of course GIGI is a special case -- when one
is committed to doing a bootstrapped compiler, one has a lot of freedom
to play games.  For example, I'm sure the GNAT front end would not
compile on any Ada compiler other than GNAT.  In fact, in some cases,
one version of the GNAT compiler won't compile under a different
(earlier or later) version of GNAT.

   Well (a) such compilers are not used for serious development in my
   experience, and in any case (b) we always use GNU C to compile Gigi
   in any case so it certainly does not affect us.

They could have required that type casts of that nature don't lose
information, so they're reversible.  If they had wanted to, which they
didn't.

   Interesting, certainly K&R requires lossless reversible conversion of
   pointers to integers and back again. But that's not the point, suppose
   all pointers were stored by xoring the location of the pointer with the
   pointer, Silly of course, but legal, providing the code generator properly
   renormalizes on every load, but enough to bamboozle the CGC. This is an
   extreme example, you can imagine cases that might actually arise, e.g.
   encoding some information into pointers in a retrievable way.

Re: Garbage Collection in Ada

[Robert Dewar]

iRobert Duff

"There are some counter-examples.  Hans Boehm pointed out one case in
this thread -- a GC that conservatively scans the stack (or the top-most
stack frame) for each thread/task, which is an integral part of the
compiler system.  This is done for efficiency and/or for ease of
implementation -- given the fact that it is very difficult to do garbage
collection if you have lots of tasks that can be interrupted between any
two instructions.  If the GC can happen at any time, the GC doesn't know
much about the consistency of things on the stack.  Or in registers."


A counter example to my claim that CGC is not embedded in standardly
used compilers or operating systems requires you to cite a particular
system or compiler that is commercially available, not to theorize about
what might be done!

Re: Garbage Collection in Ada

[Lars Farm]

Robert Dewar <dewar@merv.cs.nyu.edu> wrote:

> P.S. does lack of expertise mean you have no experience with conservative
> collectors? 

No, I have experience with conservative GC. Hans-Juergen Boehm has
participated in this thread. He is an expert and I want make it clear
that I am not in his league, or even near. I have used his collector and
tweaked it slightly for my compilers. Noticed that it works very nicely
in two relatively small real life projects and failed to see the bad
effects you mention.

I'm genuinely puzzled and simply trying to figure out which of the
conflicting views is right: (1) my limited experience combined with
others claims that the set of falsely retained pointers is relatively
small. A small, perhaps negligible problem. or (2) Your claims that this
is a serious error that likely will make my program fail. The views
simply don't match. I need more information.

> For someone with no experience, you sure are an enthusiast :-)

I didn't say I was without experience. Using GC in C++ has been a good
experience ;-) There is only one thing holding me back from using GC
always in C++. Portability of source code. I would like to see GC one
way or another in a language. User and vendor optional is fine with me,
but some language sanction is needed. At least be able to determine at
compiletime whether this compiler/runtime system supports GC or not.
Because very few C++ or Ada programmers currently trust GC. 

My interest in Ada is simply that I see Ada as the most reasonable
alternative to C++. I'm also trying to figure out if Ada is what I want.


-- 
Lars Farm, lars.farm@ite.mh.se

Re: Garbage Collection in Ada

[Robert Dewar]

Lars asks

"A question of definitions, perhaps. Would you agree that the built in
new/delete is part of the runtime system in C++? Users may legaly
replace the global new/delete. Wouldn't the replacement then be part of
the runtime system? Note, replacements are subject to the same ..."


The new and delete operations are part of the proposed C++ standards, and 
are thus part of the language. Whether they are part of the "runtime" or
not is an implementation detail. If you replace them (there is no requirement
in C++ that you be able to do so), then you may or may not have a standard
implementation.

Your replacement may or may not be part of the runtime system, since that
in any case is not a formally defined term, but it is certainly NOT part
of the standard commercial distribution of the compiler and OS.

Re: Garbage Collection in Ada

[Robert Dewar]

Lars said

"I'm genuinely puzzled and simply trying to figure out which of the
conflicting views is right: (1) my limited experience combined with
others claims that the set of falsely retained pointers is relatively
small. A small, perhaps negligible problem. or (2) Your claims that this
is a serious error that likely will make my program fail. The views
simply don't match. I need more information."

That is a complete misreading of what I said, please go to an archive and
reread the thread! I never said that it would "likely" make your program
fail. I simply said that

(a) there was a non-zero probability that a program relying on CGC could fail
(b) at least for my application areas, I am not interested in programs that
    may fail unpredictably, even if the probability is small.

Sure there are many things that may make a program fail, but these are bugs
that must be stamped out. I don't see that it is reasonable to build into
a program a technique that by its very nature introduces this kind of
unreliability.

Your experience says nothing to answer this concern. If you cut corners on
maintaining your personal airplane, and manage to fly around without crashing,
that does not constitute evidence that the recommended careful mainteance
is a bad idea.

There is a big difference between "my program seems to work", and "I have
designed my program to be reliable to the best of my ability".

Note again the important exception that if the only issue is performance,
then it seems quite reasonable to rely on CGC to generally improve 
performance in the average case.
\x1a

Re: Garbage Collection in Ada

[Laurent Pautet]

>>>>> "Jon" == Jon S Anthony <jsa@alexandria> writes:
Jon> payback".  I am clearly not wrong in claiming Orbix/Ada offers
Jon> functionally everything (and more) than the Distributed System Annex.

Yes ? Is it obvious in a client code to handle an exception (print the
exception message) that has not been declared in a server spec ? Is it
obvious to ensure remote asynchronous transfert control in CORBA ? How
do you implement share data (matrix and slices) ? And atomic
operations on these data ?  These are of course examples but it is
very easy to find features that are impossible or complex to write
with CORBA (even remote object features) and that are very easy with
Annex E. Of course, you will be able to implement complex features
with CORBA, but you're going to write everything with some kind of
message passing (or asynchronous RPCs) when DSA would provide exactly
what you are looking for.

Of course, it could be very interesting to implement DSA on the top of
CORBA because in some respects, "<DSA> offers functionally everything
(and more) than <CORBA>" :-)

Re: Garbage Collection in Ada

[Jon S Anthony]

In article <dewar.845692633@merv> dewar@merv.cs.nyu.edu (Robert Dewar) writes:

> Jon said
> 
> "Robert.  Sometimes you amaze me.  What makes you think any such
> interest would be there if the DSA had NOT BEEN INCLUDED????
> Hmmmm????"
> 
> 
> Sorry, I am not sure I understand, included in what?
> 
> 
> Included in GNAT? Well it certainly was not at first!
> 
> Included in  Ada 95? The best answer there is Corba, there is at least
> as much interest in using Corba as a distribution mechanism as there is
> in using the Annex E facilities, so inclusion in the RM is not the key!
> 
> The interest in these things comes from application requirements!

I really meant "included in the RM" and probably should have tossed in
a smilely or two.  Yes, the interest comes from application
requirements.  The interest you say which is generating _new_ Ada
customers, comes from seeing the DSA as a nice Ada solution to the
requirements.

/Jon
-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com

Re: Garbage Collection in Ada

[Hans-Juergen Boehm]

I will argue yet again that there is no fundamental difference in
reliability between conservative collection and a general purpose
vendor-supplied nonmoving memory allocator with explicit deallocation.
To guarantee that your program doesn't run out of memory, you would have
to prove that a certain amount of memory suffices.  I'm not an expert on
Ada implementations, but in C this is impossible for many reasons:

1.  The worst-case memory requirements of ANY general purpose malloc
implementation are quite bad.  This is a mathematical theorem.  The only
way to limit this is to restrict object sizes.

2.  Many vendor malloc implementations have even worse worst-case
behaviour, sometimes much worse.

3.  Vendors rarely specify the allocation algorithm.  So it's not
possible to tune for the algorithm even in nonportable code.

4.  Independent of fragmentation issues, language standards don't
sprcify padding, allocator overhead, etc.

Random corrections/observations:

- I know of no commercial system vendors that include a conservative GC.
There are many third-party language implementations that include a GC
that's at least partially conservative (e.g. SRC Modula-3, NAG Fortran
90, Sun's Java, Sather, ...)

- I don't believe it's realistically possible for a C compiler to
exclusive-or the pointer location into the pointer value (or to use
self-relative pointers).  Copying pointer-containing unions becomes
essentially impossible.  (This is irrelevant to the discussion, but ...)

- "Virtual origins" work fine with a conservative GC, so long as you
also keep the naive pointer representation.  This is likely to be cheap 
(at most one extra store).

- The latest draft of the C++ standard requires new and delete to be
replaceable.  (This is also irrelevant, I think ...)

- There are a number of measurements of accidentally retained memory by
conservative GC.  It's usually smaller than fragmentation losses, which
aren't very big either.  That says nothing about worst-case bounds.  

-- 
Standard disclaimer ...
Hans-Juergen Boehm
boehm@mti.sgi.com

Re: Garbage Collection in Ada

[Nicolay Belofastow]

Hello!

Following the topic -- does GNAT Ada95 compiler (for Win95)
support the  GC?

Thanks in advance, Nick.
--
-------------------------------------------------
Nickolay Belofastow
University of the Federal Armed Forces, Munich
e81bnick@rz.unibw-muenchen.de

Re: Garbage Collection in Ada

[Robert Dewar]

1.  The worst-case memory requirements of ANY general purpose malloc
implementation are quite bad.  This is a mathematical theorem.  The only
way to limit this is to restrict object sizes.

   Yes, and restricting object sizes is a common technique. Indeed
   going all the way and restricting object sizes to a single size
   completely eliminates fragmentation, but does NOT eliminate the
   problem of CGC hanging on to blocks that should be freed.

3.  Vendors rarely specify the allocation algorithm.  So it's not
possible to tune for the algorithm even in nonportable code.

   Yes, and providing your own allocator with known characteristics
   is a common technique.

- "Virtual origins" work fine with a conservative GC, so long as you
also keep the naive pointer representation.  This is likely to be cheap
(at most one extra store).

   Actually it is a space issue more than a speed issue, it means that
   pointers to unconstrained arrays would need to be three words instead
   of two, certainly not fatal, but not space that would seem worth
   spending for the relatively specialized use of 3rd party CGC's.

Re: Garbage Collection in Ada

[Robert Dewar]

Nick asked

"Following the topic -- does GNAT Ada95 compiler (for Win95)
support the  GC?

Thanks in advance, Nick."



Well I guess you have not been following it *too* carefully, or you would
know the answer. As I have discussed several times, GNAT does not implement
GC for a simple reason, it is not something our customers are asking for.
Yes I understand the enthusiasts are sure that implementing GC will bring
flocks of new customers but I am not convinced (note that we go through
examples of this all the time, people are always convinced that we should
implement their favorite feature in GNAT and fund the implementation
ourselves because we will get scads of extra paying users :-)

It's certainly on the list as a future possible enhancement, in fact we
have done quite a bit of work studying the issue of whether we can provide
a special garbage collected storage pool.

But right now we are much more busy with things that are customers do
want, and that will *definitely* attract more userss, notably validation!

Re: Garbage Collection in Ada

[Hans-Juergen Boehm]

Geert Bosch wrote:
> 
> Another reason to stop work on the CGC was that there is much more
> interest for an exact GC for GNAT. During my work on the CGC I found
> literature by Paul Wilson and Marc Shapiro describing precise scanning
> using just debug information to do full compacting/moving GC.
> 
In the absence of C-style unions, you can get layout information for
heap objects from debug information.  I have yet to hear any claims
before this that you can get reliable pointer-location information for
stack frames and registers, especially for optimized code, from
debugging information.  Certainly none of the debuggers I use are
accurate enough on optimized code.  Yes, that means you can build a
Bartlett-style mostly copying (or mostly-compacting) collector.  But it
will still scan the stack conservatively.

Using debugging information in this way is fine.  On the other hand,
copying or compacting during every collection is not a good idea.
(Copying takes too much space.  It's too hard to compact incrementally,
and it takes too much time.)  At most you want to copy young objects and
compact old objects occasionally.

-- 
Standard disclaimer ...
Hans-Juergen Boehm
boehm@mti.sgi.com

Re: Garbage Collection in Ada

[Geert Bosch]

Robert Dewar (dewar@merv.cs.nyu.edu) wrote:
`` Actually I think that Geert is indeed working on interfacing the HJB
   CGC to GNAT (that's why he complained about the possibility of us
   moving to use virtual origins, something we definitely intend to do
   at some point, [...]''

More exactly, I _was_ working on a CGC for GNAT. This was an assignment
for a course I had, but I have decided not to continue working on it
after I finished the course. This was partly because of time
constraints and the reasons given below.

`` [...] so presumably this conservative GC would stop working if we
   did that, unless it got more clever (more clever is possible here,
   but difficult, i.e. the scan of memory could recognize in addition
   to simple direct pointers, possible instances of virtual origin
   descriptors, they have a perfetly well defined format. ''

From the discussion in comp.lang.ada I concluded that it was wasted
time to spend more time developing a CGC for GNAT. Even if such a GC
turns out to work just fine in practise people also have to accept the
technology, which is not the case for many people.

Another reason to stop work on the CGC was that there is much more
interest for an exact GC for GNAT. During my work on the CGC I found
literature by Paul Wilson and Marc Shapiro describing precise scanning
using just debug information to do full compacting/moving GC.

Even when there will be some arbitrary pointers left like CPU-registers
and pointers due to interfacing with foreign language libraries without
debugging information, this can still be a good approach. (See also
Joel Bartlett's mostly copying GC.)

So, there is a good way to implement precise GC for GNAT without
changing the compiler which is very complex already. Using debug
information with GNAT also has the virtue that (under mild conditions)
precise scanning can be done even when interfacing to C/C++ and that
the fat pointers used by GNAT are a big help.

Because of these points I think it is very well possible to implement a
precise GC for GNAT without changing or limiting the compiler too
much.  According to comp.lang.ada readers there is also demand for a
precise GC for GNAT, so my next question is: who is going to develop
such a GC or fund development? ;-)

Regards,
   Geert

-- 
E-Mail: geert@sun3.iaf.nl    

Re: Garbage Collection in Ada

[Lars Farm]

Robert Dewar <dewar@merv.cs.nyu.edu> wrote:

> If you replace them (there is no requirement in C++ that you be
> able to do so), then you may or may not have a standard implementation

18.4  Dynamic memory management/1
[...]
  Replaceable:
    a  C++  program  may  define a function with this function signature
    that displaces the default  version  defined  by  the  C++  Standard
    library.
  Required behavior:
    Return     a    pointer    to    dynamically    allocated    storage
    (_basic.stc.dynamic_), or else throw a bad_alloc exception.
[...]


-- 
Lars Farm, lars.farm@ite.mh.se

Re: Garbage Collection in Ada

[Lars Farm]

Robert Dewar <dewar@merv.cs.nyu.edu> wrote:

> You can certainly imagine a system that provides conservative garbage
> collection as a standard part of a compiler, or even just a standard
> system library. But I don't know of any such commercial products, do you?

A question of definitions, perhaps. Would you agree that the built in
new/delete is part of the runtime system in C++? Users may legaly
replace the global new/delete. Wouldn't the replacement then be part of
the runtime system? Note, replacements are subject to the same
requirements as the built in new/delete. Boehms collecting allocator
(and others) replaces the global new/delete via this mechanism. Is'nt it
then part of the runtime system?

I think a general purpose GC allocator must be viewed as part of the
runtime system even if you bought that part of the runtime system from
some other vendor than the compiler.

Does Ada have a similar mechanism? Or is Ada's optional GC purely the
vendors option?


-- 
Lars Farm, lars.farm@ite.mh.se

Re: Garbage Collection in Ada

[Jon S Anthony]

In article <rca3ez8w04p.fsf@quasimodo.enst.fr> Laurent Pautet <pautet@inf.enst.fr> writes:

> >>>>> "Jon" == Jon S Anthony <jsa@alexandria> writes:
> Jon> payback".  I am clearly not wrong in claiming Orbix/Ada offers
> Jon> functionally everything (and more) than the Distributed System Annex.
> 
> Yes ? Is it obvious in a client code to handle an exception (print the
> exception message) that has not been declared in a server spec ?

Sure.  What makes you think otherwise?


>  Is it obvious to ensure remote asynchronous transfert control in
> CORBA ?

With threads (tasking), yes.  So, with Ada you're OK.


> How do you implement share data (matrix and slices) ? 

Shared data is _all you have_!  You don't pass objects in CORBA, that is
the whole point - distributed shared objects.


> And atomic operations on these data ?

Huh?  This seems to be "value semantic based" and thus not appropriate
in a distributed object environment.  Of couse, if you are hell bent
on doing that, you can, but remember an object is more than it's
state.


> These are of course examples but it is very easy to find features
> that are impossible or complex to write with CORBA (even remote
> object features) and that are very easy with Annex E.

You haven't mentioned any yet.


> Of course, you will be able to implement complex features with
> CORBA, but you're going to write everything with some kind of
> message passing (or asynchronous RPCs) when DSA would provide
> exactly what you are looking for.

CORBA is NOT message passing semantics.  The big thing that DSA would
buy you here is that it is an all Ada solution.  That's it.


> Of course, it could be very interesting to implement DSA on the top of
> CORBA because in some respects, "<DSA> offers functionally everything
> (and more) than <CORBA>" :-)

No it does not.  It does not offer anything like the Interface
Repository, location brokering and auto-startup, persistence, multiple
instances object servers, fail over, transactions, out of the box
interoperation with COM/OLE, ability to transact with Java applets,
incorporation, availability and operational in various browsers
(Netscape), etc., etc., etc.  Come on.  You can't be serious.  DSA
offers a reasonable slice of the core bits of CORBA.  If that is all
you are after, well then, OK, fine.

/Jon
-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com

Re: Garbage Collection in Ada

[Lars Farm]

I said:
> "I'm genuinely puzzled and simply trying to figure out which of the
> conflicting views is right: (1) my limited experience combined with
> others claims that the set of falsely retained pointers is relatively
> small. A small, perhaps negligible problem. or (2) Your claims that this
> is a serious error that likely will make my program fail. The views
> simply don't match. I need more information."

Robert Dewar <dewar@merv.cs.nyu.edu> wrote:
> That is a complete misreading of what I said, please go to an archive and
> reread the thread! I never said that it would "likely" make your program
> fail.

Ok. On doing so (see below) the impression I get is that I should expect
a crash per week.

A program that crashes once a week will be thrown off my disk because I
would consider it seriously broken. A program that crashes once per 3000
years would for many users be a negligible problem. At that rate there
are other bugs that will dominate in any work performed by humans.
Program development is still a human activity. This difference in
magnitude could illustrate the two conflicting views I mentioned. 

By the way, not every program guides missiles or airplanes. Some
programs have extraordinary stability requirements. This type of program
obviously needs more work than others. GC probably also has positive
effects on stability even for this kind of program. Simpler design leads
to fewer bugs, programmer induced faults. There is a break even point.


> Message-ID: <dewar.845505704@merv>

> Finally, there is one disadvantage of a conservative collector
> that you did not mention, namely the possibility that it will
> unexpectedly collect blocks that are in use.


> Message-ID: <dewar.845608007@merv>

> Are there really programs that count on conservative GC working? Well
> perhaps so. For example, Microsoft Word, at least the version I use,
> sometimes leaks memory, and just possibly this is a data dependent
> effect if it uses conservative GC, since it could be that if certain
> words are in your document, you are unlucky and some storage does
> not get freed.
> 
> Similarly you can imagine a command interpretor which works most of the
> time, except when a certain person logs on, because their password
> causes a critical section of storage not to be freed.


> Message-ID: <dewar.845747957@merv>

> I would say that relying on a conservative
>     garbage collector NOT to get unlucky is something that you 
>     can afford to do in one-off programs that don't need to be 
>     reliable, and perhaps even in typical PC software (so what 
>     if the word processor crashes once a week - that seems to be 
>     what people expect anyway).


>Message-ID: <dewar.845247229@merv>

> Just one point, virtual origins are not a problem at all in a proper
> garbage collector, only in approximate "conservative" ones, which are
> not so conservative and are happy to remove blocks in use if virtual
> orgins around. The technique of using virtual origins can perfectly
> well be used in C (see the sources of gigi for an example of this use).


>Message-ID: <dewar.845470185@merv>

> Well if your requirements here are so weak that you find that these
> kind of conservative GC's are acceptable, then what's your problem, 
...
> If you count on  a conservative
> collector to free storage, you have a very unreliable program, since 
> you could find on some particular run that you were just unlucky and
> a junk integer value held a critical large block in memory, causing
> the program to crash and burn. 


> Message-ID: <dewar.845559504@merv>

> 3. You cannot require blocks to disappear, since if you have conservative
> collectors in mind they do not guarantee to free even a single block in
> a given program.


> Message-ID: <dewar.845840549@merv>

  (comparing hashtable hazards favorably to conservative GC hazards)

> Well not so intolerable, there is a big difference btween compiling one
> program slower by a relatively small linear factor, and blowing up in
> an application at runtime because you ran out of memory. As I said

> Message-ID: <dewar.845809398@merv>
> Actually, as I have noted before, I am dubious about real
> applications depending on conservative GC,
















-- 
Lars Farm, lars.farm@ite.mh.se

Re: Garbage Collection in Ada

[Tapani Rundgren]

Laurent Pautet wrote:
> 
> >>>>> "Jon" == Jon S Anthony <jsa@alexandria> writes:
> Jon> payback".  I am clearly not wrong in claiming Orbix/Ada offers
> Jon> functionally everything (and more) than the Distributed System Annex.
Don't agree!
> 
> Yes ? Is it obvious in a client code to handle an exception (print the
> exception message) that has not been declared in a server spec ? Is it
> obvious to ensure remote asynchronous transfert control in CORBA ? How
> do you implement share data (matrix and slices) ? And atomic
> operations on these data ?  These are of course examples but it is
> very easy to find features that are impossible or complex to write
> with CORBA (even remote object features) and that are very easy with
> Annex E. Of course, you will be able to implement complex features
> with CORBA, but you're going to write everything with some kind of
> message passing (or asynchronous RPCs) when DSA would provide exactly
> what you are looking for.
> 
> Of course, it could be very interesting to implement DSA on the top of
> CORBA because in some respects, "<DSA> offers functionally everything
> (and more) than <CORBA>" :-)

Ten points, thanks Laurent!!!!!

-- 
-------------------------------------------------------------
| Tapani Rundgren     Email: Tapani.Rundgren@ein.ericsson.se|
| Bj�rkv�gen 14       Work:  +46 54 29 44 89                |
| S-663 41 Hammar�    Home:  +46 54 52 25 02                |
-------------------------------------------------------------

Re: Garbage Collection in Ada

[Mitch Gart]

Lars Farm (lars.farm@ite.mh.se) wrote:

: Your dislike (apparently shared by other Ada people) for conservative
: collectors has raised a couple of questions that I can not answer. I
: would like to get some feel for how bad this really is. 

: - How large is the probability that this occurs?
: - How large is the probability that this state persists?
: - How large fraction of allocated memory will typically be
:   falsely retained?
: - Is the set of retained blocks growing over time or will it 
:   level out at some point in time? If so where?
: - other?

What I don't like is the idea that the GC will have to go through ALL
data memory (and registers) looking for pointers.  The time it takes
to make a scan is proportional to total memory size rather than proportional
to the number of pointers in use, or proportional to the number of 
heap blocks, or proportional to some other reasonable value.

- Mitch Gart

Re: Garbage Collection in Ada

[Brian Rogoff]

dewar@merv.cs.nyu.edu (Robert Dewar) writes:
   It's certainly on the list as a future possible enhancement, in fact we
   have done quite a bit of work studying the issue of whether we can provide
   a special garbage collected storage pool.

I recall reading a paper on an Ada 95 ODMG binding in which Storage_Pool was 
replaced by a 'Storage_Manager' which could map access types to machine 
addresses and back, and an attribute defined to get this Storage_Manager for 
any access. The goal was persistence, but the scheme could be used for GCed 
accesses too. The idea seemed interesting; what are the pitfalls?

-- Brian

Re: Garbage Collection in Ada

[Jon S Anthony]

In article <dewar.846048434@merv> dewar@merv.cs.nyu.edu (Robert Dewar) writes:

> iJon Anthony says
> 
> "You're being sloppy - you mean I may be part wrong in claiming that
> implementing all the annexes may not have had "that level of payback".
> I am clearly not wrong in claiming Orbix/Ada offers functionally
> everything (and more) than the DSA.  I can guarantee that.  I had the
> choice and have opted for the ORB.  Further, I am not wrong in stating
> that I don't have this sort of option for GC."
> 
> No, that's wrong, they are overlapping capabilities, sure, but it is not
> the case that Orbix/Ada offers functoinally all that DSA offers, but i
> will let the GLADE DSA folks elaborate on this ...

Well, as I have said elsewhere - I've not seen or heard anything that
would make your "denial" true.  I again say that DSA is a smallish bit
of the core of CORBA and has nothing to do or say with all the large
amounts of the rest of the OMA.  IOW, you are still wrong.

/Jon

-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com

Re: Garbage Collection in Ada

[Hans-Juergen Boehm]

Mitch Gart wrote:
> 
> Lars Farm (lars.farm@ite.mh.se) wrote:
> 
> : Your dislike (apparently shared by other Ada people) for conservative
> : collectors has raised a couple of questions that I can not answer
> : ...
> What I don't like is the idea that the GC will have to go through ALL
> data memory (and registers) looking for pointers.  The time it takes
> to make a scan is proportional to total memory size rather than proportional
> to the number of pointers in use, or proportional to the number of
> heap blocks, or proportional to some other reasonable value.
> 
"Conservative" GC is not an all or nothing proposition.  I don't think
anyone would claim that the collector should not take advantage of
easily available information.  It should be easy enough to have an Ada
compiler generate address ranges that contain only statically allocated
pointerfree Ada variables.  Those could easily be skipped by the
collector.  As Fergus Henderson points out this is even easier for
pointerfree heap objects.  On the other hand, there are certain kinds of
pointer information that are harder to come by.  I would argue that it's
often beneficicial to scan the following regions conservatively:

1. C allocated data and stack frames.  The C code may be part of the
language run-time system.

2. Stack frames, and especially the top one.  Generating descriptors is
hard work, error-prone, and takes space.

(Most collectors for a work-station environment actually try to keep the
GC cost per allocation fixed.  If there is too much static data that
must be scanned we grow the heap to reduce collection frequency.  Since
this happens mostly if the heap is a small fraction of the data size,
the space cost is usually tolerable.)
-- 
Standard disclaimer ...
Hans-Juergen Boehm
boehm@mti.sgi.com

Re: Garbage Collection in Ada

[Fergus Henderson]

dewar@merv.cs.nyu.edu (Robert Dewar) writes:

>But this is, so far, a fantasy. The only kind of GC provided by standard
>implementations, at least in my experience, is proper accurate GC, that is
>of course embedded into the compiler or operating system or both.
>
>You can certainly imagine a system that provides conservative garbage
>collection as a standard part of a compiler, or even just a standard
>system library. But I don't know of any such commercial products, do you?

I don't know of any such commercial products, but I do know a
GPL'ed system that provides conservative garbage collection
as a standard part of the implementation: Mercury.
(For more info, see <http://www.cs.mu.oz.au/mercury>).

--
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.

Re: Garbage Collection in Ada

[Fergus Henderson]

mg@dsd.camb.inmet.com (Mitch Gart) writes:

>What I don't like is the idea that the GC will have to go through ALL
>data memory (and registers) looking for pointers.  The time it takes
>to make a scan is proportional to total memory size rather than proportional
>to the number of pointers in use, or proportional to the number of 
>heap blocks, or proportional to some other reasonable value.

With the Boehm GC, memory that does not contain any pointers,
such as strings, bit-vectors, arrays of ints, and so forth,
can be allocated using GC_malloc_atomic() rather than GC_malloc().
If you use GC_malloc_atomic() to allocate data areas that will
not contain pointers, then the GC will not scan those data areas.

--
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.

Re: Garbage Collection in Ada

[Richard A. O'Keefe]

dewar@merv.cs.nyu.edu (Robert Dewar) writes:

>The problem is that it is all too easy to have a global variable around
>that accidentally holds on to a giant structure.

It is also easy to do this with manual allocation.
The practical issue that _I_ see here is that garbage collection
enables "storage profiling" where you can _ask_ "what storage is
being held onto and why?".  There was a very nice paper about a
garbage profiling published in PLDI 96 (I _think_ that was the conference).
Garbage profiling is a valuable development tool, just like time profiling,
and I hope it is soon adopted in many systems.

In a system which achieves economies (if such economies exist) by not
doing garbage collection, it is much harder to provide such facilities.
You can indeed ask where the currently retained blocks were _allocated_
(or at least you can in the memory debugging library I use for C), but
you can't ask "_why_ is this block retained?"

So the bottom line is that when you consider the whole lifecycle instead
of just a single run, garbage collection PLUS garbage profiling is a better
bet than relying on the programmer to be perfect.

>Or for example, depending
>on your implementation, taking the 'Access of one field of one record in
>some big structure may end up holding on to an entire subgraph that you
>do not need.

And again, in a manually managed system, exactly the same situation can
arise, and the programmer may not dare to free the storage manually because
the analysis to prove it safe statically is too hard (or in the case of
someone else's code receiving the 'Access), impossible.

And again, garbage profiling can help with this, whereas no-support-for-gc
means in practice no support for garbage profiling either.

>You may in practice need to be just as careful about adding

>   Junk := null;

>statements to your program as you are now about adding

>   Free (Junk);

>statements to your program now. 

This seems unlikely, because the former is a *local* decision, that
*this* reference is no longer needed, while the latter is a *global*
decision, that *all* references are no longer needed.

I would very much like to see LCLint-style memory checking in a tool
for Ada.

>GC is certainly a magic bullet solution to the problem of accidentally
>freeing storage that should not be freed, but it is NOT a magic bullet
>with respect to not freeing things that should be freed.

But it *is* half of the magic bullet.  The other half is garbage
profiling, which requires at least the same hooks as garbage collection.
If you are concerned about the memory use of your program, you want to
know
 - which objects are being retained after their last real use
 - and which references are keeping the dead blocks around
It _is_ possible to build a development tool for manual management
that tells you which objects are being retained after their last real
use (trace allocation, deallocation, loads, and stores, then inspect
the trace).  But the other half you need is _why_ the objects are
being retained after their last use.

>People who 
>approach a GC language environment with this expectation will be
>disappointed!

This is not an argument *against* automatic garbage collection,
it is an argument *for* garbage profiling.
-- 
Mixed Member Proportional---a *great* way to vote!
Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.

Re: Garbage Collection in Ada

[Robert Dewar]

Lars said replyin to me:

> No, you are confused, if a language expects GC, and if a proper GC is
> incorporated, there is no respect in which the presence of GC inhibits
> optimizations. Where did you get this idea?

From you, <dewar.845470588@merv> about compiler optimization vs
collectors. Since virtual origin is new to me may well be confused. You
said (about C++, conservative GC and virtual origin):


Virtual origins cause trouble only if

(a) you are using a conservative garbage collector of the HJB type
(b) the collector is not part of the implementation, and therefore
	does not understand how to deal with virtual origins.

Read my first senteence above, it is correct!

Re: Garbage Collection in Ada

[Robert Dewar]

iJon Anthony says

"You're being sloppy - you mean I may be part wrong in claiming that
implementing all the annexes may not have had "that level of payback".
I am clearly not wrong in claiming Orbix/Ada offers functionally
everything (and more) than the DSA.  I can guarantee that.  I had the
choice and have opted for the ORB.  Further, I am not wrong in stating
that I don't have this sort of option for GC."

No, that's wrong, they are overlapping capabilities, sure, but it is not
the case that Orbix/Ada offers functoinally all that DSA offers, but i
will let the GLADE DSA folks elaborate on this ...

Re: Garbage Collection in Ada

[Larry Kilgallen]

In article <54kjat$hpn$1@goanna.cs.rmit.EDU.AU>, ok@goanna.cs.rmit.EDU.AU (Richard A. O'Keefe) writes:

> In a system which achieves economies (if such economies exist) by not
> doing garbage collection, it is much harder to provide such facilities.
> You can indeed ask where the currently retained blocks were _allocated_
> (or at least you can in the memory debugging library I use for C), but
> you can't ask "_why_ is this block retained?"

My experience is with the VMS tool which gives an allocation-time
stack trace for any block of memory which is left over at image
exit (or some other convenient time).  Knowing how it was
allocated has generally been sufficient to find the problem.
There may be complicated logic failures on my part which
led to a failure to deallocate, but they are not something
susceptible to automation.

In fact, that might be an argument against use of GC for me,
since I would rather learn that _I_ was not cleaning up right
than learn that the GC did not clean up after me.  At the
same time I failed to clean up memory I might have also failed
to perform some other cleanup activity which is harder to detect.

Yes, I know, the Ada standard does not guarantee any memory will
be returned ever.  The result of that is that if there is a choice
I will gravitate toward implementations which _do_ return memory
so that I have that aid in learning what I have done wrong.

Considering that I make mistakes, perhaps I should always develop
without GC and always run "production" with GC.

Larry Kilgallen

Re: Garbage Collection in Ada

[Richard A. O'Keefe]

dewar@merv.cs.nyu.edu (Robert Dewar) writes:

>Actually, as I have noted before, I am dubious about real applications
>depending on conservative GC, so I can't see it being an integral part
>of a language implementation. For example, I can see putting a conservative
>collector interface into some user library for GNAT, but not into the main
>language library.

A conserative garbage collector was an intrinsic part of Interlisp-D.
All references from the heap were precise, but the stack was scanned
conservatively (in order to make the processing of unboxed floats cheap).
The Quintus Prolog garbage collector had a similar problem with floats,
and took the conservative route.

These were not after-the-fact off-the-shelf collectors for an uncooperative
language, but special purpose collectors co-designed with the implementation
of languages designed for garbage collection.  This kind of conservative
collector worked very well indeed in practice.

-- 
Mixed Member Proportional---a *great* way to vote!
Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.

Re: Garbage Collection in Ada

[Mitch Gart]

Saying that a programmer is sloppy by relying on garbage collection to
help automatically manage memory is kind of like saying they're wimpy 
for using a high level language when they could do everything in assembler.  
Nonsense, I say.  Whenever programmers can make use of a high level 
abstraction which helps them concentrate on the problem domain instead of 
the language and mechanics of programming, that's a good thing, IMHO.

- Mitch Gart

Re: Garbage Collection in Ada

[Robert I. Eachus]

  (This post started yesterday, and I added a section replying to
Richard A. O'Keefe's comments on the Interlisp-D compiler at the end.)

  > In article <199610181934142408603@dialup101-3-15.swipnet.se>,
  > Lars Farm <lars.farm@ite.mh.se> wrote:
  > >- How large is the probability that this occurs?

  > (Where "this" = "conservative GC fails to collect some garbage".)

  > I don't see any way of assigning a numeric probability to it.  That's
  > the main thing that makes *me* nervous about it.  I mean, there's
  > nothing under the programmer's control that can let you know if or when
  > this sort of bug might happen.

    We can make some average case assumptions and see that the
probability of trouble in even moderate sized programs is pretty high.
The probability a block is marked as uncollectable is the probability
that any space already in the uncollectable set has something that
will be seen as a pointer to that block.  Assuming (BIG assumption)
that all bit patterns are equally likely, and 32-bit pointers, the
probability that any word is seen as locking a block is
1/2**32/(addresses per block).  If we use R to indicate the number of
words in the required (uncollectable) space not used for real
pointers, C as the number of addresses in the collectable space and B
as the (average) number of addresses per block, then the birthday
effect takes over when R*C*B approaches 2**32.  Basically this means
that conservative GCs become useless when available memory times
required memory times block size is of the same order as the number of
different pointers.

    To take it one step further, if your program requires 16K of
non-pointer "random" data space on a 32-bit addressable machine, even
with small allocated objects, a "conservative" collector is so much
junk.  (Uncollected garbage will on average lock down more uncollected
garbage, and the amount of uncollected garbage will grow without
bound.)

    What about 64-bit machines?  Now another factor jumps out to bite
you.  Bit patterns in memory are not random.  In particular, low
numbers are favored, and are more likely to correspond to actual
memory locations.  On a machine with a 64-bit address space, my guess
is that a conservative collector is useful up to a megabyte of
non-pointer live data.

    Now lets go with an absolute best case scenario for long lived
systems.  The application has exactly one word of non-pointer storage
that is non-garbage, points to a valid heap address, and doesn't
change.  Each dyanamically allocated object also contains one
non-pointer word and a pointer that is sometimes non-null.  It is easy
to prove that over time more and more of the store will not be
available, and eventually you will run out of storage.  So
"conservative" collectors are of no use in applications where you want
to do your best to keep the application running.  If you don't
believe the above, write the program--I'll make sure you have a good
enough RNG--and run it.  Memory consumption (you measure it after GC
runs of course) will stay low initially, but eventually you will lock
in some garbage, then memory consumption rises rapidly.  You probably
turn the program off before it crashes because you are spending most
of your time in garbage collection.

   This lesson was learned and learned well in the early days of LISP
implementations.  Systems attempting to use conservative collectors
eventually died.  I remember one incident on a PDP-1 at MIT where this
happened in under an hour.  (The machine had 16K of 18-bit memory, and
a large--for 1964--drum that could be directly addressed.  The LISP
implementation stored all objects on the drum, using if I remember
correctly 22-bit pointers, but the drum had less than a million
words.)

In article <54mrhq$bqn$1@goanna.cs.rmit.EDU.AU> ok@goanna.cs.rmit.EDU.AU (Richard A. O'Keefe) writes:

  > A conserative garbage collector was an intrinsic part of
  > Interlisp-D.  All references from the heap were precise, but the
  > stack was scanned conservatively (in order to make the processing
  > of unboxed floats cheap).  The Quintus Prolog garbage collector
  > had a similar problem with floats, and took the conservative
  > route.

   This does not have the same abysmal characteristics.  As long as
the heap and stack are treated differently, the worst case behavior is
that you expect the amount of junk locked to depend on the number of
non-pointer values on the stack (and the size of heap structures), not
how long the program has been running.

   This particular "semi-conservative" GC style fell out of favor
becuase you had to munge records copied from the stack to the heap,
and vice-versa and special case offsets on where the object was
currently located.

   The better solution was to always store and GC) records and arrays
the same way no matter where they are located (usually starting with a
one-word pointer to a GC thunk), add a counter to the stack frame and
put all pointers at the head of the data section.  The GC code turns
out to be very simple, you can compact if you wish, and all you lose
is one word per heap object and two words per complex object on the
stack.

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...
--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...

Re: Garbage Collection in Ada

[Hans-Juergen Boehm]

There are many serious problems with this analysis, including the fact
that it's blatantly inconsistent with any recent practical experience.
I'll reply to the more theoretical ones here.  Anyone who has any doubts
about this is more than welcome to try the experiment.  A suitable
collector for C can br found in:

http://reality.sgi.com/employees/boehm_mti/gc_source/gc.tar.gz.

 Robert I. Eachus wrote:
>   > In article <199610181934142408603@dialup101-3-15.swipnet.se>,
>   > Lars Farm <lars.farm@ite.mh.se> wrote:
>   > >- How large is the probability that this occurs?
> 
>   > (Where "this" = "conservative GC fails to collect some garbage".)
> 
>     We can make some average case assumptions and see that the
> probability of trouble in even moderate sized programs is pretty high.
> The probability a block is marked as uncollectable is the probability
> that any space already in the uncollectable set has something that
> will be seen as a pointer to that block.  Assuming (BIG assumption)
> that all bit patterns are equally likely, and 32-bit pointers, the
> probability that any word is seen as locking a block is
> 1/2**32/(addresses per block).
That is a big assumption.  In fact on modern machines valid heap
addresses generally occur rarely in other positions.  Small integers are
rarely valid heap addresses.  Neither are floating point numbers or
character strings.  More importantly a good conservative collector will
allocate around previously seen bogus pointers, reducing the probability
substantially further.  See my PLDI 93 paper for measurements.  This is
however not the main problem with the analysis. 
> If we use R to indicate the number of
> words in the required (uncollectable) space not used for real
> pointers, C as the number of addresses in the collectable space and B
> as the (average) number of addresses per block, then the birthday
> effect takes over when R*C*B approaches 2**32.
It seems to me that either C should be expressed in objects, or B should
disappear.  A minor point.
> Basically this means
> that conservative GCs become useless when available memory times
> required memory times block size is of the same order as the number of
> different pointers.
No.  That is when you would start to see SOME memory accidentally
retained if you ignored the above arguments.  That doesn't make it
unusable.  See below.
> 
>     To take it one step further, if your program requires 16K of
> non-pointer "random" data space on a 32-bit addressable machine, even
> with small allocated objects, a "conservative" collector is so much
> junk.  (Uncollected garbage will on average lock down more uncollected
> garbage, and the amount of uncollected garbage will grow without
> bound.)
NO!  NO!  And this is the crucial point.  If you have 16K of junk and a
256K heap, unusually distributed data and a dump collector, you will see
a bogus pointer.  (In reality the constants are quite a bit bigger,
though application dependent.)  If that bogus pointer pins another 16K
of junk, you'll lock down more memory, etc. etc.  But bogus pointers
raely pin down another 16K of junk.  A random pointer into a balanced
tree pins down something like 2 nodes on average.  Wentworth published a
paper about conservative collection in a fully utilized 16-bit address
space a while back.  It worked fine for many appllications and not for
others.  This is discussed more in my PLDI 93 paper.

Applications written for conservative collection, even in C can easily
avoid putting much "junk" into heap objects, further reducing this
effect.  It is normally easy to allocate a large fraction of the heap
using pointer-free allocation primitives.  For a language like Ada, it's
easy to supply more detailed layout information for heap objects.
That's cheap.  Stack layout information is harder.

>     What about 64-bit machines?  Now another factor jumps out to bite
> you.  Bit patterns in memory are not random.  In particular, low
> numbers are favored, and are more likely to correspond to actual
> memory locations.
No.  64-bit machines of which I'm aware allocate the heap starting at
something like 2**32 by default.  The collecting allocator could place
it wherever it wants.

> On a machine with a 64-bit address space, my guess
> is that a conservative collector is useful up to a megabyte of
> non-pointer live data.
I've routinely run fairly long running applications with more than that
on 32-bit machines.  So have a number of other readers, I suspect.

> 
>     Now lets go with an absolute best case scenario for long lived
> systems.  The application has exactly one word of non-pointer storage
> that is non-garbage, points to a valid heap address, and doesn't
> change.  Each dyanamically allocated object also contains one
> non-pointer word and a pointer that is sometimes non-null.  It is easy
> to prove that over time more and more of the store will not be
> available, and eventually you will run out of storage.
THIS IS OBVIOUSLY FALSE.  Consider the case in which each pointer points
to a NIL object, and the junk in the accidentally referenced object and
the NIL object points outside the heap area.  (Our allocator would in
fact allocate around the original nonchanging value.  Unchanging values
are easy.)

> So
> "conservative" collectors are of no use in applications where you want
> to do your best to keep the application running.  If you don't
> believe the above, write the program--I'll make sure you have a good
> enough RNG--and run it.  Memory consumption (you measure it after GC
> runs of course) will stay low initially, but eventually you will lock
> in some garbage, then memory consumption rises rapidly.  You probably
> turn the program off before it crashes because you are spending most
> of your time in garbage collection.
Please try it for yourself.  Until April I was reading my mail on a
conservatively garbage collected system that couldn't possibly have
stayed up for weeks by this chain of reasoning.  (It did.)  Many other
systems that are in routine use couldn't possibly work either.

-- 
Standard disclaimer ...
Hans-Juergen Boehm
boehm@mti.sgi.com

Re: Garbage Collection in Ada

[Jon S Anthony]

In article <32701284.167E@mti.sgi.com> Hans-Juergen Boehm <boehm@mti.sgi.com> writes:

Lots of good stuff about why Robert Eachus' "theory of conservative GC" is
so far in the weeds you would have trouble finding it with the Space
Telescope.

For me, the most salient points are:

> I've routinely run fairly long running applications with more than that
> on 32-bit machines.  So have a number of other readers, I suspect.

and

> Please try it for yourself.  Until April I was reading my mail on a
> conservatively garbage collected system that couldn't possibly have
> stayed up for weeks by this chain of reasoning.  (It did.)  Many other
> systems that are in routine use couldn't possibly work either.

Exactly.  The "theory" just doesn't account for the observed facts.
Hence, anyone who is even remotely "scientifically motivated" would
have to just toss it on the incorrect theory junk pile.  While the
"science" in "computer science" has always struck me as dubious (at
best), one would hope that there would be at least _some_ adherence to
this basic principle.

/Jon

-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com

Re: Garbage Collection in Ada

[Richard Riehle]

I find it odd that, in all this discussion of Garbage Collection,
we have not had any mention of System.Storage_Pools (ALRM 13.11).

Although I realize this is not the panacea for all garbage collection
problems, those who have suggested that the run-time executive would
have to wander blindly through all of a program's memory to determine
if some wayward pointer is lurking in some hidden corner, might consider,
when such issues are critical, setting up a storage pool controlled
via Ada.Finalization. 

I, for one, am quite pleased that the designers of Ada 95 included this
capability, and sometimes wonder how many of my colleagues in the Ada
community have examined this feature closely enough to realize that it
is does have some virtue.

While it is true that Root_Storage_Pool is derived
from Ada.Finalization.Limited_Controlled, this should not be
a particular hardship when control over the storage pool,
and automatic garbage collection are essential to a given design.

Richard Riehle
richard@adaworks.com

Re: Garbage Collection in Ada

[Robert I. Eachus]

In article <JSA.96Oct25141553@alexandria> jsa@alexandria (Jon S Anthony) writes:

  > Exactly.  The "theory" just doesn't account for the observed facts.
  > Hence, anyone who is even remotely "scientifically motivated" would
  > have to just toss it on the incorrect theory junk pile.  While the
  > "science" in "computer science" has always struck me as dubious (at
  > best), one would hope that there would be at least _some_ adherence to
  > this basic principle.

   My observations are based on simulations which in some cases run
more than a week--of CPU time.  The characteristics of my experience
are: heap allocated objects containing a large amount of non-pointer
state, including random values and in some cases the state of a random
number generator.  This is the worst case environment for a
conservative collector.

    Hans-Juergen Boehm described a much different environment:

> Please try it for yourself.  Until April I was reading my mail on a
> conservatively garbage collected system that couldn't possibly have
> stayed up for weeks by this chain of reasoning.  (It did.)  Many other
> systems that are in routine use couldn't possibly work either.
   
     Heap memory values in such an environment will tend to contain
valid pointer values and substrings of mostly English ASCII text.  It
is possible that in Boehm's environment, no legal pointer corresponds
to any printable substring.

     So yes your milage WILL vary, but in the simulation business,
conservative collectors are an extremely poor choice.  (And what makes
them so bad is not that they fail often, but that when they fail three
days into a week long run, you are up the proverbial creek.)

--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...

Re: Garbage Collection in Ada

[Jon S Anthony]

In article <Pine.GSO.3.95.961027083501.11380C-100000@nunic.nu.edu> Richard Riehle <rriehle@nunic.nu.edu> writes:

> I find it odd that, in all this discussion of Garbage Collection,
> we have not had any mention of System.Storage_Pools (ALRM 13.11).

Actually, they have been mentioned several times - by me and a couple
others.


> Although I realize this is not the panacea for all garbage collection
> problems, those who have suggested that the run-time executive would
> have to wander blindly through all of a program's memory to determine
> if some wayward pointer is lurking in some hidden corner, might consider,
> when such issues are critical, setting up a storage pool controlled
> via Ada.Finalization.

Or (as has been mentioned) tying (sp?) instances of GC (possibly
different flavors, where each could be more appropriate to the target
type) to specific pools.  Either implementation defined or possibly
even user defined pools.


> I, for one, am quite pleased that the designers of Ada 95 included this
> capability, and sometimes wonder how many of my colleagues in the Ada
> community have examined this feature closely enough to realize that it
> is does have some virtue.

It is a "god send" for those of us trying to put some GC like storage
management into specific applications.  This is the route that I ended
up going down - finalization stuff is largely _irrelevant_.


> While it is true that Root_Storage_Pool is derived
> from Ada.Finalization.Limited_Controlled, this should not be
> a particular hardship when control over the storage pool,
> and automatic garbage collection are essential to a given design.

The keys are being able to

a) tie an access type to a pool
b) define a type which cannot be allocated except by user defined constructor
   (limited type with unknown discriminants).  This gurantees that a) is the
   only access type a client can use for the type.
c) ability to redefine _new_ for the pool

to a much lesser extent: d) ability to redefine manual deallocation for pool.

Finalization for the pool could also be useful (though only in special
cases)

/Jon
-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com

Re: Garbage Collection in Ada

[Hans-Juergen Boehm]

Robert I. Eachus wrote:
> 
>    My observations are based on simulations which in some cases run
> more than a week--of CPU time.  The characteristics of my experience
> are: heap allocated objects containing a large amount of non-pointer
> state, including random values and in some cases the state of a random
> number generator.  This is the worst case environment for a
> conservative collector.
My experience has been that for the vast majority of applications,
conservative collection behaves well and spurious retention is not an
issue.  All evidence suggests that they are perfectly stable over long
runs.  You will occasionally see spurious retention.  But the expected
number of additional spurious pointers reachable from a spuriously
retained object is < 1, so things stabilize.

Every once in a while I hear about an application for which
that's not true.  Typically these store large amounts of more or less
random data in the heap.  The state of a single random number generator
(or 100 random number generators) is not an issue.  2 megabytes of
compressed bitmaps are an issue.  In all such cases of which I am aware
there was a straightforward solution to the problem:  Inform the
collector that these objects contain no pointers, or contain pointers in
only a few positions.  In one case it was easier to change the data
format slightly.  I believe all of the modifications were trivial
compared to the difficulty of using manual deallocation.

Again, I believe all of this is largely irrelevant for an Ada
implementation.  If you are concerned about this issue, it's easy to
allocate objects with the correct layout information for HEAP objects.
The hooks currently in our collector are probably even sufficient to
implement this.

> 
>     Hans-Juergen Boehm described a much different environment:
> 
> > Please try it for yourself.  Until April I was reading my mail on a
> > conservatively garbage collected system that couldn't possibly have
> > stayed up for weeks by this chain of reasoning.  (It did.)  Many other
> > systems that are in routine use couldn't possibly work either.
> 
>      Heap memory values in such an environment will tend to contain
> valid pointer values and substrings of mostly English ASCII text.  It
> is possible that in Boehm's environment, no legal pointer corresponds
> to any printable substring.

Actually bitmaps are also quite common.  Character strings and some
bitmaps were allocated with a pointerfree allocation primitive, so this
wasn't an issue.  (This was easy to arrange, since they were allocated
in very few distinct places.)  Thread stacks, static data, and mixed
structures in the heap were scanned conservatively.  The Cedar
environment was (and probably still is) used for a number of
applications including some fairly long-running CPU-intensive ones.


-- 
Hans-Juergen Boehm
boehm@mti.sgi.com

Re: Garbage Collection in Ada

[James Rogers]

Jonas Nygren wrote:
> 
> To me GC solves the problem of deallocation when there are two or more
> references
> to the same object. Without GC this is a difficult problem to solve,
> specially so
> in very large programs, where you have the problem of possible dangling
> pointers.
> 
> I have tried Java a bit and recommend it to NO-GC advocates, it is
> rather
> refreshing not to have to think about deallocation. You should try it.
> 
> /jonas

The solution in non-garbage collection implementations is to use
"smart pointers" or reference counting.  An excellent example of
how this is done in Ada comes from John English's new textbook

"Ada 95: The Craft of Object-Oriented Programming"

His example is:

----------------------------------------------------------------------------
--
--   File:    je.ads
--   Purpose: Ultimate parent of all example packages (specification)
--   Author:  John English (je@brighton.ac.uk)
--
--   This code is from "Ada 95: The Craft of Object-Oriented
Programming"
--   by John English (Prentice Hall 1997). Copyright (c) John English.
--   Permission is granted to copy and distribute this file for
--   non-commercial use only.
--
----------------------------------------------------------------------------

package JE is
    -- an empty package!
end JE;


----------------------------------------------------------------------------
--
--   File:    je-pointers.ads
--   Purpose: Generic "smart pointers" package (specification)
--   Author:  John English (je@brighton.ac.uk)
--
--   This code is from "Ada 95: The Craft of Object-Oriented
Programming"
--   by John English (Prentice Hall 1997). Copyright (c) John English.
--   Permission is granted to copy and distribute this file for
--   non-commercial use only.
--
----------------------------------------------------------------------------

with Ada.Finalization;
generic
    type Item_Type(<>) is limited private;
    type Access_Type   is access Item_Type;
package JE.Pointers is
    type Pointer_Type is private;

    function Pointer (Value   : Access_Type)  return Pointer_Type;
    function Value   (Pointer : Pointer_Type) return Access_Type;

private
    type Reference_Counted_Object is
        record
            Value : Access_Type;
            Count : Natural;
        end record;
    type Reference_Counted_Pointer is access Reference_Counted_Object;

    type Pointer_Type is new Ada.Finalization.Controlled with
        record
            Pointer : Reference_Counted_Pointer;
        end record;

    procedure Finalize (Object : in out Pointer_Type);
    procedure Adjust   (Object : in out Pointer_Type);
end JE.Pointers;



----------------------------------------------------------------------------
--
--   File:    je-pointers.adb
--   Purpose: Smart pointers package (body)
--   Author:  John English (je@brighton.ac.uk)
--
--   This code is from "Ada 95: The Craft of Object-Oriented
Programming"
--   by John English (Prentice Hall 1997). Copyright (c) John English.
--   Permission is granted to copy and distribute this file for
--   non-commercial use only.
--
----------------------------------------------------------------------------

with Ada.Unchecked_Deallocation, Ada.Text_IO;
package body JE.Pointers is
    procedure Delete_Item is
                new Ada.Unchecked_Deallocation (Item_Type, Access_Type);
    procedure Delete_Pointer is
                new Ada.Unchecked_Deallocation
(Reference_Counted_Object,
                                                Reference_Counted_Pointer);

    function Pointer (Value : Access_Type) return Pointer_Type is
        Object : Pointer_Type;
    begin
        if Object.Pointer /= null then
            Delete_Item (Object.Pointer.Value);
        else
            Object.Pointer := new Reference_Counted_Object;
        end if;
        Object.Pointer.all := (Value => Value, Count => 1);
        return Object;
    end Pointer;

    function Value (Pointer : Pointer_Type) return Access_Type is
    begin
        if Pointer.Pointer = null then
            return null;
        else
            return Pointer.Pointer.Value;
        end if;
    end Value;

    procedure Finalize (Object : in out Pointer_Type) is
    begin
        Ada.Text_IO.Put ("Finalising pointer...");
        if Object.Pointer /= null then
            Object.Pointer.Count := Object.Pointer.Count - 1;
            if Object.Pointer.Count = 0 then
                Ada.Text_IO.Put (" reference count = 0, deleting");

                Delete_Item (Object.Pointer.Value);
                Delete_Pointer (Object.Pointer);
            else
                Ada.Text_IO.Put (" reference count > 0");
            end if;
        else
            Ada.Text_IO.Put (" null, ignored");
        end if;
        Ada.Text_IO.New_Line;
    end Finalize;

    procedure Adjust (Object : in out Pointer_Type) is
    begin
        Ada.Text_IO.Put ("Copying pointer...");
        if Object.Pointer /= null then
            Object.Pointer.Count := Object.Pointer.Count + 1;   
        else
            Ada.Text_IO.Put (" null, ignored");
        end if;
        Ada.Text_IO.New_Line;
    end Adjust;
end JE.Pointers;

-- 
Jim Rogers
*************************************************************
Team Ada

Re: Garbage Collection in Ada

[Jon S Anthony]

In article <32771A0A.32F6@ehs.ericsson.se> Jonas Nygren <ehsjony@ehs.ericsson.se> writes:

> I don't understand this. Can storage pools replace automatic garbage
> collection?  How should one use storage pools to accomplish this?

No, of course not.  But you can, on an application specific basis, get
reasonable forms of "real" GC.  But it is tied to a specific pool and
specific types attached to that pool.


> To me GC solves the problem of deallocation when there are two or
> more references to the same object. Without GC this is a difficult
> problem to solve, specially so in very large programs, where you
> have the problem of possible dangling pointers.

Yeah, and?  The point is if you can get complete control over the
allocation and have a true and complete set of roots (depends on
application) then you can do it.  Just like implementation provided GC
can in the general case.  What's your point?


> I have tried Java a bit and recommend it to NO-GC advocates, it is
> rather refreshing not to have to think about deallocation. You
> should try it.

What makes you think Java is special here.  Just try SmallTalk,
Eiffel, Sather (conservative GC), any Lisp, etc.  What's your point?

/Jon

-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com

Re: Garbage Collection in Ada

[Jonas Nygren]

Jon S Anthony wrote:
> 
> In article <Pine.GSO.3.95.961027083501.11380C-100000@nunic.nu.edu> Richard Riehle <rriehle@nunic.nu.edu> writes:

<snip> 

> > While it is true that Root_Storage_Pool is derived
> > from Ada.Finalization.Limited_Controlled, this should not be
> > a particular hardship when control over the storage pool,
> > and automatic garbage collection are essential to a given design.
> 
> The keys are being able to
> 
> a) tie an access type to a pool
> b) define a type which cannot be allocated except by user defined constructor
>    (limited type with unknown discriminants).  This gurantees that a) is the
>    only access type a client can use for the type.
> c) ability to redefine _new_ for the pool
> 
> to a much lesser extent: d) ability to redefine manual deallocation for pool.
> 
> Finalization for the pool could also be useful (though only in special
> cases)
> 

I don't understand this. Can storage pools replace automatic garbage
collection?
How should one use storage pools to accomplish this?

To me GC solves the problem of deallocation when there are two or more
references
to the same object. Without GC this is a difficult problem to solve,
specially so
in very large programs, where you have the problem of possible dangling
pointers.

I have tried Java a bit and recommend it to NO-GC advocates, it is
rather 
refreshing not to have to think about deallocation. You should try it.

/jonas

Re: Garbage Collection in Ada

[Brian Rogoff]

jsa@alexandria (Jon S Anthony) writes:
   Richard Riehle <rriehle@nunic.nu.edu> writes:
   > While it is true that Root_Storage_Pool is derived
   > from Ada.Finalization.Limited_Controlled, this should not be
   > a particular hardship when control over the storage pool,
   > and automatic garbage collection are essential to a given design.

   The keys are being able to

   a) tie an access type to a pool
   b) define a type which cannot be allocated except by user defined 
      constructor (limited type with unknown discriminants).  This 
      gurantees that a) is the only access type a client can use for the type.

   c) ability to redefine _new_ for the pool

   to a much lesser extent: 

   d) ability to redefine manual deallocation for pool.

   Finalization for the pool could also be useful (though only in special
   cases)

I mentioned that the ODMG Ada 95 binding paper, which I can no longer find on 
the web, had a discussion of storage pools, and suggested that a very similar 
feature be designed which was like Storage_Pools except that it supported 
user definable dereferencing and rereferencing of access types. This was 
used for persistence and GC.

-- Brian

Re: Garbage Collection in Ada

[Jonas Nygren]

Mitch Gart wrote:
  
  Jonas Nygren (ehsjony@ehs.ericsson.se) wrote:
  
  (snip)
  
  : package Collected is
  
  :    type Object is
  :       tagged record
  :          Reference_Count : Natural;
  :       end record;
  :    type Object_Access is access all Object'Class;
  
  :    type Handle is new Ada.Finalization with
  :       record
  :          Ref : Object_Access;
  :       end record;
  
  : end Collected;
  
  (snip)
  
  This suffers from several problems:
  
  - If you provide a function to do allocations,
  
      function Allocate_Obj return Handle;
  
    and users use this function, things work well, but if a user calls
    "new Object" directly things don't work at all.
  
  - Obj1 := Obj2;      doesn't work because the reference count value is
    copied.  If Obj2's count is 3 before the assignment, after the
assignment
    Obj1's count is also 3 which is probably wrong.

Mitch,

you are quite correct. The Object part should be in the private
part of the package and only Handle and its derivatives should
be in the visible part. This have the effect that type extension
can only be done in child packages. Pehaps I should have shown that
too in my example but I thought it might have caused information 
overload.

By requiring type extension in child packages one lose the capability
of hiding implementation of the parent implementation for the derived
type. I think this just serves to strengthen the argumentation in 
favor for GC in Ada.

/jonas

Re: Garbage Collection in Ada

[Mitch Gart]

Jonas Nygren (ehsjony@ehs.ericsson.se) wrote:

(snip)

: package Collected is

:    type Object is
:       tagged record
:          Reference_Count : Natural;
:       end record;
:    type Object_Access is access all Object'Class;

:    type Handle is new Ada.Finalization with
:       record
:          Ref : Object_Access;
:       end record;

: end Collected;

(snip)

This suffers from several problems:

- If you provide a function to do allocations,

    function Allocate_Obj return Handle;

  and users use this function, things work well, but if a user calls
  "new Object" directly things don't work at all.  

- Obj1 := Obj2;      doesn't work because the reference count value is
  copied.  If Obj2's count is 3 before the assignment, after the assignment
  Obj1's count is also 3 which is probably wrong.

Mitch Gart

Re: Garbage Collection in Ada

[Jon S Anthony]

In article <3278C69B.310F@ehs.ericsson.se> Jonas Nygren <ehsjony@ehs.ericsson.se> writes:

> Mitch Gart wrote:
>   
>   Jonas Nygren (ehsjony@ehs.ericsson.se) wrote:
>   
>   (snip)
>   
>   This suffers from several problems:
>   
>   - If you provide a function to do allocations,
>   
>       function Allocate_Obj return Handle;
>   
>     and users use this function, things work well, but if a user calls
>     "new Object" directly things don't work at all.
>   
>   - Obj1 := Obj2;      doesn't work because the reference count value is
>     copied.  If Obj2's count is 3 before the assignment, after the
> assignment
>     Obj1's count is also 3 which is probably wrong.
> 
> Mitch,
> 
> you are quite correct. The Object part should be in the private
> part of the package and only Handle and its derivatives should
> be in the visible part. This have the effect that type extension
> can only be done in child packages. Pehaps I should have shown that
> too in my example but I thought it might have caused information 
> overload.

This shows up (at least in part) why for this sort of stuff (constructing
GC behavior within the language - on a per app/per type basis) should
use limited types (no assignment goof up) with unknown discriminants
(user/client _can't_ call "new Object", but _must_ use the constructor).

/Jon
-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com

Re: Garbage Collection in Ada

[Jon S Anthony]

In article <01bbc76a$92d34240$829d6482@joy.ericsson.se> "Jonas Nygren" <ehsjony@ehs.ericsson.se> writes:

> What's my point? It's very simple, Ada needs garbage collection!

Well, I can't argue with that.

> It seems as if my command of the english language is not sufficient
> to bring my message about and I am terribly weak when it comes to
> being multi-lingual. The only other language I would even attempt to
> express in writing is Swedish. If this would help you, Jon, please let
> me know, and I'll put a direct answer to you in Swedish.

:-)  Believe me you are much better at English than I could hope to be
at Swedish!

/Jon
-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com

Re: Garbage Collection in Ada

[Matthew Heaney]

In article <E055IC.26I.0.-s@inmet.camb.inmet.com>, mg@harp.camb.inmet.com
(Mitch Gart) wrote:

>: package Collected is
>
>(snip)
>
>This suffers from several problems:
>
>- If you provide a function to do allocations,
>
>    function Allocate_Obj return Handle;
>
>  and users use this function, things work well, but if a user calls
>  "new Object" directly things don't work at all.  
>
>- Obj1 := Obj2;      doesn't work because the reference count value is
>  copied.  If Obj2's count is 3 before the assignment, after the assignment
>  Obj1's count is also 3 which is probably wrong.

Actually, Mitch's example points out what I feel is an omission in the
langauge: the ability to overload the access object deference operator
"all".

(Yeah, yeah, I already _know_ it's not an operator.  My point is that I
want it to be.)

I like having the control of finalization of objects, but I would also like
the ability to finalize an access object, so that when its lifetime ends I
can decrement a reference count.

The previous examples in this thread do that, but there's a large syntactic
difference between manipulating an Ada access object and those that aren't
access objects.  I don't want to have to do any work to get at the "real"
access object component of a (controlled) handle object.

I want to be able to define a type that's a subtype of
Finalization.Controlled, and define primitive operations for it so that
it's syntactically identical to an access type.  I don't want the user of
my "access type" to have to do anything different than he would have do to
when manipulating a "normal" access type.

So I want to be able to do this

   type T is ...;
   type TA is private;

   function "new" (O : T) return TA;
   function "all" (O : TA) return T;
private
   type T_Rep is
      record
         O : T;
         Count : Natural;
      end record;

   type TA_Rep is access T_Rep;

   type TA is new Finalization.Controlled with
      record
         Rep : TA_Rep;
      end record;
...
   O : TA := ...;
begin
      ... O.all ...   


If this package were generic (with T as its generic formal type), then I
suppose this access type would be very reusable.

Whatever else you might think about C++, you have to admit that letting the
programmer define operators for his class-types, to make them look like
built-in types, is very nice.

Language designers: any reason why overloading "all" would be too hard?

--------------------------------------------------------------------
Matthew Heaney
Software Development Consultant
mheaney@ni.net
(818) 985-1271

Re: Garbage Collection in Ada

[Robert A Duff]

In article <mheaney-ya023280000311962335300001@news.ni.net>,
Matthew Heaney <mheaney@ni.net> wrote:
>Language designers: any reason why overloading "all" would be too hard?

Well, functions return values (or constant objects, if you want to be
precise in Ada 95 terms), whereas "P.all" returns a variable (if P is an
access-to-variable type).  So it wouldn't work.  C++ has references,
which are more like variables.  (By the way, I find the notation ".all"
to be rather ugly -- I prefer Pascal's "^", or even C's "*".)

I agree with your point, though.  It's not just ".all", but many
notations in Ada are predefined, so you can't make a user-defined
abstraction that "looks like" a predefined one.  For example, suppose
you want to have an associative array data type, which is just like a
normal array, except that the index type can be something like String.
You can do that, but you have to use a different notation for array
indexing, aggregates, etc.  Or, suppose you want to make a
multi-precision integer type, which is just like a normal integer,
except it won't overflow on large numbers.  Well, you can't use numeric
literals, case statements, etc.

The danger of course is that if the user defines a numeric literal to do
something weird (with side effects!), then the program is harder to
understand.  But that problem already exists in Ada for "+", for
example.  The answer is for the programmer to use good taste when
redefining "+".

- Bob

Re: Garbage Collection in Ada

[Norman H. Cohen]

Robert A Duff wrote:
 
> In article <mheaney-ya023280000311962335300001@news.ni.net>,
> Matthew Heaney <mheaney@ni.net> wrote:
> >Language designers: any reason why overloading "all" would be too hard?
> 
> Well, functions return values (or constant objects, if you want to be
> precise in Ada 95 terms), whereas "P.all" returns a variable (if P is an
> access-to-variable type).  So it wouldn't work.  

The same scheme that Ada 95 uses to allow programmers to redefine the
behavior of "new" could have been used to allow redefinition of the
behavior of ".all".  The type System.Storage_Pools.Root_Storage_Pool
could have been given another primitive operation to be overridden by
those defining their own storage-pool types:

   procedure Dereference
      (Pool                     : in out Root_Storage_Pool;
       Storage_Address          : in out Address;
       Storage_Size_In_Elements : in Storage_Elements.Storage_Count;
       Alignment                : in Storage_Elements.Storage_Count);

The compiler would generate code for .all that would compute the nominal
address of the designated object and invoke Dereference, passing that
address to Storage_Address.  Dereference would, in some cases, replace
that address with a different one.  (Unlike Allocate, Deallocate, and
Storage_Size, Dereference would not be abstract; it would have a default
implementation that does nothing.  People not interested in redefining
the behavior of ".all" could ignore it.  I'm not sure why the last two
parameters are really needed; I'm just being "foolishly consistent" with
Allocate and Deallocate.)

One potential use of Dereference would be to recognize "forwarding
pointers" in a storage pool with background compactifying garbage
collection.  As objects are copied from the current area into the new,
compacted area, the old copy of an object is replaced by a special value
indicating that the object has been moved, followed by the new address
of the object.  Dereference would return without doing anything for
objects that had not been moved, and would return the address indicated
by the forwarding pointer for objects that had been moved.

Another potential use of Dereference would be swizzling:  A data
structure consisting of many nodes pointing at each other would be
represented partly in a persistent store (e.g. on a disk) with some sort
of persistent pointers (e.g. disk addresses or indices) and partly in
memory.  Nodes would be lazily brought into memory as needed.  One
possible implementation is to use values of type Address to encode
persistent pointers.  There would be a hash table mapping persistent
pointers to in-memory objects.  Dereference would be passed an encoded
persistent pointer through its Storage_Address parameter and would look
up that perisistent pointer in the hash table.  If there was not already
an entry for that persistent pointer in the hash table, Dereference
would read the node from the persistent store into memory and create a
hash-table entry mapping the persistent pointer to the new in-memory
address.  Then, in any event, Dereference would replace its
Storage_Address parameter with the in-memory address of the object
(either the one that was found already in the hash table or the one that
it just inserted there because it had not been in the hash table).

As a final example, Dereference could be used to implement a storage
pool with *checked* deallocation.  The storage pool would implement a
pointer to X as a pointer to a pointer to X.  Access-value assignment
would have the effect of creating multiple copies to the
pointer-to-pointer-to X.  Deallocation would consist of freeing the
storage for X itself and setting the direct pointer to X to null. 
Dereference would implement the extra level of indirection and also
check that the address it is passed is not the address of a null pointer
(indicating an attempt to dereference a pointer to a deallocated
object).

--
Norman H. Cohen
mailto:ncohen@watson.ibm.com
http://www.research.ibm.com/people/n/ncohen

Re: Garbage Collection in Ada

[Brian Rogoff]

"Norman H. Cohen" <ncohen@watson.ibm.com> writes:
   Robert A Duff wrote:

   > In article <mheaney-ya023280000311962335300001@news.ni.net>,
   > Matthew Heaney <mheaney@ni.net> wrote:
   > >Language designers: any reason why overloading "all" would be too hard?
   > 
   > Well, functions return values (or constant objects, if you want to be
   > precise in Ada 95 terms), whereas "P.all" returns a variable (if P is an
   > access-to-variable type).  So it wouldn't work.  

   The same scheme that Ada 95 uses to allow programmers to redefine the
   behavior of "new" could have been used to allow redefinition of the
   behavior of ".all".  The type System.Storage_Pools.Root_Storage_Pool
   could have been given another primitive operation to be overridden by
   those defining their own storage-pool types:

      procedure Dereference
	 (Pool                     : in out Root_Storage_Pool;
	  Storage_Address          : in out Address;
	  Storage_Size_In_Elements : in Storage_Elements.Storage_Count;
	  Alignment                : in Storage_Elements.Storage_Count);

This looks almost exactly like a proposal I read (a long time ago, on a web 
page long since forgotten) for adding persistence to Ada 95. The main 
difference is that Storage_Address was of type "Access_Type", which was a 
generic formal parameter to the Storage_Pools package, and another parameter 
to Dereference was a System.Address type. There was also a Rereference 
procedure for converting System.Address types back to Access_Types.

   <... snipping description of some the things this might allow ...>

This seems, at first naive glance, to provide all of the hooks to do GC and 
more, in a very Ada-like way. The idea seems to have been around for a 
while too, perhaps hundreds of web-years (at least 10 months). So what are 
the drawbacks? 

-- Brian

Re: Garbage Collection in Ada

[Tucker Taft]

Brian Rogoff (rogoff@sccm.Stanford.EDU) wrote:

: "Norman H. Cohen" <ncohen@watson.ibm.com> writes:
:    Robert A Duff wrote:

:    > In article <mheaney-ya023280000311962335300001@news.ni.net>,
:    > Matthew Heaney <mheaney@ni.net> wrote:
:    > >Language designers: any reason why overloading "all" would be too hard?
:    > 
:    > Well, functions return values (or constant objects, if you want to be
:    > precise in Ada 95 terms), whereas "P.all" returns a variable (if P is an
:    > access-to-variable type).  So it wouldn't work.  

:    The same scheme that Ada 95 uses to allow programmers to redefine the
:    behavior of "new" could have been used to allow redefinition of the
:    behavior of ".all".  The type System.Storage_Pools.Root_Storage_Pool
:    could have been given another primitive operation to be overridden by
:    those defining their own storage-pool types:

:       procedure Dereference
: 	 (Pool                     : in out Root_Storage_Pool;
: 	  Storage_Address          : in out Address;
: 	  Storage_Size_In_Elements : in Storage_Elements.Storage_Count;
: 	  Alignment                : in Storage_Elements.Storage_Count);

: This looks almost exactly like a proposal I read (a long time ago, on a web 
: page long since forgotten) for adding persistence to Ada 95. The main 
: difference is that Storage_Address was of type "Access_Type", which was a 
: generic formal parameter to the Storage_Pools package, and another parameter 
: to Dereference was a System.Address type. There was also a Rereference 
: procedure for converting System.Address types back to Access_Types.

:    <... snipping description of some the things this might allow ...>

: This seems, at first naive glance, to provide all of the hooks to do GC and 
: more, in a very Ada-like way. The idea seems to have been around for a 
: while too, perhaps hundreds of web-years (at least 10 months). So what are 
: the drawbacks? 

The problem has to do with knowing when the user is "done" with
the result of Dereference, and whether it is a read or a write
reference.  Remember that it is permissible to pass the result of
X.all to a very long subprogram, or to rename it.
In general an operation like this would work for a transaction-oriented
persistence mechanism, where you "commit" changes as a separate
operation, and pages stay in virtual memory indefinitely once referenced
(or until explicitly committed).

: -- Brian

-Tucker Taft   stt@inmet.com   http://www.inmet.com/~stt/
Intermetrics, Inc.  Cambridge, MA  USA