Allocation of local variables on stack

[Ingo Rohloff <ingo.rohloff@xxxxxxxxxxxxxx>]

Hello,

I am trying out the following program:

---------------------------------%<-----------------------
#include <stdio.h>

static char *stackA;
static char *stackB;

static void saveStackPtr(char **ptr)
{
    int b;
    *ptr=(char *)(&b);
}

static void calc(int c,int *array)
{
    int result;
    if (c<=0) {
        // base case c<=0:
        saveStackPtr(&stackB);
        if (array==NULL) {
            printf("a[0] == 1\n");
        } else {
            array[0]=1;
        }
        return;
    }

    // here: c>0
    if (array==NULL) {
        // no array allocated, so allocate it now
        int i;
        int a[2500];

        // calculate array entries recursively
        calc(c-1,a);

        // calculate current array entry a[c]
        a[c]=a[c-1]+3;

        // print full array
        for(i=0;i<=c;i++) {
            printf("a[%d] = %d\n",i,a[i]);
        }
    } else {
        // array already allocated
        calc(c-1,array);

        // calculate current array entry a[c]
        array[c]=array[c-1]+3;
    }
}

int main()
{
    saveStackPtr(&stackA);
    calc(9,NULL);
    printf("stackA = %p\n",stackA);
    printf("stackB = %p\n",stackB);
    printf("used stack = %d\n",(int)(stackA-stackB));
}
---------------------------------%<-----------------------


The function "calc" calculates n*3+1 for all 0<=n<=c in a recursive fashion.

If you look at the code for "calc", you will notice that
the array "a[2500]" is only declared, when the parameter
"array" to the function is NULL.

Now this only happens in the call to "calc", which is done in "main".

The stackA and stackB pointers are used to calculate a rough estimate,
how much stack is used by this program.

Now:
"int a[2500];" should consume around 10_000 bytes (4 bytes per integer, 2500 entries).
So you could expect that the whole program consumes around
10_000 bytes of stack + something additional
(for overhead when "calc" is called recursively).

But: It turns out this program consumes around 100_000 bytes of stack
(10 times as much as expected).
The reason is, that for each call of "calc" the array "int a[2500];" is allocated,
even if it is only used in the first call.
There are 10 calls to "calc" (0<=c<=9) and so you
consume 100_000 bytes of stack (+ something extra for overhead).

I am wondering what the technical reason is for this behavior.

I am currently guessing that "setjmp/longjmp" might be to blame.
Reasoning: When googling for "Variable Length Array longjmp" you get
hints that variable length arrays might not mix well with longjmp.

And: "Variable Length Arrays" do behave differently. If I use
"int a[c+1]" in the above program, I get a different behavior
(array is only allocated when corresponding "if" block is executed).

So is there any technical explanation why the allocation of "int a[2500];"
is done at function entry at not at declaration ?

with best regards
  Ingo Rohloff

Attachment: smime.p7s
Description: S/MIME Cryptographic Signature