You are here

Little Programming Advice

Ulrich Drepper - Thu, 25/05/2006 - 7:42am
This won't apply to too many people since unfortunately not many people realize the advantages of using stack-based allocation vs malloc-based allocation. In addition, many people still don't know about the new features in C99 (or old features of gcc).

Specifically, this is about variable length arrays and their interaction with alloca(). A VLA is simply an array allocated in a function block which does not have a fixed length. Just as for fixed length arrays, VLAs are guaranteed to not accumulate if the block is executed more than once. This is in contrast to using alloca(). See these two examples:

for (i = 0; i < n; ++i) {
  char arr[i+1];         // <-  VLA
  memset(arr, i, i+1);
  somefct(arr, i);
}


and

for (i = 0; i < n; ++i) {
  char *arr = (char *) alloca (i+1);
  memset(arr, i, i+1);
  somefct(arr, i);
}


In case of the VLA, the space needed for the arrayarr is recycled after every around. The maximum amount of memory needed for the arrays in all rounds together is n. This is in contrast to the second example where alloca() is used. Memory allocated this way remains usable until the function containing the alloca() call is left. This means the total memory use for all loop iterations together is n*(n+1)/2. But this is not what this all is about. I just wanted to point out the difference.

The tricky part is when one writes optimized code using both of these techniques together. I recently had a piece of code where I inadvertently mixed the two. The code went something like this:

{
  char arr[strlen(s)];
  fill_in(arr, s);
  s = strdupa(arr);
}


The strdupa() function is actually a macro which works like strdup() but uses alloca() instead of malloc(). What is the compiler supposed to do with such a piece of code? On the one hand, the memory for arr should be freed when the block is left. This happens by adjusting the stack pointer by the inverse amount used in the allocation. But on the other hand alloca() has been used to allocate a new string and that string doesn't go away until the function is left. This is an unsolvable conflict.

It is usually easy enough to avoid this situation. Just move the VLA definition further out, or use alloca() as well (in case the accumulated memory isn't that much), or use malloc(). But the real kicker is that gcc doesn't warn about this and silently creates invalid code. This makes for some funk programs and lots of fun while debugging unless you happen to know about this kind of problem.

The gcc tried to fix the problem by issuing warnings but the same patch caused false positives as well. So frequently that at least the gcc in RHEL/Fedora does not issue the warning at all.

It is still worthwhile using VLAs and alloca(). Just be careful when mixing them.