It has been a long time since I have programmed in basic compilers with basic arrays, but recently I saw an array declaration like this:
int y;
cin>>y;
int z[y];
old time compilers used to give error "Storage size of array isn't constant". Then I found out about variable size arrays in C99. I wonder how they work internally. Does that makes array dynamic? Is this memory allocated at heap? Does this binding is still done statically? If so how.
Variable Length Array(VLA)s are a C99 feature but several compilers including gcc supports VLA as an extension outside of C99 and both gcc and clang support variable length arrays in C++ as an extension even though this is really a C99 feature.
In both gcc and clang building using the -pedantic flag will produce a warning similar to the following in C:
warning: variable length arrays are a C99 feature [-Wvla-extension]
and something similar to this in C++:
warning: ISO C++ forbids variable length array ‘z’ [-Wvla]
The usual implementation will allocate VLA on the stack since they will treat them just like other automatic variables which although the standard does not refer to the stack or heap are usually allocated on the stack in most cases.
We can also see from the C99 draft standard that VLAs are just another variation of an array declaration from section 6.7.5.2 Array declarators paragraph 4 says (emphasis mine):
If the size is not present, the array type is an incomplete type. If the size is * instead of being an expression, the array type is a variable length array type of unspecified size, which can only be used in declarations with function prototype scope;124) such arrays are nonetheless complete types. If the size is an integer constant expression and the element type has a known constant size, the array type is not a variable length array type; otherwise, the array type is a variable length array type.
we see from paragraph 5 that it's size does not change during it's lifetime:
[...]The size of each instance of a variable length array type does not change during its lifetime.[...]
Although a major difference with VLAs and other variables is that sizeof is evaluated for VLAs while otherwise it computed at compile time, from section 6.5.3.4 The sizeof operator paragraph 2:
[...]If the type of the operand is a variable length array type, the operand is evaluated; otherwise, the operand is not evaluated and the result is an integer constant.
Does that makes array dynamic?
It depends how you define "dynamic". VLA certainly cannot grow or shrink or, in other words, change its size once it is created. It is dynamic, though, in a sense that its length is not known in compile-time.
Is this memory allocated at heap?
How the memory is allocated for the VLA is implementation specific. Generally speaking, the memory for the VLA is allocated from space in the stack frame of the caller. It is then automatically freed when the function where VLA is defined returns to its caller, or if VLA goes out of scope.
The closest relative of VLA is alloca() function, which pretty much can be considered to have the same effect, at least in C. Assuming that compiler implements the VLA the same way alloca() is implemented, you can think of these two arrays as being technically the same in C:
int *a = alloca(sizeof(int) * N);
int b[N];
The VLA has, however, more compact and convenient syntax. But most importantly, VLA by nature has an automatic storage duration and gives compiler more freedom to decide whether to destroy/free the array upon leaving the scope where it was declared, or upon returning from the function.
This becomes very important in languages such as C++ where compiler implements RAII idiom and must guarantee to destroy objects with automatic storage duration upon exiting their scope.
Note, however, that VLA is not currently a part of C++ language and is implemented by compiler as a non-standard extension. But they are expected to become standard in C++14.
Short answer: it reserves space on the stack, by incrementing the stack pointer.
