garbage collection

garbage collection

[Ronald Ayoub]

In the book "Programming in Ada 95" by Barnes he says:

If an allocated object becomes inaccessbile becasue no declard objects refer
to it directly or indirectly then the storage it occupies may be reclaimed
so that it can be reused for other objects. An implementation may (but need
not) provide garbage collection for this.

I need this to be clarified for me. If an implementation doesn't provide 
garbage collection then that storage is forever lost, is that correct? Or
does this mean that it may not be garbage collected but when a call to new
is executed it is at that time scene as available. Please clarify. This seems
like a real bad idea not to have some form of garbage collection inforced.

Ron

Re: garbage collection

[tmoran]

> If an implementation doesn't provide garbage collection then that
> storage is forever lost, is that correct?

No.  When the access type goes out of scope there is clearly no way
the storage can be on the target end of a pointer, so the
implementation should free that storage.  With the 'Storage_Size
attribute on the access type, "the storage for the pool is reclaimed
when the master containing the declaration of the access type is
left".  If that's not soon enough, you have several options,
including:

1) Ada.Unchecked_Deallocation (the equivalent of "free"), if you are
careful not to deallocate and later refer to the same storage.

2) Use a controlled type so your Finalize routine can recycle storage.

3) Do your own storage management for the relevant types using the
Storage_Pool facility.  See Barnes, section 21.4 for a good
discussion of storage management.

4) The most straightforward way, as has been pointed out, is not to
use "new" unnecessarily.  Since you can declare dynamically sized
things inside a subroutine, and can nest subroutines, storage that
is allocated in a stack-like (first allocated is last deallocated)
style can normally be handled with simple declarations, without the
overhead or dangers of "new".  With tasks, you can even have several
separate stack-like allocations going on at once.

Re: garbage collection

[Keith Thompson]

tmoran@bix.com writes:
> > If an implementation doesn't provide garbage collection then that
> > storage is forever lost, is that correct?
> 
> No.  When the access type goes out of scope there is clearly no way
> the storage can be on the target end of a pointer, so the
> implementation should free that storage.

Just to clarify, most implementations don't actually do this.  Thus,
under most Ada implementations, storage *will* be "forever lost" if
you allocate it and don't explicitly deallocate it.  (Well, "forever"
usually means "until the program terminates".)

-- 
Keith Thompson (The_Other_Keith) kst@cts.com  <http://www.ghoti.net/~kst>
San Diego Supercomputer Center           <*>  <http://www.sdsc.edu/~kst>
One of the great tragedies of ancient history is that Helen of Troy
lived before the invention of the champagne bottle.

Re: garbage collection

[Tucker Taft]

Keith Thompson wrote:
> 
> tmoran@bix.com writes:
> > > If an implementation doesn't provide garbage collection then that
> > > storage is forever lost, is that correct?
> >
> > No.  When the access type goes out of scope there is clearly no way
> > the storage can be on the target end of a pointer, so the
> > implementation should free that storage.
> 
> Just to clarify, most implementations don't actually do this.  Thus,
> under most Ada implementations, storage *will* be "forever lost" if
> you allocate it and don't explicitly deallocate it.  (Well, "forever"
> usually means "until the program terminates".)

In Ada 95, implementations are required to reclaim the storage associated
with an access type if the 'Storage_Size attribute is specified (which
Tom also mentioned, by the way).  If no 'Storage_Size is specified, then
you are correct that most Ada 95 compilers don't reclaim the storage
automatically when leaving the scope of the access type.

> --
> Keith Thompson (The_Other_Keith) kst@cts.com  <http://www.ghoti.net/~kst>
> San Diego Supercomputer Center           <*>  <http://www.sdsc.edu/~kst>
> One of the great tragedies of ancient history is that Helen of Troy
> lived before the invention of the champagne bottle.

-- 
-Tucker Taft   stt@averstar.com   http://www.averstar.com/~stt/
Technical Director, Distributed IT Solutions  (www.averstar.com/tools)
AverStar (formerly Intermetrics, Inc.)   Burlington, MA  USA

Re: garbage collection

[Robert Dewar]

In article <37BC2203.328E6338@averstar.com>,
  Tucker Taft <stt@averstar.com> wrote:
> Keith Thompson wrote:
> >
> > tmoran@bix.com writes:
> > > > If an implementation doesn't provide garbage collection
then that
> > > > storage is forever lost, is that correct?
> > >
> > > No.  When the access type goes out of scope there is
clearly no way
> > > the storage can be on the target end of a pointer, so the
> > > implementation should free that storage.
> >
> > Just to clarify, most implementations don't actually do
this.  Thus,
> > under most Ada implementations, storage *will* be "forever
lost" if
> > you allocate it and don't explicitly deallocate it.  (Well,
"forever"
> > usually means "until the program terminates".)
>
> In Ada 95, implementations are required to reclaim the storage
associated
> with an access type if the 'Storage_Size attribute is
specified (which
> Tom also mentioned, by the way).  If no 'Storage_Size is
specified, then
> you are correct that most Ada 95 compilers don't reclaim the
storage
> automatically when leaving the scope of the access type.

Ada compilers have differed here. The old Alsys compilers always
used to automatically free local access stuff on exit. The
trouble is that people are quite used to controlling this
memory manually, and in this case you do add quite a bit
of overhead by arranging for the automatic release.

We went backwards and forwards on what the default should be
in GNAT, and decided finally that the default was not to free
this storage, however, it is trivial to specify that the space
for a local access collection SHOULD be freed on access by
using:

   for access_type_name'Storage_Pool
     use System.Pool_Local.Unbounded_Reclaim_Pool;

Probably a good idea would be to add a configuration pragma
that made this pool assignment the default.

By the way, a recommendation is to look through the collection
of storage pool implementations provided in GNAT, there is a lot
of useful functionality there, including a very useful debug
pool that checks for correct storage handling.

P.S. Ada 83 also required that access types with an explicit
storage size be freed on scope exit. The Ada 83 RM strongly
suggests that this should be the default for all access types,
but stops short of requiring this. Even the implication is
removed from the Ada 95 RM.

Robert Dewar
Ada Core Technologies


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

Re: garbage collection

[Robert Dewar]

In article <37BC2203.328E6338@averstar.com>,
  Tucker Taft <stt@averstar.com> wrote:
> Keith Thompson wrote:
> >
> > tmoran@bix.com writes:
> > > > If an implementation doesn't provide garbage collection
then that
> > > > storage is forever lost, is that correct?
> > >
> > > No.  When the access type goes out of scope there is
clearly no way
> > > the storage can be on the target end of a pointer, so the
> > > implementation should free that storage.
> >
> > Just to clarify, most implementations don't actually do
this.  Thus,
> > under most Ada implementations, storage *will* be "forever
lost" if
> > you allocate it and don't explicitly deallocate it.  (Well,
"forever"
> > usually means "until the program terminates".)
>
> In Ada 95, implementations are required to reclaim the storage
associated
> with an access type if the 'Storage_Size attribute is
specified (which
> Tom also mentioned, by the way).  If no 'Storage_Size is
specified, then
> you are correct that most Ada 95 compilers don't reclaim the
storage
> automatically when leaving the scope of the access type.

Ada compilers have differed here. The old Alsys compilers always
used to automatically free local access stuff on exit. The
trouble is that people are quite used to controlling this
memory manually, and in this case you do add quite a bit
of overhead by arranging for the automatic release.

We went backwards and forwards on what the default should be
in GNAT, and decided finally that the default was not to free
this storage, however, it is trivial to specify that the space
for a local access collection SHOULD be freed on access by
using:

   for access_type_name'Storage_Pool
     use System.Pool_Local.Unbounded_Reclaim_Pool;

Probably a good idea would be to add a configuration pragma
that made this pool assignment the default.

By the way, a recommendation is to look through the collection
of storage pool implementations provided in GNAT, there is a lot
of useful functionality there, including a very useful debug
pool that checks for correct storage handling.

P.S. Ada 83 also required that access types with an explicit
storage size be freed on scope exit. The Ada 83 RM strongly
suggests that this should be the default for all access types,
but stops short of requiring this. Even the implication is
removed from the Ada 95 RM.

Robert Dewar
Ada Core Technologies


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

Re: garbage collection

[tmoran]

> > No.  When the access type goes out of scope there is clearly no way
> > the storage can be on the target end of a pointer, so the
> > implementation should free that storage.
>
> Just to clarify, most implementations don't actually do this.
  Why?  Is an implementation not easy, efficient, and predictable?
And of course overidable by the user simply by raising the
level where the access type is declared.
  It seems undesirable to have to specify a number, big enough, but
not too big, for the amount of storage needed when you merely want
to get automatic deallocation.

Re: garbage collection

[Keith Thompson]

tmoran@bix.com writes:
> > > No.  When the access type goes out of scope there is clearly no way
> > > the storage can be on the target end of a pointer, so the
> > > implementation should free that storage.
> >
> > Just to clarify, most implementations don't actually do this.
>   Why?  Is an implementation not easy, efficient, and predictable?
> And of course overidable by the user simply by raising the
> level where the access type is declared.
>   It seems undesirable to have to specify a number, big enough, but
> not too big, for the amount of storage needed when you merely want
> to get automatic deallocation.

I just realized that I had mis-read the article to which I was
responding.  What "most implementations don't actually do" is general
garbage collection, i.e., freeing allocated memory after it becomes
inaccessible.  Freeing allocated memory when leaving the scope of an
access type is much easier.

I *think* that most implementations don't even do this, but I'm not as
sure on this point.  It does impose a little extra overhead, in both
time and space.

Specifying the 'Storage_Pool attribute is a very powerful and
under-used feature, IMHO.  The biggest obstacle to its use, I suspect,
is the need to implement the Storage_Pool operations.

If System.Storage_Pools also provided routines for dereferencing
access values (perhaps one each for reading and writing), and perhaps
also for initialization and finalization of access objects, it would
be even more powerful.  I haven't entirely thought this through, so it
may be a bad idea for some reason.

-- 
Keith Thompson (The_Other_Keith) kst@cts.com  <http://www.ghoti.net/~kst>
San Diego Supercomputer Center           <*>  <http://www.sdsc.edu/~kst>
One of the great tragedies of ancient history is that Helen of Troy
lived before the invention of the champagne bottle.

Re: garbage collection

[Matthew Heaney]

In article <yecwvuqhrkx.fsf@king.cts.com> , Keith Thompson <kst@cts.com>  
wrote:

> Specifying the 'Storage_Pool attribute is a very powerful and
> under-used feature, IMHO.  The biggest obstacle to its use, I suspect,
> is the need to implement the Storage_Pool operations.

One thing I miss is not having a set of nameable, pre-defined storage pools.
You have that in GNAT, but it's not really portable because of certain
low-level calls (to a C routine called "_gnat__allocate", or something like
that).


> If System.Storage_Pools also provided routines for dereferencing
> access values (perhaps one each for reading and writing), and perhaps
> also for initialization and finalization of access objects, it would
> be even more powerful.  I haven't entirely thought this through, so it
> may be a bad idea for some reason.

That's one nice thing about C++.  You can implement a pointer abstraction
that has a syntax identical to a built-in pointer.  In Ada95, you have to
implement a "handle" type that provides a dereference operator:

  type T (<>) is limited private;

  type T_Access is access all T;

  type T_Handle is private;

  function "+" (Handle : T_Handle) return T_Access;

All the primitive operations of T take access parameters, since we're always
dealing with pointers to T:

  procedure Op (O : access T);

  function Get_Attribute (O : access T) return Attr_T;

You also have constructor(s) that return a handle object:

  function New_T return T_Handle;  -- not T_Access


All the actual garbage collection is associated with T_Handle, since there's
no way to do that with the access type T_Access directly.  (Which is how
Ada95 differs from C++.)

I use this technique to implement reference-counting for on-the-heap
abstractions, so that when the count drops to zero the memory is
automatically reclaimed.  See the patterns archives for lots of examples.

<http://www.acm.org/archives/patterns.html>

The only trap door in this scheme is that there's no way to prevent the
client from manipulating the access object directly, say, by making a copy.
It has to be understood by users that that is something you never do with a
handle-based abstraction.

It would be swell if the language were amended to make access types limited;
this would prevent any problems engendered by accidental copying of access
objects.

--
Matt

It is impossible to feel great confidence in a negative theory which has
always rested its main support on the weak points of its opponent.

Joseph Needham, "A Mechanistic Criticism of Vitalism"

Re: garbage collection

[Keith Thompson]

"Matthew Heaney" <matthew_heaney@acm.org> writes:
[...]
> It would be swell if the language were amended to make access types limited;
> this would prevent any problems engendered by accidental copying of access
> objects.

Not all access types, I hope; sometimes you do want to copy access
values!

-- 
Keith Thompson (The_Other_Keith) kst@cts.com  <http://www.ghoti.net/~kst>
San Diego Supercomputer Center           <*>  <http://www.sdsc.edu/~kst>
One of the great tragedies of ancient history is that Helen of Troy
lived before the invention of the champagne bottle.

Re: garbage collection

[Robert Dewar]

In article <yecvha9izs6.fsf@king.cts.com>,
> "Matthew Heaney" <matthew_heaney@acm.org> writes:
> [...]
> > It would be swell if the language were amended to make
access types limited;
> > this would prevent any problems engendered by accidental
copying of access
> > objects.

There has *got* to be a smiley missing here. It is inconceivable
to make this change to the language (all access types limited)
and would be HIGHLY undesirable.

Presumably, if the above is not a joke (which it might be,
I am not sure), it is a proposal for some kind of extension
involving limited access types.

Actually I think the reasonable thing to do is to extend the
storage pool abstraction so that a version of it contains
a copy operation that is called for all implicit copies of
the given access value. You probably want to introduce some
general controlled notion here.


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

Re: garbage collection

[Matthew Heaney]

In article <7pmad9$jnq$1@nnrp1.deja.com> , Robert Dewar 
<robert_dewar@my-deja.com>  wrote:

>>> It would be swell if the language were amended to make access types limited;
>>> this would prevent any problems engendered by accidental copying of access
>>> objects.
>
> There has *got* to be a smiley missing here. It is inconceivable
> to make this change to the language (all access types limited)
> and would be HIGHLY undesirable.

Oh dear, I seemed to have confused people.

No, I certainly don't mean make *all* access types limited.  Only those
access types specifically marked as limited, a la limited record types.

> Presumably, if the above is not a joke (which it might be,
> I am not sure), it is a proposal for some kind of extension
> involving limited access types.

Yes, it is a proposal for an extension involving limited access types.

> Actually I think the reasonable thing to do is to extend the
> storage pool abstraction so that a version of it contains
> a copy operation that is called for all implicit copies of
> the given access value. You probably want to introduce some
> general controlled notion here.

That would be really slick: being able to make access types controlled
directly, instead of having to wrap the access object in a some kind of
controlled abstraction (what I usually call a "handle").

--
Matt

It is impossible to feel great confidence in a negative theory which has
always rested its main support on the weak points of its opponent.

Joseph Needham, "A Mechanistic Criticism of Vitalism"

Re: garbage collection

[Matthew Heaney]

In article <yecvha9izs6.fsf@king.cts.com> , Keith Thompson <kst@cts.com>  
wrote:

> "Matthew Heaney" <matthew_heaney@acm.org> writes:
> [...]
>> It would be swell if the language were amended to make access types limited;
>> this would prevent any problems engendered by accidental copying of access
>> objects.
>
> Not all access types, I hope; sometimes you do want to copy access
> values!

Yes, of course.  Something like:

  type T_Access is limited access all T;

This proposal has also been bandied about for another reason: it has been
proffered as part of the solution to the problem of not being able to take
the 'Access of a local subprogram.


--
Matt

It is impossible to feel great confidence in a negative theory which has
always rested its main support on the weak points of its opponent.

Joseph Needham, "A Mechanistic Criticism of Vitalism"

Re: garbage collection

[Robert Dewar]

In article <37be0c85@news1.us.ibm.net>,
  "Matthew Heaney" <matthew_heaney@acm.org> wrote:
> That's one nice thing about C++.  You can implement a pointer
> abstraction that has a syntax identical to a built-in pointer.
> In Ada95, you have to implement a "handle" type that provides
> a dereference operator:

Not in GNAT, simply derive from the Checked_Pool abstraction,
providing an appropriate Dereference function.

Robert Dewar
Ada Core Technologies


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

Re: garbage collection [storage pools]

[Robert Dewar]

In article <37be0c85@news1.us.ibm.net>,
  "Matthew Heaney" <matthew_heaney@acm.org> wrote:
> One thing I miss is not having a set of nameable, pre-defined
> storage pools.
> You have that in GNAT, but it's not really portable because of
> certain
> low-level calls (to a C routine called "_gnat__allocate", or
> something like
> that).

Well it is unlikely that implementations of storage pools
will be completely portable in any case, because they will
undoubtedly do implementation defined stuff using unchecked
conversions, address arithmetic, calls to library routines
etc. So it is probably not a good idea to try to insist on
portable implementations.

It would be VERY nice to have a standard set of storage pools
with standard interfaces. This is an excellent area to suggest
to the ARG for future standardization.

In GNAT, we provide the following

Stack_Bounded_Pool
  really intended only for internal use, implements the
  allocation strategy for fixed size objects when a storage
  size clause is present.

Unbounded_No_Reclaim_Pool
  again really intended for internal use, this is the default
  storage pool that simply allocates from the heap

Unbounded_Reclaim_Pool
  this is the one that I have mentioned before, it provides a
  local allocation capability where the objects are all freed
  automatically on scope exit

Checked_Pool
  this is like the standard unbounded no reclaim pool, but has a
  dereference procedure that is called on each dereference of an
  object in the pool. This is still an abstract pool, the user
  must specialize it with an appropriate extension to provide
  a useful definition for dereference. This is really a language
  extension (of the allowed kind, provided by a package).

Debug_Pool
  this is like the standard unbounded no reclaim pool, but
  it maintains extra overhead to do full validity checking
  on all operations. This is useful for tracking down
  storage leaks.

One can think of many more useful pools, most notably one that
provides defined worst case bounded time performance for real
time use.

It would also be useful to standardize a pragma to override
the normal default storage pool (we plan adding such a pragma
to the next version of GNAT).

Robert Dewar
Ada Core Technologies


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

Re: garbage collection [storage pools]

[Simon Wright]

Robert Dewar <dewar@gnat.com> writes:

> It would be VERY nice to have a standard set of storage pools
> with standard interfaces. This is an excellent area to suggest
> to the ARG for future standardization.

I would strongly support this idea.

-- 
Simon Wright                        Work Email: simon.j.wright@gecm.com
Alenia Marconi Systems                         Voice: +44(0)1705-701778
Integrated Systems Division                      FAX: +44(0)1705-701800

Re: garbage collection

[Brian Rogoff]

On 20 Aug 1999, Keith Thompson wrote:
> Specifying the 'Storage_Pool attribute is a very powerful and
> under-used feature, IMHO.  The biggest obstacle to its use, I suspect,
> is the need to implement the Storage_Pool operations.
> 
> If System.Storage_Pools also provided routines for dereferencing
> access values (perhaps one each for reading and writing), and perhaps
> also for initialization and finalization of access objects, it would
> be even more powerful.  I haven't entirely thought this through, so it
> may be a bad idea for some reason.

See a discussion of this in comp.lang.ada, Nov '96, in a thread named 
"Garbage Collection in Ada". 

-- Brian

Re: garbage collection

[Robert Dewar]

In article <vvhv3.214$36.49923@typhoon-sf.snfc21.pbi.net>,
  tmoran@bix.com wrote:
> > Just to clarify, most implementations don't actually do
> > this.
>   Why?  Is an implementation not easy, efficient,
> and predictable?

Easy: fairly so, look at System.Pool_Local in the GNAT sources
(s-pooloc.ads). Not that complex. The body is 189 lines, perhaps
only 60 lines or so of actual code.

Predictable: sure

Efficient: there's the rub, there is significant overhead from
arranging for the automatic release, both in space and time. We
found that most existing code does NOT assume this automatic
release, and it clearly makes no sense to use this pool by
default if the program does all its own deallocation.

> And of course overidable by the user simply by raising the
> level where the access type is declared.
>   It seems undesirable to have to specify a number, big
enough, but
> not too big, for the amount of storage needed when you merely
want
> to get automatic deallocation.

No, that's not the way to do it (using Storage_Size). Only
use a Storage_Size where it really does make sense to allocate
in a fixed length area on the stack. Instead use a storage
pool. If you are using GNAT, just do

  for this_access_type'Storage_Pool
    use System.Pool_Local.Unbounded_Reclaim_Pool;

and of course do a "with" of System.Pool_Local.

If you are using some other compiler that does not provide this
very useful capability, then you need to write your own storage
pool implementation (the one with GNAT may work, but you can't
assume that library routines supplied with GNAT will work
unchanged with other compilers (*) since they may depend on
GNAT specific features -- I don't know if this one does or not).

Robert Dewar
Ada Core Technologies

(*) People sometimes make the mistake of assuming that because
the GNAT runtime is written in Ada, it can automatically be used
with other compilers. Sometimes this is the case (indeed one
other vendor was routinely supplying some of the GNAT math
routines for a while, to plug holes in their own run-time, they
may still do this, I don't know ...)

But on the other hand, sales folks for that same vendor were
telling people: "DOn't worry about the information systems
annex, we don't provide it, but if you need it, you can just
pick up the GNAT routines and use them with our compiler."
Unfortunately that is definitely not the case. In the first
place, the underlying compiler must support 18-digit decimal
scaled arithmetic. Secondly, the implementation relies on
GNAT specific stuff, e.g.

   procedure Divide
     (Dividend  : in Dividend_Type;
      Divisor   : in Divisor_Type;
      Quotient  : out Quotient_Type;
      Remainder : out Remainder_Type)
   is
      --  We have a nested procedure that is the actual
      --  intrinsic divide.
      --  This is required because in the current RM, Divide
      --  itself does
      --  not have convention Intrinsic.

      procedure Divide
        (Dividend  : in Dividend_Type;
         Divisor   : in Divisor_Type;
         Quotient  : out Quotient_Type;
         Remainder : out Remainder_Type);

      pragma Import (Intrinsic, Divide);

   begin
      Divide (Dividend, Divisor, Quotient, Remainder);
   end Divide;

Now it would be possible to implement a non-intrinsic divide,
but it would be gruesomely inefficient. This is simply a divide
operation, and really needs to be specialized by the compilers
code generator. Trying to do this with portable Ada is just
at the wrong level!


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.

Default Storage Pool (was Re: garbage collection)

[Simon Wright]

Robert Dewar <dewar@gnat.com> writes:

>   for this_access_type'Storage_Pool
>     use System.Pool_Local.Unbounded_Reclaim_Pool;
> 
> and of course do a "with" of System.Pool_Local.
> 
> If you are using some other compiler that does not provide this
> very useful capability, then you need to write your own storage
> pool implementation (the one with GNAT may work, but you can't
> assume that library routines supplied with GNAT will work
> unchanged with other compilers (*) since they may depend on
> GNAT specific features -- I don't know if this one does or not).

It would have been very helpful for the Booch Components if all
compilers provided a (standardised, if at all possible) mechanism to
access their default Storage Pool. We had to muck around with indirect
means of finding it, which triggered problems in several compilers.

(BTW, Unbounded_Reclaim_Pool extends Unbounded_No_Reclaim_Pool which
uses gnat_malloc, gnat_free so there would be some work to do to use
them with another compiler -- 3.11p)

Re: Default Storage Pool (was Re: garbage collection)

[Robert A Duff]

Simon Wright <simon@pogner.demon.co.uk> writes:

> It would have been very helpful for the Booch Components if all
> compilers provided a (standardised, if at all possible) mechanism to
> access their default Storage Pool.

There is no requirement that the compiler only have one default pool.

But you can say:

    type T1 is access ...;
    ...
    type T2 is access ...;
    for T2'Storage_Pool use T1'Storage_Pool;

- Bob
-- 
Change robert to bob to get my real email address.  Sorry.

Re: garbage collection

[Gisle S�lensminde]

In article <7pe93j$ehg$1@dailyplanet.wam.umd.edu>, Ronald Ayoub wrote:
>In the book "Programming in Ada 95" by Barnes he says:
>
>If an allocated object becomes inaccessbile becasue no declard objects refer
>to it directly or indirectly then the storage it occupies may be reclaimed
>so that it can be reused for other objects. An implementation may (but need
>not) provide garbage collection for this.
>
>I need this to be clarified for me. If an implementation doesn't provide 
>garbage collection then that storage is forever lost, is that correct? Or
>does this mean that it may not be garbage collected but when a call to new
>is executed it is at that time scene as available. Please clarify. This seems
>like a real bad idea not to have some form of garbage collection inforced.
>
>Ron

This is one of the strange things with Ada. Nearly all textbooks are
giving you the impression that garbage collection is common in
Ada compilers, and that maybe some compilers not has implemented
GC, since the standard allows an implemention to not implement it.    
  
The fact is that hardly any Ada compilers have GC. The only ones I know    
about is those targeted for java virtual machine bytecode, where the
virtual machine implements GC. (appletmagic and soon? jgnat)

The reason is of cause that GC  not is desireable for most realtime
systems, which is the traditional area for Ada, but for many other tasks,
GC is a good thing. However, I miss GC less in Ada then in many other
languages, because you are less dependent on dynamic memory then in 
most other languages, and controlled types can be used to automaticly
free memory when they goes out of scope or are assigned to. 

--
Gisle S�lensminde ( gisle@ii.uib.no )   

Re: garbage collection

[Pascal MALAISE]

Ronald Ayoub wrote:
...
> If an implementation doesn't provide
> garbage collection then that storage is forever lost, is that correct? Or
> does this mean that it may not be garbage collected but when a call to new
> is executed it is at that time scene as available. Please clarify. This seems
> like a real bad idea not to have some form of garbage collection inforced.

The most portable approach is not to depend on a potential garbage
collector
in the runtime and keep a free list of unused chunks. With this mecanism
a process has at least a measurable and maximum (even if not optimized)
virtual size.


-- Allocates and frees cells of data access,
--  using a free list to re-use free cells.
generic
  type DATA_TYPE is private;
  type DATA_ACCESS_TYPE is access DATA_TYPE;

package DYN_DATA is

  -- Allocates a new cell.
  -- The result is the access to a pre allocated area for DATA_TYPE.
  function ALLOCATE return DATA_ACCESS_TYPE;

  -- Allocates a new cell and fills it with DATA
  -- The result is the access to a pre allocated area for DATA_TYPE,
  --  storing DATA
  function ALLOCATE (DATA : DATA_TYPE) return DATA_ACCESS_TYPE;

  -- Frees a cell. DATA_ACCESS is set to null.
  procedure FREE (DATA_ACCESS : in out DATA_ACCESS_TYPE);

end DYN_DATA;

6 ada instructions.
Body available on request. It does not depend on any package and has 37
ada instructions :-)

Of course, if you claim some chunks and release them, then claim for
other chunks of
another type (even the same size), some new data is allocated that a
garbage collector
would have re-used. That's the drawback.
But the old chucks are only swap usage, aren't they?

-- 
Pascal MALAISE
(priv) mailto:malaise@magic.fr
(prof) mailto:malaise@fr.airsysatm.thomson-csf.com

Re: garbage collection

[David Botton]

Perhaps send the package to AdaSource@AdaPower.com and make your code
available to the world :)

David Botton

Pascal MALAISE wrote in message <37BAFA16.3138228B@magic.fr>...

>6 ada instructions.
>Body available on request. It does not depend on any package and has 37
>ada instructions :-)

Re: garbage collection

[Robert I. Eachus]

Ronald Ayoub wrote:
 
> I need this to be clarified for me. If an implementation doesn't provide
> garbage collection then that storage is forever lost, is that correct? Or
> does this mean that it may not be garbage collected but when a call to new
> is executed it is at that time scene as available. Please clarify. This seems
> like a real bad idea not to have some form of garbage collection inforced.

   The correct answer is c) All Ada compilers provide some forms of
storage management, and most Ada programs lose no storage.  But very few
Ada implementations support compacting garbage collectors.

   I could go into all the gory details, but that about sums it up.  The
validation tests do include several tests to insure that storage is not
lost in many common situations, but there is no requirement that storage
be freed the moment their are no more references.  Many Ada compilers
instead free the storage when the access type goes out of scope for some
or all types.

   Why?  Three reasons.  Freeing the storage when the type goes out of
scope allows for predictable storage reclamation which is very useful in
real-time code.  Second, the user can easily manage storage for any type
the way he wants to.  Insisting on "full" garbage collection would limit
the user's choices.

   And finally, Ada allows return values from functions which are
unbounded, and for which the storage is "automagically" managed.  If you
define a function which returns a string in Ada, there is no need for
explicit alloc and free calls or the equivalent.  So in ninety percent
or more of the cases where you need garbage collection in other
languages, you don't even need explicit allocations in Ada.

-- 

                                        Robert I. Eachus

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

Re: garbage collection

[Gautier]

>    Why?  Three reasons.  Freeing the storage when the type goes out of
> scope allows for predictable storage reclamation which is very useful in
> real-time code.  Second, the user can easily manage storage for any type
> the way he wants to.  Insisting on "full" garbage collection would limit
> the user's choices.

BTW: is it possible to prove that an object is not more accessed 
(of course: as long as its type exists) ? It's so easy to copy a pointer...

-- 
Gautier

Re: garbage collection

[Robert I. Eachus]

> BTW: is it possible to prove that an object is not more accessed
> (of course: as long as its type exists) ? It's so easy to copy a pointer...

  Which is why Ada has access types instead. ;-)  Seriously, if an
access type goes out of scope, then it is legitimate to recover all
storage associated with the type.  If you have gone and done something
like using Unchecked_Conversion to convert to a different access type,
well, you asked for it.  (You can get into similar trouble by saving
addresses.

  The whole idea is that access types are safe as long as you don't go
outside the rules.

-- 

                                        Robert I. Eachus

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

Re: garbage collection

[Keith Thompson]

"Robert I. Eachus" <eachus@mitre.org> writes:
[...]
>    I could go into all the gory details, but that about sums it up.  The
> validation tests do include several tests to insure that storage is not
> lost in many common situations, but there is no requirement that storage
> be freed the moment their are no more references.  Many Ada compilers
> instead free the storage when the access type goes out of scope for some
> or all types.
> 
>    Why?  Three reasons.  Freeing the storage when the type goes out of
> scope allows for predictable storage reclamation which is very useful in
> real-time code.  Second, the user can easily manage storage for any type
> the way he wants to.  Insisting on "full" garbage collection would limit
> the user's choices.
[...]

BTW, in my experience most access types don't go out of scope until
the program terminates, because they're declared in library-level
packages.  The automated reclamation can only take place if the access
type is declared directly or indirectly within a subprogram or a task
body (there may be other cases).

(I'm not sure how typical my experience is; how common is it to
declare an access type within a subprogram?)

Note that declaring an access *object* within a subprogram doesn't let
the storage it refers to be reclaimed; the access value could have
been copied to an object in an outer scope before the subprogram
completed.

>    And finally, Ada allows return values from functions which are
> unbounded, and for which the storage is "automagically" managed.  If you
> define a function which returns a string in Ada, there is no need for
> explicit alloc and free calls or the equivalent.  So in ninety percent
> or more of the cases where you need garbage collection in other
> languages, you don't even need explicit allocations in Ada.

Right, I think this is the biggest reason that the lack of garbage
collection in most Ada implementations isn't (much of) a problem.

-- 
Keith Thompson (The_Other_Keith) kst@cts.com  <http://www.ghoti.net/~kst>
San Diego Supercomputer Center           <*>  <http://www.sdsc.edu/~kst>
One of the great tragedies of ancient history is that Helen of Troy
lived before the invention of the champagne bottle.

Re: garbage collection

[Robert Dewar]

In article <yec9076vqly.fsf@king.cts.com>,
  Keith Thompson <kst@cts.com> wrote:
> BTW, in my experience most access types don't go out of scope
> until
> the program terminates, because they're declared in
> library-level
> packages.  The automated reclamation can only take place if
> the access
> type is declared directly or indirectly within a subprogram or
> a task
> body (there may be other cases).

True, but the one familiar case in which access types are
declared locally is *precisely* when you want to take advantage
of the compiler being able to free everything on scope exit.
Of course you have to make sure that your compiler has this
capability (GNAT does, I don't know about other Ada 95
compilers).


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.