Re: What's wrong with alloca() ?

preston@dawn.cs.rice.edu (Preston Briggs) writes:
>[Support |alloca()|!]


John Levine writes:
>[In some systems it can't be done reliably. It is nice, though.]


|alloca()| is both useful and problematic. There are various
implementations and various alternatives, some of which are discussed
here.




STACK-BASED:


The `normal' implementation of |alloca()| adds space in the current
stack frame. There are a variety of problems, none insurmountable:


  * It requires compiler support.
  * Every routine that has |alloca()| requires both a frame pointer
      and a stack pointer.
  * The compiler has to get right things like


f (alloca(10), alloca(10));


      The naive implementation does something like: allocate 10 bytes,
      push the address, allocate 10 bytes, push the address. The correct
      behavior is allocate 10, allocate 10, push, push.


Fixing these problems is a ``small matter of programming'', that
complicates several things, with the corresponding problem of more bugs.




NON-STACK:


It is also possible to support |alloca()| using arbitrary |malloc()|'d
memory. It is not as efficient as stack allocation but is more
(entirely?) portable and does not require compiler support. The
disadvantages include:


  * Cleanup (freeing) can be delayed long enough that the memory
      demands are huge, as large as all storage ever |alloca()|'d.
  * The performance can be much worse, so programs that rely on
      |alloca()| being fast may run slowly -- by a very large margin --
      when the non-stack |alloca()| is used.


Doug Gwyn wrote the cannonical |alloca()| library implementation. It is a
portable non-stack implementation that he used in order to port some
programs that used |alloca()|. He has stated publicly that he regrets
having released it because it encourages people to continue using
|alloca()|.




OTHER PROBLEMS:


There is one other problem: according to at least once definition of
|alloca()| (there are several, which is a problem of its own), the storage
may be freed as soon as the current set of curly braces is left, or as
late as function exit.


while (expr) {
sto = alloca (n);
use (sto, n);
}


Thus, is the system is allowed to reuse the storage on each iteration, or
to allocate a new space for each iteration?


Deallocation on scope exit is a problem because it becomes nearly
impossible to |alloca()| memory in a useful way, since you can't do


if (expr) {
sto = preallocated();
} else {
sto = alloca (n);
}


On the other hand, defering all deallocation until function exit has the
problem that you can't efficiently allocated space in a loop.




ALTERNATIVES:


A better (or even just one :-) |alloca()| specification would help. In
some cases, it would lead to suboptimal memory use (by delaying freeing
longer than needed). However, at least programmers would know what they
were getting in to and be able to make informed decisions about which
allocator to use.


It might also be useful to define e.g., |al_enter()|, |al_free()|, and
|al_exit()| calls to delimit regions of usage. The semantics would be
like the current |alloca()|, but |al_free()| is allowed to free everything
since the last |al_enter()| scope entry and |al_exit()| exits the scope.
Implicitly, there is an entry at each procedure entry, and a free and exit
at each procedure exit. For the above |while| loop:


al_enter();
while (expr) {
sto = alloca (n);
use (sto, n);
al_free();
}
al_exit();


These calls would help substantially with the performance of the library
(non-stack) implementation.


Sounds great, right? By the time you've added these calls you're just
about all the way to having ``object stack'' allocation, called
``obstacks'' in GNU terminology. An obstack is an allocation region that
can be used for incremental allocation and then freed all at once.


ob = ob_new(); // Create an obstack.
while (x=input()) {
sto = ob_alloc (ob, x.size); // Allocate some memory.
process (sto, x);
add_to_graph (root, sto); // Save for later use.
}
use_graph (root); // Later use.
ob_free (ob); // Free all at once.


Obstacks differ from |alloca()|, at least in conventional usage, in that
you can't free part of an obstack (cheaply). On the other hand, you can
have several obstacks in use at once and free them at different times.


Obstacks are difficult to implement as efficiently as |alloca()|. A
compiler can sometimes reduce an |alloca()| to a single register-register
add. The stack is ``infinite'' so no overflow tests are needed.
Implementing obstacks as efficiently requires mucking with page protection
and signal handlers explicitly. That introduces portability problems.
Similarly, freeing with |alloca()| requires a simple register-register
add. Easily ported implementations of obstacks require data structure
tweaks to free an obstack.




SUMMARY:


|alloca()| is pretty cool, but it has problems. Obstacks can be pretty
efficient, and except for allocations of very small regions, the
performance difference is likely to be dwarfed by the costs of using the
allocated regions. Neither |alloca()| nor obstacks have well-defined
interfaces. If anybody wants to work on standard implementations or
standards descriptions, I volunteer to contribute my two cents :-)




;-D on ( My memory of the situation ) Pardo
--

Return to the comp.compilers page.
Search the comp.compilers archives again.