What are the implications of implementing variable-length arrays?

Question

At first C did not have variable-length arrays; all array sizes must be compile times constants. Then, in C99, variable-length arrays, a controversial addition, were added, permitting runtime-sized stack arrays.

int x;
scanf("%d", x);
int vla[x];

The addition had implications such as sizeof() being able to evaluate arguments at runtime. But is this implication avoidable? Why are variable-length arrays such a controversial feature? What are the implications and catches of implementing variable-length arrays, and how do compilers usually get around them or avoid them?

Answer 1

VLAs were added to C99, but made optional in C11. The reason they were made optional doesn't appear to be in public documents.

The initial proposal to add VLA to C (N637) cited numerical computing as the motivation, and the proposal was based on an existing implementation on Cray platforms. In terms of burden on implementers, a similar feature existed on many platforms via the function alloca, which is easy to implement on most platforms where the local variables of a function are on a stack that's a contiguous block of memory (which is the case on almost all platforms). Nonetheless, at least one major C implementation cited VLA as a low-priority feature: in Visual C++, they were one of the last missing C99 features and they will not be added.

I think (but I don't have insider information) that the difficulties with VLA aren't in implementations, but for users. VLAs are bug-prone for many reasons. An obvious one is that they can very easily lead to a stack overflow, which often has disastrous consequences (at best a crash, often memory corruption). Another consequence is that innocuous-looking constructs such as sizeof(...) may now have side effects, and even a simple sizeof(a) doesn't actually return the size of the array a if it's a VLA function parameter (that's true if it's a function parameter as well with a static size, but VLAs make it look more like it should work).

Another reason against having VLA in the C standard is that according to John Nagle on comp.std.c,

Prototypes of functions with VLA parameters do not have to exactly match the function definition. This is incompatible with C++ style linkage and C++ function overloading, preventing the extension of this feature into C++.

C++ is mostly an extension of C; it tweaks some behavior (enough that most idiomatic C programs aren't valid C++) but having a major feature of C that's not in the next edition of C++ is unusual, and is problematic for compilers that handle both languages (which is most C++ compilers).

From personal experience in as a C programmer on embedded platforms, we never use VLAs, even when we're sure that all compilers we care about would support them. They're too bug-prone and they make it impossible to predict your program's stack size (we like to make sure that the deepest nesting of function calls will not overflow the stack — we don't use recursion either). Jens Gustedt on comp.std.c also cites GPUs as a type of platforms where VLAs aren't welcome (I don't know exactly why, but I guess because the memory assigned to each thread's stack tends to be limited).

Answer 2

I'd say one of the reasons is that it was a rather niche feature with a very natural syntax (which you usually try to avoid). Most times I've seen VLAs used in code, it was by novice programmers who didn't care much about how it worked and just preferred it to the more verbose heap allocations. Another common case is people intending to encapsulate the array size in a compile-time variable, but forgetting(/not realizing the need) to mark it as constexpr or at least const. There's little benefit to a feature like this, and it introduces confusion to users and complexity to the language (like, as you've mentioned, having sizeof operate at runtime in some cases). It's a much more fitting solution to provide the alloca function as the API for stack allocations for cases when it is actually needed, and have the programmers handle the resulting variable-length array by pointer, same as in other cases.

As for whether the implications can be avoided, I'd say, possibly, but not in the general case. If, for instance, the base-pointer optimization is enabled (making the local variables be resolved through the stack pointer instead of the base pointer), any VLA significantly slows down the local variable access (as it needs to perform at least one more operation every time). Overall, perhaps some clever tricks could be introduced, but VLAs seem to be of too little use to overcome such difficulties for.

Also worth noting is that a similar concept of variable-sized structs (i.e. having an array extend past the end of a struct) is a widely used idiom in C/C++, despite having almost no specific language support (like no special cases for sizeof nor automatic copying).

TL;DR: alloca does the trick just as well, but is less confusing both for users and language designers

Answer 3

I recall this feature being a GNU extension for a long time before becoming standardized. I suspect it was implemented using alloca() or similar to allocate space on the stack.

This is certainly born out by the Wikipedia page on the subject.

There is a very good quality answer to this question here.

It's easily missed as its asked in the context of C++.

The big danger is the simple and obvious implementation is dangerous. For example:

foo(int n)
{
   int someArrayOnTheStack[n];
   // do stuff
}

You can easily overflow the stack if n is big. In our security conscious world that's a buffer overflow exploit waiting to happen.

You can get around that by allocating on the heap instead but that defies users expectations as it looks like a stack declaration but magically becomes a heap one with no visible call to malloc().

Of course in C++ you'd just write:

foo(int n)
{
   std::vector<int> someArray(n);
   // do stuff
}

Which matches expectations and so the feature is unnecessary there.

The linked Q&A points out some other issues.