Allocate Array on the Stack with Length Determined at Run-Time

[alyfarahat]

One of the things I was surprised to know from today's lecture is that it is allowed to allocate an array on the stack with length determined at run-time. For example,

void foo(int length)
{
    int arr[length];
    populate_range(arr, length);
    return;
}

Now what would be a use-case where dynamic allocation is the only way to go? Is it a situation where we need dynamic-length arrays that are persistent across multiple threads of execution, for example?

[mvelegar]

Statically allocated arrays are destroyed when the function exits, i.e. anything allocated on the stack is basically gone when the function exits. So it you want to create an array and return it to the calling function, it has to be on the heap (dynamically allocated). Does that help?

[mvelegar]

Also, multiple threads doesn’t enter into this issue. Multiple threads can happily work off statically allocated arrays (as long as the function that “owns” the array is the one spawning the threads and does not exit until all the threads are done). So it all boils down to “do you want to use the array after the function exits?” If yes, it has to be dynamically allocated. Else, it can be statically allocated.

[alyfarahat]

You can still statically allocate an array of variable length at the caller and populate it by reference as in the example we had in the lecture and the example code I have in this thread. I am saying that because dynamic allocation requires that we keep track of memory and free variables by hand; unlike static allocation of variable length. So would it be a good practice to "try to avoid" dynamic allocation as much as possible?

[mvelegar]

I am not sure I understand your first paragraph in reference to your initial question, perhaps @cswiercz can clarify that. You can statically or dynamically allocate an array of variable length and populate it, one use case for choosing dynamic allocation is if you have a calling function that does not "own" this array but needs to use it (like I said before). The example code you have has static allocation for arr, but any function calling foo will not have access to arr (unless you change definition of foo and make it return arr). The answer to your next question: would it be a good practice to "try to avoid" dynamic allocation as much as possible? is YES.

[cswiercz]

@alyfarahat I think some of the confusion comes from something I misspoke about when it comes to how the program determines how much stack memory to allocate. As a demonstration, I just created a minimal working example of dynamic stack allocation here: stacks_on_stacks.c.

I wrote a function to double an input vector in a very silly way: dynamically allocate a stack array, store the input vector in this stack array, double it, and then store the result back in the input (/output) vector:

void double_array(int* arr, int length)
{
  int temp[length]; // dynamic stack allocation. disappears after func call
  int i;

  // copy contents of arr to temp
  for (i=0; i<length; ++i)
    temp[i] = arr[i];

  // double
  for (i=0; i<length; ++i)
    temp[i] *= 2;

  // copy contents back
  for (i=0; i<length; ++i)
    arr[i] = temp[i];

  // `temp` (and `i`) pops off the stack
}

When main() calls double_array() enough stack space for the double_array() stack frame is allocated for an array of ints of length length and the index variable i. The moment double_array() exits the stack pointer is moved back down to main().

Using stack memory for temps like could, in some applications, be useful for performance purposes.

I did a lot of C programming back in the C89 standard. Since then, even as early as the C99 standard, "variable length arrays" have become legal and are useful for efficient temporary storage. See this Stackoverflow discussion.

[cswiercz]

One moral of the story: there is a difference between "static" and "dynamic" arrays as well as "stack" and "heap" arrays. Here is a shoddy table.

	static	dynamic
stack	int a[5];	int a[length];
heap	int* a = malloc(5*sizeof(int));	int* a = malloc(length*sizeof(int));

[mvelegar]

Thanks @cswiercz for that table. I was thinking after my last reply that the confusion was between dynamic memory allocation (heap) arrays and allocating arrays of variable length.

[cswiercz]

No problem. It took me more time to figure out how to display a table than to write up my first response.

[alyfarahat]

@cswiercz and @mvelegar , thank you so much for making this clear. I am actually glad I learned about the stack-dynamic (Table[1, 2]) arrays. It turns out that many people in industry (at least where I work) are unaware of it, as I used to be. This is a very valuable piece of information.

[cswiercz]

To be honest, I was also unaware of its legality until a few months ago.

[alyfarahat]

One reason we could have missed the run-time sized array feature for such a long time is that the feature was not supported in C++, including C++11. The first release of C++ where run-time sized arrays are supported is C++14, gcc 4.9 is the first version of gcc to support C++14 features. Here is a link for further details. http://blog.smartbear.com/development/a-glimpse-into-c14/