-2

I am curious to know the necessity of allocating auto variables on Stack memory in C. Please don't say that stack memory is faster. Stack memory generally has less size compared to heap and there is no necessity of implementing stack algorithm for auto variables. Then why are the auto variables stored in stack memory?

manikawnth
  • 2,739
  • 1
  • 25
  • 39
  • 5
    Stack memory **is** faster. There is zero time overhead in allocating something on the stack; allocating on the heap would require an (implicit) call to `malloc` and `free`. – Oliver Charlesworth Jan 01 '14 at 14:30
  • Affinity with the scope is high. – BLUEPIXY Jan 01 '14 at 14:32
  • With heap allocation there is a chance of failure. With a fixed stack size and fixed depth stack allocation and/or usage, stack allocation is guaranteed to succeed – Brandin Jan 01 '14 at 14:32
  • 1
    @Brandin Fixed or even bounded stack usage is hard to prove statically though (and simply impossible for some useful code). And on most systems, it is *much* easier to accidentally overflow the stack than to run out of address space. OOM is almost always coupled to a logic bug or excessively large data sets, whereas stack overflows can easily happen from naively using recursion or creating large arrays on the stack "because it's faster". –  Jan 01 '14 at 14:36
  • 5
    It should also be noted that the C standard doesn't *require* a stack implementation for auto variables. The implementation is free to do whatever it wants. – Oliver Charlesworth Jan 01 '14 at 14:38
  • @delnan There is no need to prove bounded usage statically. With unit tests you can demonstrate a bound on stack usage. With heap allocation there is just no way to guarantee success. – Brandin Jan 01 '14 at 14:56
  • @Brandin Tests can show the presence of a bug, not its absence. For unit tests to give a bound on stack usage, the unit tests need to trigger the worst possible stack space consumption -- how would you know you achieved that? In the presence of recursion, indirect calls, `alloca`, etc. the stack use can depend on the exact input data: A recursive quicksort may need only 20 recursive calls in all your unit tests, but the first real data set may cause pathological behavior with 1k recursive calls, overflowing your conservatively-set stack size. –  Jan 01 '14 at 15:15
  • @delnan For well-known algorithms like quicksort, the maximum recursion has already well-known proofs. There is no possibility to prove anything once we do malloc, failure can always happen depending on what else is happening on the system – Brandin Jan 01 '14 at 16:18
  • @Brandin Quicksort was one example, try finding a ready made proof for an algorithm that doesn't have a Wikipedia article. And a proof of maximum space taken works *regardless* of how that space is allocated (stack, heap, statically). And in all these cases, you only get a bound for `space used when entering this function - maximal space used during execution of this function`, i.e. it's a local property regardless of how space is allocated. To predict *total* space you, you need to take the *whole* system into account in *any* case. –  Jan 01 '14 at 16:32

1 Answers1

3

It's not necessary. Implicitly heap-allocating all automatic variables (and freeing them at the end of their lifetime) would be entirely correct, it's just a rather bad solution. The stack isn't even the best option, registers are even better. But yes, a stack is the way of allocating automatic storage when registers run out. The code for allocating on a stack is much smaller and faster (just bump a pointer, once). Even the fast path of a general heap allocator is several orders of magnitude more expensive.

Even segmented stacks, where the stack model is kept and only augmented with an overflow check and dynamic growth (to avoid overflow), can make function calls measurably slower than C. Rust abandoned segmented stacks because, aside from being very tricky to implement and optimize, they were an obstacle in competing with C for applications like operating system modules.

Note that you can make stacks arbitrarily large. Of course, then it needs more address space and (if you actually use all that memory) more physical memory, but that was kind of the point of the exercise, wasn't it?