I’ve been researching about Ada the last few days an one thing leaves me quite puzzled:
I’ve read quite a bit that in a lot of situations ADA doesn’t need to use the Heap. but how does that work?
For example when I get a string from user input, I can’t know the length of it so I have to allocate it on the heap. Or If I have a growable array/Vector it needs to be put on the heap, right?
How does Ada handle these?
I’ve read something about Ada being able to do dynamic allocations on the stack but I thought that should be impossible as the stack frame is fixed from the moment a function is called?
I thought thats the whole Point of the stack: It’s fast and efficient, but fixed so if you want to initialize something with a size unknown at compile time, you have to use the Heap.
And since the data section is also set at compile time, I assume it has similar limitations
When you define a variable in a subprogram (procedure/function), the compiler allocates space on the stack, just like it would in any other language.
The data you define in packages are compiled and the compiler allocates space within the program’s data section, the linker collects those sections and places them together in the right places.
As for returning large objects, GNAT uses a secondary stack, but other compilers have used the normal stack frames.
Look at pools for dynamic memory, the heap is one pool.
GNAT’s documentation on primary and secondary heap says a separate, task-specific secondary stack is provided:
To accommodate such returns, GNAT provides each task with a separate secondary stack that objects of unconstrained types are returned on.
This stack is allocated from the heap except in a few cases when the size is known at compile time:
Memory for dynamically-sized secondary stacks is assigned from the heap except for the initial stack allocation for tasks declared at the library level that use the default secondary stack size.
For reduced runtimes profiles (Light, Light-Tasking and Embedded run-times) the solution is static allocation, with the default being 20kb.
Fixed-size secondary stacks are generally allocated from a pool of static default-sized secondary stacks generated by gnatbind
So if I understand well to say Ada doesn’t need the heap is technically wrong… It uses it invisibly, with automatic GC when the object is out of scope.
No, you can write entire programs without the heap, in your program. If the runtime uses the heap underneath, then yeah, but most of the time you can do without it.
But dealing with C imports, you’ll use the heap still in places, usually on the C side.
Memory for dynamically-sized secondary stacks is assigned from the heap except for the initial stack allocation for tasks declared at the library level that use the default secondary stack size.
What does this mean then ? It’s still memory allocated at run-time. Or else please explain technically how are managed unconstrained function results. Yes you can do without, says the documentation, but then you can’t return unconstrained arrays or indefinite types (with no max size indicated I assume).
If you avoid function returns such as for Spark mode then you do not need a secondary stack. Heap can be freed at any time logically within a subroutine with the dangers that causes which incidentally can now be avoided with Sparks borrowing features. Actually I have had the interesting result that I often preferred the code without functions as it was more obvious what was going on. YMMV.
The key with Adas stack is packages and procedures (scope), declare blocks and Adas array features . You can leverage these to control when stack is allocated and freed and because it is based on predictable code flow patterns actually it is faster and automatically compact/alligned. On embedded targets I basically set the heap to most of my memory. For me it replaces the heap as arrays have always turned out to be more suitable so far but there are some cases like minimally sized binary trees that would require the heap to be used. You can see the difference if you look at Booch 83 components in particular the bounded and unbounded variants. There is a book “software conponents with Ada” that describes them. Also bear in mind that Ada has the option of pools now too but it’s upto you if you find them useful or not.
procedure Do_Something is
begin
-- Do some code here
-- Later On:
declare
-- This string's length is known only at runtime and
-- is allocated on the stack
Line : String := Ada.Text_IO.Get_Line;
begin
-- Do some stuff with the Line variable
-- Line is deallocated from the stack here
end;
end Do_Something;
As for the “how”: This is compiler specific. GNAT uses frame registers to grow and shrink the stack for the declare block on at least some platforms. It also uses a secondary stack to do the function return. I don’t tknow how it handles all platforms though.
Stacks have a fixed maximum. If you allocate a string that is too big for the stack, then Ada does stack checking and will generate an exception in those cases for you. You can then decide if you want the stack size for your task if you feel it makes sense.
NOTE that for some platforms GNAT does invoke the heap for their secondary stack if you allocate too much for the stack. But you can swap out the runtime for one does not and instead raises an exception. This is sometimes seen in embedded runtimes where heap may not be allowed. Also note that the heap invocation in this case would be temporary in order to get the object onto the larger primary stack and the compiler manages all that internally. That said the secondary stack is rather large. It’s pretty rare for GNAT to need it.
task T
with Storage_Size => 10240,
Secondary_Stack_Size => 1024;
where Storage_Size is the task’s stack size, Secondary_Stack_Size is the task’s secondary stack size.
I’m not sure what happens in AdaCore’s embedded or native runtimes, but in FreeRTOS_Ada the task’s stack is allocated from the heap (at program initialisation - this is Ravenscar, so the task isn’t allowed to terminate). If the secondary stack size isn’t specified, it’ll take a part of the task’s stack; if it is_specified, it’s statically created (in BSS) by the compiler (unless it’s zero, in which case it can’t be used). Both kinds of stack are fixed size.
I think about 7-8 years or so ago, I grabbed a copy of one of your s-secsta.ads/adb on Sourceforge to add to my near zfp runtime. I didn’t have a tasking system, so I modified it to use a library level chunk from BSS only.
IMO, the absolute best way to answer that is with this video.
No.
As explained in the video: because in Ada you can initialize an unconstrained array-type to a particular size, you can then perfectly size your buffer to the data, instead of either (a) making it so big nothing bad happens, or (b) guessing on a “reasonable” size.
Example:
Declare
Function Prompt( Text : String ) return String is
Begin
Ada.Text_IO.Put_Line( Text );
Return Ada.Text_IO.Get_Line;
End Prompt;
-- Here we size 'Buffer' to the length of the User's input,
-- initializing it with the text returned; no buffer overflow.
Buffer : Constant String := Prompt_User( "What is your name?" );
Begin
Ada.Text_IO.Put_Line( "Ah, so your name is '" & Buffer & "'." );
End Example;
Ah, that’s where Ada’s declarative region comes in: w/i the declarative-region things are “elaborated”, and that elaboration can involve assigning values.
There are several techniques that can be used, one is the usage of a second stack, another is to “nest” your stack-frames, and I’m sure there’s some implementations [DOTNET or JVM?] where the dynamic/actual-data is in the heap but the reference/pointer is fixed-size and so makes no complication for the stack-frame.
Also, I get the feeling that calling-conventions can play a role here. (IIRC, the Pascal calling convention is that the callee cleans up, which means that insofar as the caller is concerned, all calls are the same; this is ‘foggy’ half-remembrance though.)
As I noted in another thread, a task with Stack_Storage_Size specified has its stack created by the compiler in - I think - BSS, & “just” needs setting up.
In addition to strings, like what many have already shown, you can do this with arrays too.
For example:
type My_Array is array (Positive range <>) of Integer;
You can have a function return an arbitrary length record by doing:
function Gen_Array (Length : Positive) return My_Array is
Result : constant My_Array (1 .. Length) :=
[for I in 1 .. Length => I];
begin
return Result;
end Gen_Array;
Or you can simply create a new array of arbitrary size at runtime; for example, I get a number from the user with Input : constant String := Get_Line;, I can then allocate the array later on using N : My_Array (1 .. Positive'Value (Input));
Here’s a fully working program to give you an idea of what I mean:
pragma Ada_2022;
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Characters.Handling; use Ada.Characters.Handling;
procedure Test_Dynamic is
type My_Array is array (Positive range <>) of Integer;
-- Dynamically generate an array of a given type.
function Gen_Array (Length : Positive) return My_Array is
Result : constant My_Array (1 .. Length) :=
[for I in 1 .. Length => I];
begin
return Result;
end Gen_Array;
begin
loop
Put_Line ("Enter a positive number for array or Q to exit.");
declare
-- This string is dynamically generated from user input
-- It is the exact size of the input needed.
Input : constant String := Get_Line;
begin
exit when To_Lower (Input) = "q";
declare
-- Create the dynamic array by passing in the length
M : My_Array := Gen_Array (Positive'Value (Input));
-- This also works
N : My_Array (1 .. Positive'Value (Input));
begin
N := M;
for X of M loop
Put (X'Image);
end loop;
for X of N loop
Put (X'Image);
end loop;
New_Line;
end;
exception
when others =>
-- Conversion failed, let user know.
Put_Line ("Invalid number.");
end;
end loop;
end Test_Dynamic;
I don’t have access to a computer today to test, but won’t you easily get a stack overflow with rather small values that would be otherwise avoided with a heap allocation (that accept bigger objects than the stack) ?
Yes by default on Linux it is set to something like 2000k? There is no technical reason for the stack limit on 64 bit linux with a huge virtual address space these days and it is set far lower than it should be on 32 bit. OOM killing by the kernel behaves similarly to the heap as stack so the limit can be removed entirely. Root can raise the soft limit. Stack is actually faster than the heap too. On embedded the stack is reserved but on Linux it grows without the limit. Interestingly I reserve more than Linux soft limits (by default) on one 12mm 32 bit cortex-m33 microchip.
It is also worth bearing in mind that Sparks new borrowing can be applied just to e.g. a container package or even a procedure and even prevents memory leaks. It looks far easier to use to me than Rusts borrowing too.
Ada provides stack checking, so it will raise Storage_Error (for GNAT you may have to enable it… I don’t recall if they turn that on by default or not (see -fstack-check switch). That said, unless you are doing large data processing, the stack is usually big enough to handle what most Ada programmers use it for. I’ve been developing in Ada since 2004 and I’ve run into the stack limit once and I use stack allocated indefinite objects all the time. When I do large data processing, I do go to heap allocated objects like vectors and indefinite holders.