Storage Pools and alloca

Storage Pools and alloca

[Frank J. Lhota]

C / C++ sometimes cut down on the hassles of memory management by using the
"alloca" function. The "alloca" function, which is frequently implicit,
allocates storage from the stack. Since memory allocated by "alloca" is on
the stack, it is reclaimed automatically as soon as the function that
allocated this memory returns.

AFAIK, the "alloca" functionality could be added to Ada using the storage
pool facility. One could derive a type from
System.Storage_Pools.Root_Storage_Pool and write the required subprograms
for this type as follows:

    - The Allocate procedure would allocate memory from the stack, sort of
like the C "alloca" function;
    - The Deallocate procedure should do nothing; and
    - The Storage_Size should return the amount of space left on the stack.

Of course, this is highly platform dependant, and would often require
machine code insertions.

Questions:

    1) Does any Ada compiler provide this type of storage pool?
    2) If this type of storage pool was available, would you find it useful?
    3) Would an "alloca" storage pool be a worthwhile addition to Ada 0x?

Re: Storage Pools and alloca

[Matthew Heaney]

"Frank J. Lhota" <NOSPAM.lhota.adarose@verizon.net> wrote in message
news:PHWq9.20400$nb.8357@nwrddc02.gnilink.net...
>
> AFAIK, the "alloca" functionality could be added to Ada using the storage
> pool facility.

Someone already had that idea 25 years ago:

procedure Op (N : Natural) is
   S : String (1 .. N);
begin


>     1) Does any Ada compiler provide this type of storage pool?
Yes -- all of them.

>     2) If this type of storage pool was available, would you find it
useful?
Yes.  I do already.

>     3) Would an "alloca" storage pool be a worthwhile addition to Ada 0x?
No, because it's already part of the language.

Re: Storage Pools and alloca

[Frank J. Lhota]

I should have been a little clearer. Ada has always allowed a programmer to
locally declare an object whose size can only be determined at runtime, and
this facility can be used in many places where C programmers would use
"alloca". The way I should have worded this question is that given Ada's
ability to declare dynamically sized objects, is there ever a need for an
"alloca" storage pool? My educated guess would be no, but I thought it might
be worthwhile to run this idea past the Ada community.

Re: Storage Pools and alloca

[David C. Hoos]

----- Original Message -----
From: "Frank J. Lhota" <NOSPAM.lhota.adarose@verizon.net>
Newsgroups: comp.lang.ada
To: <comp.lang.ada@ada.eu.org>
Sent: Tuesday, October 15, 2002 12:26 PM
Subject: Re: Storage Pools and alloca


> I should have been a little clearer. Ada has always allowed a programmer
to
> locally declare an object whose size can only be determined at runtime,
and
> this facility can be used in many places where C programmers would use
> "alloca". The way I should have worded this question is that given Ada's
> ability to declare dynamically sized objects, is there ever a need for an
> "alloca" storage pool? My educated guess would be no, but I thought it
might
> be worthwhile to run this idea past the Ada community.
The use of "declare blocks" in Ada is equivalent to the use of alloca in C.

For example:

declare
   The_String : constant String :=
<some-string-expression-of-unknown-length>;
begin
   <use The_String in some statement(s)>
end; -- The_String "deallocated" here where it goes out of scope

Re: Storage Pools and alloca

[Robert A Duff]

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

> C / C++ sometimes cut down on the hassles of memory management by using the
> "alloca" function. The "alloca" function, which is frequently implicit,
> allocates storage from the stack.

What do you mean by "frequently implicit"?

>... Since memory allocated by "alloca" is on
> the stack, it is reclaimed automatically as soon as the function that
> allocated this memory returns.
> 
> AFAIK, the "alloca" functionality could be added to Ada using the storage
> pool facility. One could derive a type from
> System.Storage_Pools.Root_Storage_Pool and write the required subprograms
> for this type as follows:
> 
>     - The Allocate procedure would allocate memory from the stack, sort of
> like the C "alloca" function;
>     - The Deallocate procedure should do nothing; and
>     - The Storage_Size should return the amount of space left on the stack.

Storage_Size is supposed to return the amount of "reserved" space,
which in virtual memory systems might be zero.  ('Storage_Size is kind of
useless, actually.  I've never written a program that queried
'Storage_Size.  Has anybody?)

> Of course, this is highly platform dependant, and would often require
> machine code insertions.
> 
> Questions:
> 
>     1) Does any Ada compiler provide this type of storage pool?

I believe the GNAT compiler uses a storage pool to implement
dynamically-sized stack objects.  I think most other compilers
don't use a storage pool per se, but use essentially the same
run-time mechanisms as alloca.  (I know of one Ada 83 compiler
that used heap allocation to implement the Ada features -- but I
think an alloca-like mechanism is better.)

I don't see any reason to use such a storage pool directly.
Ada's dynamically-sized stack objects seem to do everything
alloca can do, but more safely.  In fact, the Ada mechanism is
more powerful, since you can return unknown-sized objects from
functions.  (I mean, unknown size at the call site -- the size is
fixed at the point of "return" in the called function.  Like when
the spec of the function says "return String".)

>     2) If this type of storage pool was available, would you find it useful?

No.

>     3) Would an "alloca" storage pool be a worthwhile addition to Ada 0x?

No, I don't think so.  There's alloca-like stuff going on behind the
scenes in Ada, but I don't see why a programmer would want direct access
to that mechanism.

Can you think of any case (in C or C++) that uses alloca, but can't be
easily translated into the existing Ada mechanisms?  I can't.

- Bob

Re: Storage Pools and alloca

[Frank J. Lhota]

"Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message
news:wcczntfikew.fsf@shell01.TheWorld.com...
> "Frank J. Lhota" <NOSPAM.lhota.adarose@verizon.net> writes:
>
> > C / C++ sometimes cut down on the hassles of memory management by using
the
> > "alloca" function. The "alloca" function, which is frequently implicit,
> > allocates storage from the stack.
>
> What do you mean by "frequently implicit"?

By that I mean the declaration of "alloca" is often followed by

    #pragma implicit( alloca )

> >...
>
> Storage_Size is supposed to return the amount of "reserved" space,
> which in virtual memory systems might be zero.  ('Storage_Size is kind of
> useless, actually.  I've never written a program that queried
> 'Storage_Size.  Has anybody?)

I haven't. By its very nature, the value returned is inexact, which limits
its usefulness.

> > Of course, this is highly platform dependant, and would often require
> > machine code insertions.
> >
> > Questions:
> >
> >     1) Does any Ada compiler provide this type of storage pool?
>
> I believe the GNAT compiler uses a storage pool to implement
> dynamically-sized stack objects.  I think most other compilers
> don't use a storage pool per se, but use essentially the same
> run-time mechanisms as alloca.  (I know of one Ada 83 compiler
> that used heap allocation to implement the Ada features -- but I
> think an alloca-like mechanism is better.)

I recall that the first Alsys compilers actually used a mixed approach to
stack objects: if an object was small enough, it would be allocated on the
stack, otherwise it would be allocated from the heap. There was a compiler
option that specified the maximum size for stack allocations.

> I don't see any reason to use such a storage pool directly.
> Ada's dynamically-sized stack objects seem to do everything
> alloca can do, but more safely.  In fact, the Ada mechanism is
> more powerful, since you can return unknown-sized objects from
> functions.  (I mean, unknown size at the call site -- the size is
> fixed at the point of "return" in the called function.  Like when
> the spec of the function says "return String".)

The consensus seems to be that such a storage pool would not be necessary.

> >     2) If this type of storage pool was available, would you find it
useful?
>
> No.
>
> >     3) Would an "alloca" storage pool be a worthwhile addition to Ada
0x?
>
> No, I don't think so.  There's alloca-like stuff going on behind the
> scenes in Ada, but I don't see why a programmer would want direct access
> to that mechanism.
>
> Can you think of any case (in C or C++) that uses alloca, but can't be
> easily translated into the existing Ada mechanisms?  I can't.

Neither can I, but I thought it would be worthwhile to run this idea past
other Ada programmers. As you said, most (all?) Ada compilers perform an
"alloca" in the background; the question is whether it is worthwhile or even
desirable to bring this to the foreground. So far, all replies have
indicated  no desire to bring this to the foreground.

The next time ACT-Europe revises the document "Common C/C++/Java Pitfalls &
How Ada Avoids Them" document, they may wish to include something about how
Ada can create a dynamically sized stack object with the hassles and dangers
of "alloca" calls.

Thanks to everyone for your feedback.

Re: Storage Pools and alloca

[Robert A Duff]

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

> "Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message
> news:wcczntfikew.fsf@shell01.TheWorld.com...
> > "Frank J. Lhota" <NOSPAM.lhota.adarose@verizon.net> writes:
> >
> > > C / C++ sometimes cut down on the hassles of memory management by using
> the
> > > "alloca" function. The "alloca" function, which is frequently implicit,
> > > allocates storage from the stack.
> >
> > What do you mean by "frequently implicit"?
> 
> By that I mean the declaration of "alloca" is often followed by
> 
>     #pragma implicit( alloca )

Sorry, I don't know what that pragma means.  Please explain.
Is it standard C or C++?

> I recall that the first Alsys compilers actually used a mixed approach to
> stack objects: if an object was small enough, it would be allocated on the
> stack, otherwise it would be allocated from the heap. There was a compiler
> option that specified the maximum size for stack allocations.

That's not the issue I meant (although I admit I didn't make that
clear).  Yes, some machines (of those days) required that stack frames
be fairly small, so if a really big object is declared in a procedure,
it should be allocated indirectly.

The issue I was talking about was return of caller-unknown-size things.
So of we have "function F(...) return String", and it says "return
Blah", Blah would be copied to the heap, and the address of that heap
object returned, and the caller would be responsible for deallocating
it.  IMHO, that's not the best way to do it.

> The next time ACT-Europe revises the document "Common C/C++/Java Pitfalls &
> How Ada Avoids Them" document, they may wish to include something about how
> Ada can create a dynamically sized stack object with the hassles and dangers
                                                  ^^^^ ;-)
> of "alloca" calls.

Funny typo.  ;-)

- Bob

Re: Storage Pools and alloca

[Frank J. Lhota]

"Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message
news:wccvg43ift4.fsf@shell01.TheWorld.com...
> > By that I mean the declaration of "alloca" is often followed by
> >
> >     #pragma implicit( alloca )
>
> Sorry, I don't know what that pragma means.  Please explain.
> Is it standard C or C++?

GAHHH! Sorry, my mistake, I meant to say intrinsic, not implicit. I cannot
even blame this error on my spell checker, my only excuse for such a stupid
typo is that I ran out of coffee yesterday. Never again will I post anything
before I've had coffess.

> > The next time ACT-Europe revises the document "Common C/C++/Java
Pitfalls &
> > How Ada Avoids Them" document, they may wish to include something about
how
> > Ada can create a dynamically sized stack object with the hassles and
dangers
>                                                   ^^^^ ;-)
> > of "alloca" calls.
>
> Funny typo.  ;-)

Once again, this demonstrates that although Java the language is not
essential to my work, Java the beverage definitely is.

Re: Storage Pools and alloca

[Eric G. Miller]

In <0P_q9.20625$nb.4430@nwrddc02.gnilink.net>, Frank J. Lhota wrote:

> 
> "Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message
> news:wcczntfikew.fsf@shell01.TheWorld.com...
>> "Frank J. Lhota" <NOSPAM.lhota.adarose@verizon.net> writes:
>>
>> > C / C++ sometimes cut down on the hassles of memory management by using
> the
>> > "alloca" function. The "alloca" function, which is frequently implicit,
>> > allocates storage from the stack.
>>
>> What do you mean by "frequently implicit"?
> 
> By that I mean the declaration of "alloca" is often followed by
> 
>     #pragma implicit( alloca )

Errm, but "alloca" is not a standard C memory mechanism -- even if it is
available on a number of platforms. And "pragma" in C is almost 100%
platform/compiler specific...

Re: Storage Pools and alloca

[Frank J. Lhota]

"Eric G. Miller" <egm2@jps-nospam.net> wrote in message
news:pan.2002.10.16.07.36.41.561696@jps-nospam.net...
> Errm, but "alloca" is not a standard C memory mechanism -- even if it is
> available on a number of platforms. And "pragma" in C is almost 100%
> platform/compiler specific...

The "alloca" function falls into the category of a 90% standard function;
although it is not required, nearly all platforms provide it. There are a
number of functions like this in C; the very useful "strdup" function was
not officially part of the standard until 1999.

Re: Storage Pools and alloca

[Eric G. Miller]

In <W0er9.42833$qb.15347@nwrddc01.gnilink.net>, Frank J. Lhota wrote:

> 
> "Eric G. Miller" <egm2@jps-nospam.net> wrote in message
> news:pan.2002.10.16.07.36.41.561696@jps-nospam.net...
>> Errm, but "alloca" is not a standard C memory mechanism -- even if it is
>> available on a number of platforms. And "pragma" in C is almost 100%
>> platform/compiler specific...
> 
> The "alloca" function falls into the category of a 90% standard function;
> although it is not required, nearly all platforms provide it. There are a
> number of functions like this in C; the very useful "strdup" function was
> not officially part of the standard until 1999.

AFAIK, strdup is *not* part of the C99 standard (BSD, SVID, etc...).  I
don't know why it isn't (it's a trivial but useful function). 

C99 VLA's possibly meet many of the alloca use cases.

Re: Storage Pools and alloca

[Simon Wright]

Robert A Duff <bobduff@shell01.TheWorld.com> writes:

> Storage_Size is supposed to return the amount of "reserved" space,
> which in virtual memory systems might be zero.  ('Storage_Size is
> kind of useless, actually.  I've never written a program that
> queried 'Storage_Size.  Has anybody?)

We have used Storage_Size clauses where

  we want to use new/unchecked deallocation rather than managing
  storage reclamation by hand

  we know the maximum number of instances

  we don't want to have lots of malloc/free churn because of rumours
  about its performance

  we don't want to have lots of malloc/free churn because of heap
  fragmentation issues (long-running embedded system, no memory
  management)

As an example, for a maximum on 4 instances,

   type Handle is access Instance;
   for Handle'Storage_Size use Instance'Object_Size / 8 * 4;

(I know see that perhaps I should have used the standard
'Max_Size_In_Storage_Elements rather than the GNAT 'Object_Size. Oh
well, easy to change that sort of thing with a code generator!)


As for querying it, well, I think you may be right ..