Why are stack overflows still a problem?

Question

This question is mystifying me for years and considering this site's name, this is the place to ask.

Why do we, programmers, still have this StackOverflow problem?

Why in every major language does the thread stack memory have to be statically allocated on thread creation?

I will speak in the context of C#/Java, because I use them most, but this is probably a broader problem.

Fixed stack size leads to huge problems:

• There is no way to write a recursive algorithm unless you are absolutely sure that the depth of recursion is tiny. Linear memory complexity of the recursive algorithm is often unacceptable.
• There is no cheap way to start new threads. You have to allocate huge block of memory for stack to account for all the possible uses of the thread.
• Even if you don't use very deep recursion, you always have a risk of running out of stack space for the reason that the stack size is an arbitrary fixed number. Considering that the StackOverflow is usually unrecoverable, this is a big problem in my eyes.

Now, if the stack was resized dynamically, all of the problems above would be much alleviated, because stack overflow would only be possible when there is a memory overflow.

But this is not the case yet. Why? Are there some fundamental limitations of modern CPUs which would make it impossible/inefficient? If you think about the performance hit that reallocations would impose, it should be acceptable because people use structures like ArrayList all the time without suffering much.

So, the question is, am I missing something and the StackOverflow is not a problem, or am I missing something and there are a lot of languages with dynamic stack, or is there some big reason for this being impossible/hard to implement?

Edit: Some people said that performance would be a large problem, but consider this:

• We leave the compiled code untouched. The stack access stays the same, thus the "usual case" performance stays the same.
• We handle CPU exception which happens when the code tries to access the unallocated memory and launch our "reallocation" routine. Reallocations won't be frequent because <put your usual ArrayList argument here>. Should work on most protected-mode CPUs without loss of performance. No?

Answer 1

I've never personally encountered a stack overflow that wasn't caused by infinite recursion. In these cases, a dynamic stack size wouldn't help, it would just take a little longer to run out of memory.

Answer 2

Stacks are resized dynamically - or to be precise, grown dynamically. You get an overflow when a stack cannot grow any further, which is not to say it exhausted the address space, but rather grown to conflict with a portion of memory used to other purposes (e.g., a process heap).

Maybe you mean that stacks cannot be moved dynamically? The root of that is probably that stacks are intimately coupled to the hardware. CPUs have registers and piles of logic dedicated to thread stack management (esp, ebp, call/return/enter/leave instructions on x86). If your language is compiled (or even jitted) you're bound to the hardware mechanism and cannot move stacks around.

This hardware 'limitation' is probably here to stay. Re-basing a thread stack during thread execution seems far from a reasonable demand from a hardware platform (and the added complexity would badly hamper all executed code on such an imaginary CPU, even compiled). One can picture a completely virtualized environment where this limitation does not hold, but since such code couldn't be jitted - it would be unbearably slow. Not a chance you could do anything interactive with it.

Answer 3

Any code that would cause a stack overflow on a typical static-length stack is wrong anyway.

• You could make the stack a std::vector-like object, but you'd have extremely unpredictable performance when it decided to resize -- and anyway, it would most likely just keep doing it until all the heap was exhausted too, and that's more annoying.
• You could make it like a std::list, where it grew at O(1). However, the pointer arithmetic used on a static stack is so totally critical in every way to program performance that it would be uselessly slow. Languages were invented to have one return value and arbitrary numbers of input parameters because that's what fit the static stack/pointer arithmetic paradigm.

So a dynamically resizable stack would be A) a performance nightmare and B) of no value anyway, since your stack shouldn't have gotten that deep.

Answer 4

I think we will see this restriction removed in a few years.

There is simply no fundamental technical reason for fixed size stackes. They exist for historical reasons and because the programmers of compilers and VM's are lazy and don't optimize if it is good enough right now.

But GO the google language already starts with a different approach. It allocates the stack in small 4K pieces. There are also many "stackless" programming language extensions like stackless python etc who are doing the same.

The reason for this is quite simple, the more threads you have the more address space is wasted. For programs which are slower with 64bit pointers it is a serious problem. You can't really have more then hundert threads in practice. This is not good if you write a server which might want to server 60000 clients with a thread for each one (wait for the 100 core/cpu systems in the near future).

On 64bit systems it's not so serious but it still requires more resources. For example TLB entries for pages are extremely serious for good performance. If you can satisfy 4000 normal thread stackes with one single TLB entry (given a page size of 16MB and 4KB active stack space) you can see the difference. Don't waste 1020KB just for stack that you almost never use.

Small grained multithreading will be a very very important technique in the future.

Answer 5

Why do we, programmers, still have this StackOverflow problem?

Stack of fixed size is easy to implement, and is acceptable for 99% of programs. "stack overflow" is a minor problem, that is somewhat rare. So there is no real reason to change things. Also, it is not a language problem, it is more related to platform/processor design, so you'll have to deal with it.

There is no way to write a recursive algorithm unless you are absolutely sure that the depth of recursion is tiny. Linear memory complexity of the recursive algorithm is often unacceptable.

Now this is incorrect. In recursive algorithm you can (almost?) always replace actual recursive call with some kind of container - list, std::vector, stack, array, FIFO queue, etc, that will act like stack. Calculation will "pop" arguments from the end of the container, and push new arguments into either end or beginning of container. Normally, the only limit on size of such container is total amount of RAM.

Here is a crude C++ example:

#include <deque>
#include <iostream>

size_t fac(size_t arg){
    std::deque<size_t> v;
    v.push_back(arg);
    while (v.back() > 2)
        v.push_back(v.back() - 1);
    size_t result = 1;
    for (size_t i = 0; i < v.size(); i++)
        result *= v[i];
    return result;
}

int main(int argc, char** argv){
    int arg = 12;
    std::cout << " fac of " << arg << " is " << fac(arg) << std::endl;
    return 0;
}

Less elegant than recursion, but no stackoverflow problem. Technically, we're "emulating" recursion in this case. You can think that stackoverflow is a hardware limitation you have to deal with.