Static Allocation - C language

Question

As far as I know, the C compiler (I am using GCC 6) will scan the code in order to:

1. Finding syntax issues;
2. Allocating memory to the program (Static allocation concept);

So why does this code work?

int main(){
    int integers_amount; // each int has 4 bytes
  
    printf("How many intergers do you wanna store? \n");
    scanf("%d", &integers_amount);

    int array[integers_amount];
    printf("Size of array: %d\n", sizeof(array)); // Should be 4 times integer_amount
    
    for(int i = 0; i < integers_amount; i++){
        int integer;
        printf("Type the integer: \n");
        scanf("%d", &integer);
        array[i] = integer;
    }
    
    for(int j = 0; j < integers_amount; j++){
        printf("Integer typed: %d \n", array[j]);
    }
    

    return 0;
}

My point is:

How does the C compiler infer the size of the array during compilation time?

I mean, it was declared but its value has not been informed just yet (Compilation time). I really believed that the compiler allocated the needed amount of memory (in bytes) at compilation time - That is the concept of static allocation matter of fact.

From what I could see, the allocation for the variable 'array' is done during runtime, only after the user has informed the 'size' of the array. Is that correct?

I thought that dynamic allocation was used to use the needed memory only (let's say that I declare an integer array of size 10 because I don't know how many values the user will need to hold there, but I ended up only using 7, so I have a waste of 12 bytes).

If during runtime I have those bytes informed I can allocate only the memory needed. However, it doesn't seem to be the case because from the code we can see that the array is only allocated during runtime.

Can I have some help understanding that?

Thanks in advance.

Answer 1

How does the C compiler infer the size of the array during compilation time?

It's what's called a variable length array or for short a VLA, the size is determined at runtime but it's a one off, you cannot resize anymore. Some compilers even warn you about the usage of such arrays, as they are stored in the stack, which has a very limited size, it can potencially cause a stackoverflow.

---

From what I could see, the allocation for the variable 'array' is done during runtime, only after the user has informed the 'size' of the array. Is that correct?

Yes, that is correct. That's why these can be dangerous, the compiler won't know what is the size of the array at compile time, so if it's too large there is nothing it can do to avoid problems. For that reason C++ forbids VLA's.

---

let's say that I declare an integer array of size 10 because I don't know how many values the user will need to hold there, but I ended up only using 7, so I have a waste of 12 bytes

Contrary to fixed size arrays, a variable length array size can be determined at runtime, but when its size is defined you can no longer change it, for that you have dynamic memory allocation (discussed ahead) if you are really set on having the exact size needed, and not one byte more.

Anyway, if you are expecting an outside value to set the size of the array, odds are that it is the size you need, if not, well there is nothing you can do, aside from the mentioned dynamic memory allocation, in any case it's better to have a little more wasted space than too little space.

---

Can I have some help understanding that?

There are three concepts I find relevant to the discussion:

1. Fixed size arrays, i.e. int array[10]:

   Their size defined at compile time, they cannot be resized and are useful if you already know the size they should have.

2. Variable length arrays, i.e. int array[size], size being a non constant variable:

   Their size is defined at runtime, but can only be set once, they are useful if the size of the array is dependant on external values, e.g. a user input or some value retrived from a file.

3. Dynamically allocated arrays: i.e. int *array = malloc(sizeof *arr * size), size may or may not be a constant:

   These are used when your array will need to be resized, or if it's too large to store in the stack, which has limited size. You can change its size at any point in your code using realloc, which may simply resize the array or, as @Peter reminded, may simply allocate a new array and copy the contents of the old one over.

Answer 2

Variables defined inside functions, like array in your snippet (main is a function like any other!), have "automatic" storage duration; typically, this translates to them being on the "stack", a universal concept for a first in/last out storage which gets built and unbuilt as functions are entered and exited.

The "stack" simply is an address which keeps track of the current edge of unused storage available for local variables of a function. The compiler emits code for moving it "forward" when a function is entered in order to accommodate the memory needs of local variables and to move it "backward" when the program flow leaves the function (the double quotes are there because the stack may as well grow towards smaller addresses).

Typically these stack adjustments upon entering into and returning from functions are computed at compile time; after all, the local variables are all visible in the program code. But principally, nothing keeps a program from changing the stack pointer "on the fly". Very early on, Unixes made use of this and provided a function which dynamically allocates space on the stack, called alloca(). The FreeBSD man page says: "The alloca() function appeared in Version 32V AT&T UNIX"´(which was released in 1979).

alloca behaves very much like alloc except that the storage is lost when the current function returns, and that it underlies the usual stack size restrictions.

So the first part of the answer is that your array does not have static storage duration. The memory where local variables will reside is not known at compile time (for example, a function with local variables in it may or may not be called at all, depending on run-time user input!). If it were, your astonishment would be entirely justified.

The second part of the answer is that array is a variable length array, a fairly new feature of the C programming language which was only added in 1999. It declares an object on the stack whose size is not known until run time (leading to the anti-paradigmatic consequence that sizeof(array) is not a compile time constant!).

One could argue that variable length arrays are only syntactic sugar around an alloca call; but alloca is, although widely available, not part of any standard.