Sum of an entire array in specification package in compilation time

General
1

Sorry if it’s a really basic question. Im looking for a way to get the sum of entire array in compilation time to avoid Ravenscar profile “No_Implicit_Heap_Allocation” restriction

the “problematicVariable” raises a “No_Implicit_Heap_Allocation_Error”.
the “NoproblemVariable” is working… but need a lot of mechanical work…specially becouse the type MyLargeEnumerationtype could grow until thousands of elements…

¿Any ideas for a solution that will not need to write every element of the enumeration in the sum?
Here is the code:

pragma Profile (Ravenscar);
package Constants is

type MyLargeEnumerationtype is ( e1, e2, e3);
type MyBoringTableType is array (MyLargeEnumerationtype) of Natural;
M : constant MyBoringTableType :=
   ( e1  => 5,
     e2 => 8,
    e3 => 11);
Sum_Of_Boring_Table : constant Natural :=
(M (e1) + M(e2) + M(e3));
function FunctionSum return Natural;
end Constants;

package body Constants is
   function FunctionSum return Natural is
      Sum : Natural := 0;
   begin
      for I in M'Range loop
         Sum := Sum + M(I);
      end loop;
      return Sum;
   end FunctionSum;
end Constants;

pragma Profile (Ravenscar);
with constants; use constants;
package test is
   type KnowedSizetype is array ( 1 .. Sum_OF_Boring_Table) of Natural;
   type notknowedSizeType is array ( 1 .. functionsum) of Natural;
   NoproblemVariable : KnowedSizetype;
   ProblematicVariable : notknowedSizeType;   
end test;
2

Ok, first off could you edit your post to delimit/enclose the code with three backticks? (`) This will activate the code-formatter on the forum.

Second, have you tried to make a separate package for the type-definitions in a pure package? This will help in that pure packages are forbidden to have state. Then, for the package Constants, making it pure (or preelaborate).

3

The “reduction expression” is a natural way to sum all of the elements of an array. See Ada RM 4.5.10. Given an array A, you can write A'Reduce("+", 0) and immediately get the result of combining all of the components of A using the “+” operator, with the result initialized to zero before beginning the summation.

2 Likes
4

Just as a side note, I copy/pasted your code into an online Ada compiler, changed the illegal characters (it probably didn’t support wide_wide text) and it compiled without any errors. No mention of heap allocation. Can you clarify what line is giving you the heap allocation error?

Reference: Online Compiler and Editor/IDE for Java, C, C++, PHP, Python, Ruby, Perl - Code and Run Online

5

I think the code had been re-typed … .. was rendered as an ellipsis (three dots), and a tick was rendered as a smart apostrophe.

The line giving the error was the last but one, in which ProblematicVariable was declared.

6

hello, thank you for the formatting tip.
I’ve tried to use your workaround:

package types is
   pragma pure (types);
   type MyLargeEnumerationtype is ( e1, e2, e3);
   type MyBoringTableType is array (MyLargeEnumerationtype) of Natural;   
end types;

and for Constants:

with types; use types;
package Constants is
pragma Preelaborate;

M : constant MyBoringTableType :=
( e1  => 5,
  e2 => 8,
  e3 => 11);

Sum_Of_Boring_Table : constant Natural :=
(M (e1) + M(e2) + M(e3));

I finally get error “non-static constant in preelaborated unit” pointing to the line:
(M (e1) + M(e2) + M(e3));

7

Thank you very much for your advice.
I needed to recompile using -gnat2022 flag

I’ve use this:

function F_Sum return Natural is (M'Reduce("+",0));

It’s working making the sum of all elements, It’s much more elegant and compact than using a body and everything get defined in the specification… but unfortunately it still triggering the Implicit Heap Allocation restriction.

8

but unfortunately it still triggering the Implicit Heap Allocation restriction.

That seems weird, since there is nothing that requires any allocation of a large temporary in M'Reduce(...). I could believe that some other part of your code requires heap allocation, but not this use of the Reduce attribute.

9

It seems that the allocation error is raised in any variable which dimension depends of a function call , or M’Reduce… etc …
examples:

total : constant Natural := M(e1) + M(e2) + M(e3);  --and here I need to manually add another thousands elements with the real size that M array could be..

a : array ( 1 .. F_Sum) of integer; -- raises an error
b : array ( 1 .. M'Reduce("+"),0) of Integer; -- raises an error
c : array ( 1 .. total) of Integer;  -- It's ok
```
10

Did you try the following:

Total : constant Natural := M'Reduce("+", 0);
B : array (1 .. Total) of Integer;

There should be no need to allocate from the heap, though the secondary stack might be used.

11

I’ve seen some secondary stacks do a heap allocation if the needed size was above a certain threshold.

12

(Q: Is there a secondary stack during elaboration?)

I tried this (GCC 14.1.0):

     1. pragma Profile (Ravenscar);
     2. pragma Ada_2022;
     3. package Issue_105 is
     4.    type Table is array (Natural range <>) of Integer;
     5.    Values : constant Table := [1, 2, 3];
     6.    Another_Table : Table (1 .. Values'Reduce ("+", 0));
           |
        >>> error: violation of restriction "No_Implicit_Heap_Allocations"
        >>> error: from profile "Ravenscar" at line 1

     7. end Issue_105;

 7 lines: 2 errors

Looking at the expanded code (with -gnatG) I can’t see any reason for claiming heap allocation. There is elaboration code, unsurprisingly, a very plain loop.

Also, what does it mean “2 errors”?

I think this is worth a bug report

13

I suppose it is possible that the heap is used rather than the secondary stack for library-level objects whose size is not known at compile-time. I’ll let someone more familiar with the GNAT run-time model to answer that, and your other question!

14

Thinking about it some more, you can see that it’s one thing to declare a definite object at compile time and assign a value during elaboration, but quite another if the object is indefinite. So using heap allocation (which is what the code does if you remove the Ravenscar requirement) is the Right Thing. We shouldn’t (I wouldn’t) expect the compiler to cater for what’s probably an unusual use case for this feature, where the requred size could in an ideal world be calculated beforehand.

15

The problem here is that the result of 'Reduce is not static, even if all its inputs are. So any expression involving a result of 'Reduce cannot be static.
E.g.

Another_Table : Table (1 .. Values'Reduce ("+", 0));

will never be static and therefore can only be evaluated at runtime.

For this to work there needs to be a compiler optimization on 'Reduce that understands its purpose and is able to execute it. While it may sounds easy for a sum, the other part is that the first argument of 'Reduce is a reference to a function. I’m not too familiar with 'Reduce itself but from what I can tell the function can be anything:

Non_Const : Integer := 42;

function Non_Const_F (L, R: Integer) return Integer is
   (L + R + Non_Const);

type I_Array is array (range <>) of Integer;

Const_Array : constant I_Array (1 .. 10) := (1, ..., 10);

Const_Var : constant Integer := Const_Array'Reduce (Non_Const_F, 0);

While all direct inputs to 'Reduce are theoretically static the reducer has non-static inputs. The same could be true for side effects for example.

I’m not saying that a compiler optimization that can do it is impossible, but it certainly isn’t trivial, which is probably one of the reasons this doesn’t work.

1 Like
16

EDIT: Just to clarify, this is not a disagreement with your post, just wanted to toss out some clarifying stuff below. You touched on it obviously as well.

Just wanted to clarify that for new readers this statement isn’t true in general (but can be true in specific cases). It is true that since Reduce is not static, that it is never guaranteed to be static. That said, the compiler can (and currently does sometimes) choose to optimize it statically. Consider the test code:

procedure Example is
   type Table is array(Positive range <>) of Integer;
   Values : constant Table(1..10) := (others => 1);

   -- Final index should be 10 after the Reduce calculates
   Another_Table : Table (1 .. Values'Reduce ("+", 0)) := (1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
   Value : Integer := Another_Table(10) with Volatile;
begin
   null;
end Example;

with compiler switches -O3 -gnat2022 the compiler is able to figure out the last index of that table is indeed 10 at compile time (not run time) and emits:

_ada_example:
        mov     DWORD PTR [rsp-12], 10    # value,
        ret

Without needing to verify that the bounds of the array match the size of the initialization aggregate expression.

And if you change it to

procedure Example is
   type Table is array(Positive range <>) of Integer;
   Values : constant Table(1..10) := (others => 0);

   -- Final index should be 10 after the Reduce calculates
   Another_Table : Table (1 .. Values'Reduce ("+", 0)) := (1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
   Value : Integer := Another_Table(10) with Volatile;
begin
   null;
end Example;

The compiler replaces it with:

.LC0:
        .ascii  "example.adb"
        .zero   1
_ada_example:
        sub     rsp, 8    #,
        mov     esi, 9    #,
        mov     edi, OFFSET FLAT:.LC0     #,
        call    __gnat_rcheck_CE_Length_Check   #

which throws a constraint error since the array is actually a length of 0 with the change

2 Likes
17

You’re right, but™ there is a pitfall here, unfortunately. I tried your example to check whether it can be used to solve @daniel’s original question. The problem we’re facing here is that there are two optimization steps. The behavior you see is coming from the second optimization step but for the task allocator to work statically it needs to be in the first optimization step. If I expand the array declaration from your example I get:

   R13b : constant integer :=                                           
      do                                                                                                                                                                                                                                                                                                                    
         B7b : integer := 0;                                
         L10b : for C11b in 1 .. 10 loop                                       
            E8b : integer renames values (C11b);                               
            B7b := B7b {+} E8b;                                                                                                                                                                                                                                                                                             
         end loop L10b;                                                
      in B7b end                                                                                                                                                                                                                                                                                                            
   ;                                                                           
   subtype example__Tanother_tableS is example__table (1 .. R13b);

compiled with

gcc -c -x ada -gnatA -gnat2022 -O3 -g example.adb

What (I think) happens here is that GCC optimizes the local loop generated by the frontend and hence you can see the static value in the generated binary. The problem is the restriction No_Dynamic_Task_Allocation is checked before that happens. This also isn’t easily solvable because the frontend would need to figure out whether GCC can optimize it out to or not.

So your example works, but only for a different kind of static :sweat_smile:

Note: I’m not sure how much optimization is actually done in the expansion step, but if there is any it’s not sufficient for 'Reduce, at least not at the time.

1 Like