Praxeolitic Praxeolitic - 2 months ago 7
C Question

Fixed size array vs alloca (or VLAs)

When is

alloca()
preferable to memory allocated on the stack by declaring a fixed size array?




Details:

As we know,
alloca()
is a controversial function. Used recklessly, it can cause stack overflow. Used judiciously, it can shave a few nanoseconds from a tight loop by avoiding heap allocation. In this question about why
alloca
is considered bad, several of the top answers advocate for the occasional use of
alloca
.

Another way to allocate from the stack is to simply declare a fixed size array. An example of this strategy can be found in the
arena
class in Howard Hinnant's stack allocator. (That code is of course C++ but the concept is still applicable to C.)

What are the tradeoffs of using
alloca
vs a fixed size array? When, if ever, is one clearly preferable to the other? Is it simply a question of performance that should be empirically tested in each individual situation (when performance is a key goal and a hotspot has already been identified)? The fixed size array is more pessimistic -- it always allocates as much as we're willing to allocate on the stack -- but it's not clear whether this is good or bad.

Just to be as clear as possible, here's a very simple example of two function implementations where it seems reason to use either
alloca
or a fixed size array:

#include <alloca.h>
#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

void foo_alloca(const size_t mem_needed) {
printf("foo_alloca(%zu)\n", mem_needed);
char* mem;
bool used_malloc = false;
if (mem_needed <= 100)
mem = alloca(mem_needed);
else {
mem = malloc(mem_needed);
used_malloc = true;
}
assert(mem_needed != 0);
// imagine we do something interesting with mem here
mem[0] = 'a';
mem[1] = 'b';
mem[2] = 'c';
mem[3] = '\0';
puts(mem);
if (used_malloc)
free(mem);
}

void foo_fixed(const size_t mem_needed) {
printf("foo_fixed(%zu)\n", mem_needed);
char* mem;
char stack_mem[100];
bool used_malloc = false;
if (mem_needed <= 100)
mem = stack_mem;
else {
mem = malloc(mem_needed);
used_malloc = true;
}
assert(mem_needed != 0);
// imagine we do something interesting with mem here
mem[0] = 'a';
mem[1] = 'b';
mem[2] = 'c';
mem[3] = '\0';
puts(mem);
if (used_malloc)
free(mem);
}

int main()
{
foo_alloca(30);
foo_fixed(30);
foo_alloca(120);
foo_fixed(120);
}


Another option very similar to
alloca
is VLAs. As far as I know, memory obtained from
alloca
and VLAs have essentially the same behavior so the question applies to VLAs as well. If that understanding is wrong just mention it.

Answer

What are the trade-offs of using alloca() vs a fixed size array?

  1. Portability. alloca() is not a standard C library function. Fixed size arrays are part of the language.

  2. Analyzability. Tools that analyze code memory usage regularly support stack depth analysis via fixed side arrays. alloc() analyzability may/may not exist.

  3. Space efficiency. alloca() allocates the proscribed memory space. Fixed size arrays tend to over allocate.

  4. Code efficiency/speed is certainly an implementation issue and profiling would be needed to compare performance. A significant difference is not expected.

  5. VLA pros/cons is like alloca() except that is is part of the C99 standard, yet only optional in C11.