Memory management clarification

Memory management clarification

[Maciej Sobczak]

Hi,

Trying to learn a bit of Ada I came across a statement that memory 
allocated from the pool will be implicitly reclaimed when the acces 
variable used to reference it goes out of scope.
That's nice, but I would like to learn a bit more about the exact 
mechanics of this and about the guarantees that it can provide.

Let's say that there is some MyType definition and this:

type MyTypeRef is access MyType;

1.

declare
     X : MyTypeRef;
begin
    loop
       X := new MyType;
    end loop;  -- infinite loop just for the sake of discussion
end;

Note that X does not goes out of scope when the loop is executing.
Will the memory be reclaimed? When? What can be said about the memory 
consumption of such program? Is it bounded and guaranteed? Is it 
necessarily larger than without the loop (just single allocation)?

2.

loop
    declare
       X : MyTypeRef;
    begin
       X := new MyType;
    end;
end loop;

What now? Is this any different from the memory management point of view?

3.

declare
    X : MyTypeRef;
begin
    X := new MyType;
    X := new MyType;
    X := new MyType;
    X := new MyType;
    -- ...
end;

When is the memory reclaimed for each allocated object? At each 
subsequent assignment? Or maybe at the end of the block? Or even 
"sometime later"? Or maybe all subsequent assignments are eliminated by 
compiler?

4.

Is it possible to associate some function with object allocated by new, 
which would be called at the time (or maybe after) the object is reclaimed?
Yes, I'm asking about destructors or finalizers.

5.

Is it possible to "overload" new for MyType so that the X := new MyType; 
statement will do whatever *I* want it to do, including actual memory 
allocation? If yes, is it possible to hook on memory reclamation as well?

6.

What about reference cycles between dynamically allocated objects?

declare
    type ListNode;
    type ListNodeRef is access ListNode;
    type ListNode is record
       SomeData : Integer;
       Other : ListNodeRef;
    end record;
    First, Second : ListNodeRef;
begin
    First := new ListNode;
    First.all.SomeData := 7;
    Second := new ListNode;
    Second.all.SomeData := 8;

    First.all.Other := Second;
    Second.all.Other := First; -- cycle
end;

Will the memory be reclaimed?


Regards,


-- 
Maciej Sobczak : http://www.msobczak.com/
Programming    : http://www.msobczak.com/prog/

Re: Memory management clarification

[Adrien Plisson]

Maciej Sobczak wrote:
> Trying to learn a bit of Ada I came across a statement that memory 
> allocated from the pool will be implicitly reclaimed when the acces 
> variable used to reference it goes out of scope.

this is called garbage collection. can you tell us where you read this 
statement ?

if i remember right, garbage collection is _allowed_ by the standard, 
but not _defined_ in the same standard.

the only 2 compilers i can think of implementing a GC are JGNAT and 
MGNAT, 2 niche compilers targeting the JVM and CLI, mainly because the 
GC is a feature of their target platform. i'm not aware of any other 
implementation of a garbage collector, but i may be wrong...

-- 
rien

Re: Memory management clarification

[Frank J. Lhota]

Maciej Sobczak wrote:
> Hi,
> 
> Trying to learn a bit of Ada I came across a statement that memory 
> allocated from the pool will be implicitly reclaimed when the acces 
> variable used to reference it goes out of scope.

No, that is not true. What is true is that if an access type goes out of 
scope, then the data allocated from the pool for that type will be 
reclaimed. See ARM 13.11 (18).

Most Ada implementations do not support garbage collection, and with 
such implementations, your examples would simply create a lot of garbage.

Re: Memory management clarification

[Robert A Duff]

Maciej Sobczak <no.spam@no.spam.com> writes:

> Hi,
> 
> Trying to learn a bit of Ada I came across a statement that memory
> allocated from the pool will be implicitly reclaimed when the acces
> variable used to reference it goes out of scope.

If you use the default storage pool(s), the language standard does not
specify when heap memory is reclaimed.  Most implementations do not
reclaim any such memory unless you explicitly call
Unchecked_Deallocation.

If you put "for T'Storage_Size use 1_000_000;", then implementations
should reclaim all memory allocated for type T when the scope of T is
left.  The *type* -- not individual variables of the type.  This is not
a very useful capability, because most access types need to be at
library level, so the memory won't be reclaimed until the whole program
is done.

You should look up user defined storage pools.  You can say:

    for T'Storage_Pool use My_Pool;

and then you can control when memory will be reclaimed.
You can reclaim all memory in My_Pool whenever you like -- but
beware dangling pointers.

> That's nice, but I would like to learn a bit more about the exact
> mechanics of this and about the guarantees that it can provide.
> 
> Let's say that there is some MyType definition and this:
> 
> type MyTypeRef is access MyType;
> 
> 1.
> 
> declare
>      X : MyTypeRef;
> begin
>     loop
>        X := new MyType;
>     end loop;  -- infinite loop just for the sake of discussion
> end;
> 
> Note that X does not goes out of scope when the loop is executing.
> Will the memory be reclaimed?

No.

>... When? What can be said about the memory
> consumption of such program? Is it bounded and guaranteed?

No.  Unless the implementation supports garbage collection,
you will eventually run out of memory.  Most implementations
do not support GC.

>... Is it
> necessarily larger than without the loop (just single allocation)?
> 
> 2.
> 
> loop
>     declare
>        X : MyTypeRef;
>     begin
>        X := new MyType;
>     end;
> end loop;
> 
> What now? Is this any different from the memory management point of view?

No.  X.all will never be reclaimed (on most implementations).  The only
difference here is that you're allocating only one object.

Suppose we added a call P(X) inside the begin/end.  And suppose P saves
X in a global variable.  The implementation cannot deallocate the memory
X points to, because that would leave a dangling pointer in the global
variable.  A garbage collector's job is to tell whether or not that
happened -- then it can reclaim all memory not reachable.  But most Ada
implementations don't do GC -- they just assume X.all *might* be
reachable, and never reclaim it unless you do U_D.

> 3.
> 
> declare
>     X : MyTypeRef;
> begin
>     X := new MyType;
>     X := new MyType;
>     X := new MyType;
>     X := new MyType;
>     -- ...
> end;
> 
> When is the memory reclaimed for each allocated object? At each
> subsequent assignment? Or maybe at the end of the block? Or even
> "sometime later"? Or maybe all subsequent assignments are eliminated by
> compiler?

Never.  (Well, "never" really means "when the process exits".)

> 4.
> 
> Is it possible to associate some function with object allocated by new,
> which would be called at the time (or maybe after) the object is
> reclaimed?
> Yes, I'm asking about destructors or finalizers.

Yes.  Look up "controlled types".  These allow you to associate a
Finalize operation with a type.  For local variables, Finalize will be
automatically called when the procedure is left.  For heap objects,
Finalize will be called when you do Unchecked_Deallocation (or, if you
never do U_D, when the program is done).

> 5.
> 
> Is it possible to "overload" new for MyType so that the X := new MyType;
> statement will do whatever *I* want it to do, including actual memory
> allocation? If yes, is it possible to hook on memory reclamation as well?

"new" does two things: allocate memory, and initialize it (explicitly or
implicltly).  You can't exactly "overload new", but you can use storage
pools as described above -- this gives you control over the memory
allocation part of "new".  The initialization still happens in the
normal way.

> 6.
> 
> What about reference cycles between dynamically allocated objects?
> 
> declare
>     type ListNode;
>     type ListNodeRef is access ListNode;
>     type ListNode is record
>        SomeData : Integer;
>        Other : ListNodeRef;
>     end record;
>     First, Second : ListNodeRef;
> begin
>     First := new ListNode;
>     First.all.SomeData := 7;
>     Second := new ListNode;
>     Second.all.SomeData := 8;
> 
>     First.all.Other := Second;
>     Second.all.Other := First; -- cycle
> end;
> 
> Will the memory be reclaimed?

Cycles don't make any difference.

- Bob

Re: Memory management clarification

[Robert A Duff]

Adrien Plisson <aplisson-news@stochastique.net> writes:

> the only 2 compilers i can think of implementing a GC are JGNAT and
> MGNAT, 2 niche compilers targeting the JVM and CLI, mainly because the
> GC is a feature of their target platform. i'm not aware of any other
> implementation of a garbage collector, but i may be wrong...

SofCheck also has a JVM-targetted compiler, and it does GC.
A# targets the .NET platform, so I assume it does GC also.

- Bob

Re: Memory management clarification

[Robert A Duff]

"Frank J. Lhota" <NOSPAM.lhota@adarose.com> writes:

> Maciej Sobczak wrote:
> > Hi,
> > Trying to learn a bit of Ada I came across a statement that memory
> > allocated from the pool will be implicitly reclaimed when the acces
> > variable used to reference it goes out of scope.
> 
> No, that is not true. What is true is that if an access type goes out of
> scope, then the data allocated from the pool for that type will be
> reclaimed. See ARM 13.11 (18).

That's not quite true, either.  Most implementations use a global heap
by default, and never automatically reclaim memory.  If you use a
Storage_Size clause on a local access type, then what you say is true.
But local access types are not very useful.

> Most Ada implementations do not support garbage collection, and with
> such implementations, your examples would simply create a lot of garbage.

Right.

- Bob

Re: Memory management clarification

[Maciej Sobczak]

Robert A Duff wrote:

> If you use the default storage pool(s), the language standard does not
> specify when heap memory is reclaimed.  Most implementations do not
> reclaim any such memory unless you explicitly call
> Unchecked_Deallocation.

OK.

> If you put "for T'Storage_Size use 1_000_000;", then implementations
> should reclaim all memory allocated for type T when the scope of T is
> left.

Nice. Why putting this arbitrary limit?

And what does it mean, anyway - is the pool actually pre-allocated with 
this size when the for..use... statement is executed, or does it start 
empty and later "inflates" as necessary, but no bigger than the given limit?
The difference is not only the observable memory consumption (even when 
not the whole pool is used), but also the possibility and timing of 
low-memory errors.

> This is not
> a very useful capability, because most access types need to be at
> library level, so the memory won't be reclaimed until the whole program
> is done.

Indeed, not really useful.

> You should look up user defined storage pools.  You can say:
> 
>     for T'Storage_Pool use My_Pool;
> 
> and then you can control when memory will be reclaimed.
> You can reclaim all memory in My_Pool whenever you like -- but
> beware dangling pointers.

I have to beware them when using Unchecked_Deallocation as well. :)


>>2.
>>
>>loop
>>    declare
>>       X : MyTypeRef;
>>    begin
>>       X := new MyType;
>>    end;
>>end loop;
>>
>>What now? Is this any different from the memory management point of view?
> 
> No.  X.all will never be reclaimed (on most implementations).  The only
> difference here is that you're allocating only one object.

Not really - there's a loop.
I understand that the code above leaks memory, just like my first example.


> Suppose we added a call P(X) inside the begin/end.  And suppose P saves
> X in a global variable.  The implementation cannot deallocate the memory
> X points to, because that would leave a dangling pointer in the global
> variable.

Right, but I was interested exactly in the case where there is just one 
reference and it is trivial for the compiler to prove that the object is 
not aliased. But without GC there's no difference anyway.


>>4.
>>
>>Is it possible to associate some function with object allocated by new,
>>which would be called at the time (or maybe after) the object is
>>reclaimed?
>>Yes, I'm asking about destructors or finalizers.
> 
> Yes.  Look up "controlled types".  These allow you to associate a
> Finalize operation with a type.  For local variables, Finalize will be
> automatically called when the procedure is left.

Good - this, basically, should allow me to implement some form of local 
resource manager (in C++ this idiom is called RAII) that will deallocate 
the object (or any other resource) when the scope is left.

> For heap objects,
> Finalize will be called when you do Unchecked_Deallocation (or, if you
> never do U_D, when the program is done).

Fine. Is the order of calling finalizers well-defined for the latter case?


Thank you for these explanations,

-- 
Maciej Sobczak : http://www.msobczak.com/
Programming    : http://www.msobczak.com/prog/

Re: Memory management clarification

[Robert A Duff]

Maciej Sobczak <no.spam@no.spam.com> writes:

> Robert A Duff wrote:
> > If you put "for T'Storage_Size use 1_000_000;", then implementations
> > should reclaim all memory allocated for type T when the scope of T is
> > left.
> 
> Nice. Why putting this arbitrary limit?

You can put any limit you like.  It does not need to be known at compile
time.

Note that this feature is inherited from Ada 83.  It is subsumed by
storage pools (added in Ada 95).

> And what does it mean, anyway - is the pool actually pre-allocated with
> this size when the for..use... statement is executed, or does it start
> empty and later "inflates" as necessary, but no bigger than the given
> limit?
> The difference is not only the observable memory consumption (even when
> not the whole pool is used), but also the possibility and timing of
> low-memory errors.

It means approximately 1_000_000 storage units are *reserved* for this
type.  You are guaranteed to be able to allocate (approx) that much.
One possible implementation is to allocate that space on the stack of
the current procedure, and allocate the heap objects within that.
Then it gets automatically freed when the procedure returns.

But the implementation is not required to consume the memory -- for
example, it can allocate *virtual* address space, but not physical
memory or swap space.

The timing of out-of-memory errors (Storage_Error exception) is a
problem anyway -- according to the standard, you can get Storage_Error
at any time.

If you don't like the "reserve arbitrary limit" semantics, you can write
your own storage pool type that has whatever semantics you like.  For
example, reserve nothing, but still deallocate on procedure return.
The Finalize of the storage pool type comes in handy for that.

> > This is not
> > a very useful capability, because most access types need to be at
> > library level, so the memory won't be reclaimed until the whole program
> > is done.
> 
> Indeed, not really useful.
> 
> > You should look up user defined storage pools.  You can say:
> >     for T'Storage_Pool use My_Pool;
> > and then you can control when memory will be reclaimed.
> > You can reclaim all memory in My_Pool whenever you like -- but
> > beware dangling pointers.
> 
> I have to beware them when using Unchecked_Deallocation as well. :)

Indeed.  ;-)

> >>2.
> >>
> >>loop
> >>    declare
> >>       X : MyTypeRef;
> >>    begin
> >>       X := new MyType;
> >>    end;
> >>end loop;
> >>
> >>What now? Is this any different from the memory management point of view?
> > No.  X.all will never be reclaimed (on most implementations).  The only
> > difference here is that you're allocating only one object.
> 
> Not really - there's a loop.
> I understand that the code above leaks memory, just like my first example.

Yes, both leak memory.  The loop probably leaks faster.  ;-)

> > Suppose we added a call P(X) inside the begin/end.  And suppose P saves
> > X in a global variable.  The implementation cannot deallocate the memory
> > X points to, because that would leave a dangling pointer in the global
> > variable.
> 
> Right, but I was interested exactly in the case where there is just one
> reference and it is trivial for the compiler to prove that the object is
> not aliased.

I don't know of any compiler that does this trivial proof.
It's such a special case that it wouldn't be all that useful anyway.

>... But without GC there's no difference anyway.
> 
> 
> >>4.
> >>
> >>Is it possible to associate some function with object allocated by new,
> >>which would be called at the time (or maybe after) the object is
> >>reclaimed?
> >>Yes, I'm asking about destructors or finalizers.
> > Yes.  Look up "controlled types".  These allow you to associate a
> > Finalize operation with a type.  For local variables, Finalize will be
> > automatically called when the procedure is left.
> 
> Good - this, basically, should allow me to implement some form of local
> resource manager (in C++ this idiom is called RAII) that will deallocate
> the object (or any other resource) when the scope is left.

Right -- it's pretty much the same as in C++.

> > For heap objects,
> > Finalize will be called when you do Unchecked_Deallocation (or, if you
> > never do U_D, when the program is done).
> 
> Fine. Is the order of calling finalizers well-defined for the latter case?

I don't remember the exact rules.  The order is somewhat left up to the
implementation, but you'd have to read the RM to understand the details.

> Thank you for these explanations,

You're welcome.

- Bob

Re: Memory management clarification

[Frank J. Lhota]

Robert A Duff wrote:
> "Frank J. Lhota" <NOSPAM.lhota@adarose.com> writes:
> That's not quite true, either.  Most implementations use a global heap
> by default, and never automatically reclaim memory.  If you use a
> Storage_Size clause on a local access type, then what you say is true.
> But local access types are not very useful.

You're right, I left out the Storage_Size condition.

Although local access types are very rare, I have seen code where a 
local access type is used to create a temporary structure that is used 
for the subprogram call, then conveniently goes away when the subprogram 
completes. So I wouldn't say that local access types are not very 
useful, just not very common.