Heap Memory Management Question(s)

Heap Memory Management Question(s)

[Florian Liekweg]

Hi, everybody,

in the last few days, I've been thumping through the LRMs for both Ada
83 and Ada 95.  My primary intrest is to get an overview how heap
memory is being used in Ada, and how the language (tries to) support
this.  I'm also interested to learn how the people who made the
language what it is today were reasoning about what feature to
provide, and what not to provide.  It appears that some features were
put in in the hope or expectation that optimizing compilers may be
able to make use of them ...

First off, I understand that Ada provides both explicit deallocation
of heap objects, and garbage collection.  Of course, there are static
attributes (which stay alive over the whole run of a program), and
there are attributes (well, variables) that have a statically
determined lifetime (i.e. variables local to a procedure).

Now, the LRM for Ada83 defines in \S 3.8 (Access Types), that all
objects bound to variables of a particular access type form an
implicit collection, and objects belonging to different collections
are disjoint (which is actually a nice feature in comparison to
e.g. C++, where for every type T, there is only one pointer type, T*,
which is visible anywhere in the program, so that any variable "T*
foo" can point to any object allocated at any "new T ()" statement,
and any class T object can be manipulated anywhere in the program).

But is there any way to use this concept for managing the heap memory
of the objects of a particular collection?  Clearly, given some type T
and "type T_ptr is access T", when the definition of T_ptr goes out of
scope, there is no way of accessing objects of the collection of
T_ptr, so, at first sight, a clever compiler could deallocate these
objects.  Then again, isn't it possible to have some static (i.e.,
global) variable of type T_ptr which references a T object while the
T_ptr is left momentarily, and until it is entered again?  This would
imply that the lifetime of T objects belonging to the T_ptr collection
is not bracketed by the visibility of the definition of T_ptr.

Then, Ada 95 seems to have abandoned the concept of collections
entirely --- even the word itself cannot be found neither in the LRM
nor in the rationale (except when it refers to "garbage collection").
It also introduces the concept of Storage_Pools which are managed by
user-written code, which /could/ be taken to mean that any compiler
optimisations that were done on collections were not satisfactory.  Is
there any truth to that?

In general, can any users of commercial, higly optimizing ada
compilers report on any optimisations of these compilers that address
heap memory objects, and what language features or properties are
being exploited to that end?

NB, please feel free to PM me; if enough material comes up, I'll post
a summary.  In that case, please indicate what I can put into the
summary, and what you'd like to keep confidential.

Yours,
Florian

Re: Heap Memory Management Question(s)

[Robert A Duff]

Florian Liekweg <liekweg@gmx.de> writes:

> Hi, everybody,
> 
> in the last few days, I've been thumping through the LRMs for both Ada
> 83 and Ada 95.

You might want to take a look at the (draft) Ada 2005 manual,
which is available somewhere on www.adaic.com.

Also, John Barnes' book has a nice discussion of access types and
storage pools and whatnot.

> First off, I understand that Ada provides both explicit deallocation
> of heap objects, and garbage collection.

The designers of Ada 83 apparently expected GC to be supported,
but most compilers do not support GC.  However, I believe you can use
the BDW conservative GC with Ada.

> Now, the LRM for Ada83 defines in \S 3.8 (Access Types), that all
> objects bound to variables of a particular access type form an
> implicit collection, and objects belonging to different collections
> are disjoint (which is actually a nice feature in comparison to
> e.g. C++, where for every type T, there is only one pointer type, T*,
> which is visible anywhere in the program, so that any variable "T*
> foo" can point to any object allocated at any "new T ()" statement,
> and any class T object can be manipulated anywhere in the program).

"Disjoint collections" sounds like a nice feature, but I think it is
hardly ever useful.  Usually, one declares a single access type for each
designated type.  Having a name for it is just a nuisance -- the C way
is preferable in this regard.  Ada 2005 allows anonymous access types
almost anywhere -- "Foo: access T;" is sort of like "T* foo" in C.

In Ada 83, access types could only point at heap objects.
Ada 95 added "access all", which allows pointing at declared
objects, and allows conversion from any other access type
with the right designated type -- i.e. crossing collections.

I removed the term "collection" from the Ada 95 RM, because I didn't
think it was all that useful.  But the concept is still there -- access
types without the "all" behave as in Ada 83.

> But is there any way to use this concept for managing the heap memory
> of the objects of a particular collection?  Clearly, given some type T
> and "type T_ptr is access T", when the definition of T_ptr goes out of
> scope, there is no way of accessing objects of the collection of
> T_ptr, so, at first sight, a clever compiler could deallocate these
> objects.

Some compilers do that.  Most do not.  I don't think it's a good idea,
especially now that we have storage pools.  In my experience,
approximately zero access types are nested inside procedures
anyway.

>...  Then again, isn't it possible to have some static (i.e.,
> global) variable of type T_ptr which references a T object while the
> T_ptr is left momentarily, and until it is entered again?

No.  In Ada 83, if T_Ptr is local to a procedure, it's not visible
outside, so you can't declare variables of that type outside.
In Ada 95, you can use general access types (the "access all" kind) to
create such dangling pointers.  However, you have to say
'Unchecked_Access to do so, which makes it harder to do by accident.
You can use finalization to clean up such potentially-dangling
pointers.

I'm not sure what you mean by "left momentarily", but you can't create a
pointer to a local collection, return from the procedure, then reenter
the procedure and expect it to point to the same thing!  If you
dereference a dangling pointer, your program will behave in an
unpredictable manner.

>...  This would
> imply that the lifetime of T objects belonging to the T_ptr collection
> is not bracketed by the visibility of the definition of T_ptr.

The lifetime of a local collection is local.

> Then, Ada 95 seems to have abandoned the concept of collections
> entirely --- even the word itself cannot be found neither in the LRM
> nor in the rationale (except when it refers to "garbage collection").
> It also introduces the concept of Storage_Pools which are managed by
> user-written code, which /could/ be taken to mean that any compiler
> optimisations that were done on collections were not satisfactory.  Is
> there any truth to that?

I suppose you could put it that way.  There are hundreds of reasonable
ways of managing heap memory, none of which is best for all purposes.
Therefore, whatever method the compiler provides will not be
best for some programs.  That's why we added storage pools -- the user
can then define the heap-management strategy.  They can deallocate
objects en masse when leaving a procedure, if that's appropriate.
Most programs can just use the default storage pool provided
by the compiler.

- Bob

Re: Heap Memory Management Question(s)

[Florian Liekweg]

Robert A Duff wrote:
> You might want to take a look at the (draft) Ada 2005 manual,
> which is available somewhere on www.adaic.com.
> 
> Also, John Barnes' book has a nice discussion of access types and
> storage pools and whatnot.
Thank you for the pointers!

> I removed the term "collection" from the Ada 95 RM, because [reason]
> [...]
> [...]  I don't think it's a good idea,
> especially now that we have storage pools.  In my experience,
> approximately zero access types are nested inside procedures
> anyway.
That's what I wanted to know, but I fear I have introduced a
misunderstanding here:

> I'm not sure what you mean by "left momentarily", [...]

Sorry for being unclear.  I was thinking of, e.g., a package variable,
which, as I understand, is not visible and/or accessible everywhere,
but it exists and keeps its state over the lifetime of the program.

My assumption is the following:
   We can momentarily leave the area where the variable is /visible/,
   but it stays in existence.  The lifetime of the object it points to
   can now span the entire program, not just the time the variable is
   visible.
My conclusion is: Visibility of the access type doesn't help when it
   comes to determining the lifetime of that object.  NB, it could
   of course /improve/ whatever analysis a sophisticated compiler
   might do.

> [...] hundreds of reasonable
> ways of managing heap memory, none of which is best for all purposes.
> [...]  storage pools [...]
Yes, indeed.  I am keeping an eye on Ada, because it seems to me
that it takes this subject more seriously than, e.g. C++ and friends,
and is not afraid to unload some of the work associated with it onto
the compiler.

-- Florian

Re: Heap Memory Management Question(s)

[jimmaureenrogers]

Florian Liekweg wrote:
> Sorry for being unclear.  I was thinking of, e.g., a package variable,
> which, as I understand, is not visible and/or accessible everywhere,
> but it exists and keeps its state over the lifetime of the program.
>
> My assumption is the following:
>    We can momentarily leave the area where the variable is /visible/,
>    but it stays in existence.  The lifetime of the object it points to
>    can now span the entire program, not just the time the variable is
>    visible.
> My conclusion is: Visibility of the access type doesn't help when it
>    comes to determining the lifetime of that object.  NB, it could
>    of course /improve/ whatever analysis a sophisticated compiler
>    might do.

You might want to read the "Ada Distilled" article by Richard Riehle.
It is available several places online.

Ada Distilled has a good discussion of how Ada makes a distinction
between scope and visibility. Richard argues that understanding this
distinction is critical to understanding Ada.

Another point to understand about Ada is that the language
design reduces the need to use access types compared to Java,
C++, or C#.

Jim Rogers

Re: Heap Memory Management Question(s)

[Robert A Duff]

Florian Liekweg <liekweg@gmx.de> writes:

> Sorry for being unclear.  I was thinking of, e.g., a package variable,
> which, as I understand, is not visible and/or accessible everywhere,
> but it exists and keeps its state over the lifetime of the program.
> 
> My assumption is the following:
>    We can momentarily leave the area where the variable is /visible/,
>    but it stays in existence.  The lifetime of the object it points to
>    can now span the entire program, not just the time the variable is
>    visible.
> My conclusion is: Visibility of the access type doesn't help when it
>    comes to determining the lifetime of that object.  NB, it could
>    of course /improve/ whatever analysis a sophisticated compiler
>    might do.

That's correct.  Lifetime is different from visibility.
If you declare:

    X: Integer;

in a library package, it lasts essentially "forever".
Likewise, if you declare an access type:

    type A is access ...;

the heap-allocated objects in A's "collection" can last "forever"
(or you can use Unchecked_Deallocation to destroy them).

- Bob

Re: Heap Memory Management Question(s)

[Adam Beneschan]

Florian Liekweg wrote:
> Robert A Duff wrote:
> > You might want to take a look at the (draft) Ada 2005 manual,
> > which is available somewhere on www.adaic.com.
> >
> > Also, John Barnes' book has a nice discussion of access types and
> > storage pools and whatnot.

> Thank you for the pointers!

Ahem...we don't use the term "pointers" in Ada.  So that should be
"Thank you for the access values."

(sorry, couldn't resist)  ;-)

                               -- Adam