Why cannot a dynamically sized array be allocated on stack?

Question

In C, we all learned that:

int i[500]; // Array of 500 integers on stack
int *i = malloc(sizeof(int) * 500); // Array of 500 integers on heap

Stack size grows and shrinks as functions push and pop variables from it. But why cannot a dynamically size array be pushed and popped from stack?

Answer 1

Yes they can:

http://gcc.gnu.org/onlinedocs/gcc/Variable-Length.html

Variable-length automatic arrays are allowed in ISO C99, and as an extension GCC accepts them in C90 mode and in C++. These arrays are declared like any other automatic arrays, but with a length that is not a constant expression. The storage is allocated at the point of declaration and deallocated when the block scope containing the declaration exits. For example:

 FILE *
 concat_fopen (char *s1, char *s2, char *mode)
 {
   char str[strlen (s1) + strlen (s2) + 1];
   strcpy (str, s1);
   strcat (str, s2);
   return fopen (str, mode);
 }

Simple test:

$ cat testarray.c 
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char** argv) {
  size_t n = atol(argv[1]), i;
  printf("array size: %lu\n", n);

  int a[n];

  for (i=0; i<n; ++i) {
    a[i] = i;
  }

  printf("%d\n", a[0]);

  return 0;
}

$ ./a.out 100000
array size: 100000
0
$ ./a.out 1000000
array size: 1000000
0
$ ./a.out 10000000
array size: 10000000
Segmentation fault
$ ./a.out 100000000
array size: 100000000
Segmentation fault

Answer 2

If array's length will not change since first allocation, then it can be allocated on stack, even when it's size is not known at time of compilation. C99 supports this under the name variable length arrays. Previous versions of the language could simulate the same with non-standard alloca function.

However, the term “dynamically sized array” usually assumes that array can grow later again and again, indefinitely until there's still memory available, and such thing is not truly possible on stack, because the stack space after the array may be already taken by another function call.