How do compilers treat variable length arrays

Question

This might seem like a beginner's question, but I am interested in the way that a compiler normally creates arrays of variable-dimensions, like in the following program.

#include<iostream>

int main(){
  int n;
  std::cin>>n;
  int a[n];
}

From what I've learnt, in C all the initializer values must be constant, so that the compiler knows how much memory to reserve inside the function, normally by subtracting the stack pointer in order to accomodate the number of elements the array holds.

This makes sense to me. However, I don't quite understand how compilers treat the above program, since it seems to work with G++(MinGW) , but fails with Cl, Microsoft's C++ compiler. I suspect that GCC allocates memory on the heap trough a non-standard extension, but I am not sure of this.

Also, Microsoft's compiler is not renowned for being standards-compliant, so I wouldn't be surprised if it may actually be wrong in the way it treats the above program.

possible duplicate of [How does GCC implement variable-length arrays?](http://stackoverflow.com/questions/21182307/how-does-gcc-implement-variable-length-arrays) — phuclv, Nov 18 '14 at 14:06
http://stackoverflow.com/questions/19131712/declare-an-array-with-a-variable?lq=1 — phuclv, Nov 18 '14 at 14:07

bdonlan · Accepted Answer · 2011-10-02T15:33:10.903

12

In the C99 version of the C standard, variable length arrays are permitted. However, they are not permitted in any version of C++; you're seeing a G++ extension. Note that Microsoft's C compiler does not fully support C99; since G++ supports C99 it's easy enough to apply the VLA support to C++ as an extension.

As to how the compiler usually implements VLAs, it's the same as alloca() (except that it has to keep the size around for sizeof) - the compiler saves the original stack pointer, then adjusts it down by however many bytes it calculates that it needs. The downside is function entry and exit is a bit more complicated as the compiler needs to store where to reset the stack pointer to rather than just adjusting by fixed constants.

edited Oct 02 '11 at 15:33

answered Oct 02 '11 at 15:27

bdonlan

224,562
31
268
324

1

Strangely, Visual Studio supports it in C mode at least, but issues a warning because it's not C89. :) – onemasse Oct 02 '11 at 15:29
1

I think there are other downsides, if my memory of disassemblies is right, it also introduces overhead for references to stack variables, as they are usually computed with a delta from the current stack pointer. Without VLA, the delta is fixed, but with VLA it depends on the size of the array (for references after the array), and thus induces overhead as a computation is required. – Matthieu M. Oct 02 '11 at 17:51
@MatthieuM., more likely it'll just use an extra register to point to the top of the stack frame – bdonlan Oct 02 '11 at 17:53
1

@bdonlan: I guess it depends on the register pressure (esp. on x86 32bits...). Thanks for pointing it out, I had not registered that if it were often used it would probably be kept on the side. – Matthieu M. Oct 02 '11 at 17:56
@MatthieuM., Yeah, what it boils down to is you're forced to keep the frame pointer around, which can lead to a small (but significant on x86) increase in register pressure. – bdonlan Oct 02 '11 at 19:04

score 5 · Answer 2 · answered Oct 02 '11 at 15:37

There's absolutely no problem with "subtracting the stack pointer" at run-time, by a run-time value. And that is how the compilers normally implement variable-length arrays. They "subtract the stack pointer" at run-time, when the actual array size is already known. That's all there is to it. (There's no need to allocate memory on heap and I don't know what made you suspect this in GCC.).

Such functionality was available long before VLAs became part of the language. The [non-standard] function alloca does exactly that. The only difference is that the memory allocated by alloca is automatically deallocated when the function exits, while the local VLAs must obey standard block-based lifetime rules. The latter is not a problem at all, since block nest in a stack-like fashion.

In other words, for a run-time value n the declaration

int a[n];

is essentially translated into something like

int *a = alloca(n * sizeof *a);

plus some extra household data to support the functionality of sizeof etc (and, of course, automatic restoration of the original stack pointer value at the end of the enclosing block).

+1 for `alloca(n * sizeof *a)` instead of `alloca(n * sizeof int)` — Nawaz, Oct 02 '11 at 15:43
In C++ with all its fancy type deduction mechanics, you have a problem, though: what's the type of `a` when it's declared as `int a[n]`? This doesn't fit elegantly into the rest of the language, which is presumably why it isn't included in the standard. — Kerrek SB, Oct 02 '11 at 15:48

score 3 · Answer 3 · answered Oct 02 '11 at 15:26

3

No version of C++ allows variable length array. Only C99 allows it.

GCC allows it as an extension.

answered Oct 02 '11 at 15:26

Nawaz

353,942
115
666
851

score 2 · Answer 4 · answered Oct 02 '11 at 15:27

int main(){
  int n;
  std::cin>>n;
  int a[n];
}

This is not legal C++. G++ accepts Variable Length Array's as an extension but VLAs are not part of the C++ standard. They are part of the C99 standard which GCC supports(I am not sure to what extent) but MSVC doesn't.

How do compilers treat variable length arrays

4 Answers4

Linked

Related