alloca(), #if, and other controversial things...

[Steven Ryan]

>(1) Heaps are in fact almost always slower than "alloca" -- and they are
>    almost always more versatile and only rarely do I need to allocate
>    enough items that the speed difference is important.  And then, the
>    speed I gain using fixed (static or automatic) arrays beats alloca
>    all round the block.

I frequently write procedures for a fixed graph. Putting all the nodes
in a random addressable array instead of linked list frequently reduces the
time complexity by a factor of n. I can't use fixed size arrays because I
do not know the size of graph ahead of time. I know how to use malloc
to allocate space on the heap but the results are ugly, require explicit
free, and intrinsically slower.

Some of us write programs other people use and time and space not trivial
concerns.

>(2) Any alloca implementation that creates an base+offset reference to
>    the dynamic stack allocation (for more than 1 alloca call, that is)
>    appears to me to be no more efficient than the equivalent registered
>    pointer variable (and just as hard to optimize).

No, it is easier to optimise if it is known that a pointer is constrained
to a specific region [of the local stack]. This has to do with aliassing
and ref/defs.
 
>(3) As far as ignoring the task of freeing memory -- I would not do this
>    even were I using alloca -- this ties the structure of the problem
>    code to a detail of the computer architecture (as has been mentioned
>    several times before) and the detail is very much tied to traditional
>    CISC architecture (that is a single big general purpose stack that is

I don't understand: the concept of a single big general purpose stack is
fundamental to any language that implements recursion. The automatic release
of locally generated space is semantically identical to the automatic release
of local variable.

Now if you're saying it's a problem trying to graft in local allocation into
a compiler which does provide the appropriate interfaces, undoubtably right.
I don't think it should be a graft. Aw, but if it were part of the language.

All hope is not lost: many implementors have added dynamic arrays to Fortran.