Why are stack overflow issues a problem?

Question

This question puzzles me for many years and considers this site name, this is a place to ask about.

Why do we programmers still have this StackOverflow problem?

Why in each main language should the thread stack memory be statically allocated when creating the thread?

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

The fixed stack size leads to huge problems:

• It is impossible to write a recursive algorithm if you are not sure that the recursion depth is tiny. The linear memory complexity of a recursive algorithm is often unacceptable.
• There is no cheap way to start new threads. You must allocate a huge block of memory for the stack to account for all possible uses of the stream.
• 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. Given that StackOverflow usually doesn’t recover, this is a big problem in my eyes.

Now, if the stack was changed dynamically, all of the above problems would be greatly facilitated, since a stack overflow would only be possible with a memory overflow.

But this is not so. What for? Are there some fundamental limitations of modern processors that will make it impossible / inefficient? If you are thinking about the performance that redistributions impose, this should be acceptable, because people use ArrayList structures all the time, without suffering a lot.

So, the question is, am I missing something, and StackOverflow is not a problem, or am I missing something, and there are many languages ​​with a dynamic stack, or is there some big reason for this to be impossible / difficult to implement?

Edit: Some people said that performance would be a big problem, but think about it:

• We leave the compiled code intact. Access to the stack remains the same, so the performance of the "usual case" remains the same.
• We handle the CPU exception that occurs when the code tries to access unallocated memory and starts our “reallocation” procedure. Redistribution will not be frequent because <put your usual ArrayList argument here>. It should work on most processors with protected mode without loss of performance. No?

Answer 1

I am going to generalize the arguments in the answers so far, because I do not find the answer to this question well enough.

Static Stack Investigation

Motivation

Not everyone needs it.

• Most algorithms do not use deep recursion or multiple threads, so many people do not need dynamic stacks.
• A dynamic stack will make the stack overflow with infinite recursion, which is an easy mistake to make, more difficult to diagnose. (memory overflow, being as dangerous as a stack overflow for the current process, is also dangerous for other processes).
• Each recursive algorithm can be emulated with a similar iterative.

difficulties with implementation

The dynamic implementation of the stack is not as simple as it seems.

• Just changing the stack size is not enough if you do not have unlimited address space. Sometimes you also need to move the stack.
• Moving the stack will require updates for all pointers to the data structures allocated on the stack. Although it is simple for data in memory (at least in managed languages), there is no easy way to do the same for data in stream processor registers.
• Some processors (in particular, microcontrollers) implement the stack directly on the hardware, separately from the main memory.

Existing Implementations

There are several languages ​​or runtime libraries that already have a dynamic stack function or something similar to it.

• Some runtime libraries (which?) Do not prefix the entire memory block allocated for the stack. This may alleviate the problem, especially for 64-bit systems, but not completely eliminate it.
• Ira Baxter told us about PARLANSE , a language specifically designed to work with complex data structures with a high degree of parallelism. It uses small heaps of "grains" of work instead of a stack.
• fuzzy lolipop told us that "A correctly written Erlang does not have stackoverflows !"
• It is said that the Google Go programming language has a dynamic stack. (the link will be pleasant)

I would like to see more examples here.

I hope I have not forgotten about any important materials on this issue. Create this community wiki so everyone can add new information.

Answer 2

I have never encountered a stack overflow that was not caused by infinite recursion. In these cases, the dynamic size of the stack would not help, but it would take a little longer to run out of memory.

Answer 3

1) To change the size of the stacks, you must be able to move the memory, which means that pointers to something on the stack may become invalid after changing the size of the stack. Yes, you can use a different level of indirection to solve this problem, but remember that the stack is often used very, very .

2) This greatly complicates the situation. Push / pop operations on stacks usually work simply by doing some pointer arithmetic in the CPU register. This is why stack allocation is faster than free storage allocation.

3) Some processors (in particular, microcontrollers) implement the stack directly on the hardware, separately from the main memory.

In addition, you can set the size of the stack stack when creating a new thread using beginthread() , so if you don't need extra stack space, you can set the stack size accordingly.

From my experience, stack overflows are usually caused by infinite recursions or recursive functions that allocate huge arrays on the stack. According to MSDN, the default stack size specified by the linker is 1 MB (the header of executable files can set its own by default) , which seems to be more than enough for most cases.

The fixed-stack mechanism works quite well for most applications, so there is no need to change it. If this is not the case, you can always expand your own stack.

Answer 4

I can not speak for the "main languages". Many "minor" languages ​​contain heap activation entries, with each call using a piece of heap space instead of a linear piece of the stack. This allows recursion to go as deep as you have address space to host.

Some people here argue that recursion is so deep that using a "large linear stack" is just fine. It is not right. I would agree that if you need to use the entire address space, you are doing some kind of problem. However, when you have very large chart or tree structures, you want to allow deep recursion, and you do not want to guess how much linear stack space you need in the first place, because you make a mistake.

If you decide to go in parallel, and you have a lot (from a thousand to a million "grains" [I think, small threads]), you cannot have 10 MB of stack space allocated for each thread, because you will spend gigabytes of RAM. How could you get a million grains? Easy: many grains that block with each other; when a grain freezes in anticipation of a lock, you cannot get rid of it, and yet you still want to run other grains to use the available CPUs. This maximizes the amount of work available and, thus, allows the efficient use of many physical processors.

The PARLANSE parallel programming language uses this very large number of parallel grain models and heap allocation for function calls. We developed PARLANSE to provide symbolic analysis and conversion of very large source computer programs (say, several million lines of code). They produce ... giant abstract syntax trees, giant control / data flow graphics, giant symbol tables, with tens of millions of nodes. Many opportunities for parallel workers.

Highlighting the heap allows lexically embracing PARLANSE programs even within parallelism, since it is possible to implement a “stack” as a cactus stack, where forks are found in the “stack” for subgrains, and therefore, each seed can see the activation records (parent areas) of its callers . This makes the transfer of large data structures cheap when recursing; you just refer to them lexically.

You might think that heap allocation slows down the program. It does; PARLANSE pays about 5% of the performance penalty, but gets the opportunity to process very large structures in parallel, with as many grains as the address space can take.

Answer 5

Stacks change dynamically - or, to be precise, dynamically grow. You get an overflow when the stack can no longer grow, which does not mean that it has run out of address space, but rather has grown to conflict with a part of the memory used for other purposes (for example, a bunch of processes).

Maybe you mean that stacks cannot be dynamically moved? The root of this probably lies in the fact that stacks are closely related to equipment. Processors have registers and heaps of logic designed to control the flow of the stack (esp, ebp, call / return / enter / leave on x86). If your language is compiled (or even jitter), you are tied to a hardware mechanism and cannot move stacks.

This hardware “limitation” is probably here to stay. Reinstalling the thread stack during the execution of the thread seems far from reasonable demand from the hardware platform (and the added complexity will not interfere well with all the executable code on such an imaginary processor, even compiled). You can imagine a fully virtualized environment where this restriction is not met, but since such code cannot be skewed, it will be unbearably slow. It is no coincidence that you could do something interactive with it.

Answer 6

Why do we programmers still have a problem with StackOverflow?

The fixed-size stack is easy to implement and acceptable for 99% of programs. "stack overflow" is a small issue that is somewhat rare. Therefore, there is no reason to change things. Also, this is not a language issue, it is more related to the platform / processor design, so you have to deal with it.

It is impossible to write a recursive algorithm if you are not sure that the recursion depth is tiny. The complexity of a recursive linear memory algorithm is often unacceptable.

Now this is not true. In a recursive algorithm, you can (almost?) Always replace the actual recursive call with some sort of list container, std :: vector, stack, array, FIFO queue, etc., which will act as a stack. The calculation will “call” arguments from the end of the container and call new arguments to the end or beginning of the container. Usually, the only size limitation for such a container is the total amount of RAM.

Here is a 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 not stackoverflow issue. Technically, we "emulate" recursion in this case. You may think that stackoverflow is a hardware limitation that you have to deal with.

Answer 7

I think we will see that this restriction is removed after a few years.

There is simply no fundamental technical reason for fixed-size stacks. They exist for historical reasons and because the programmers of compilers and virtual machines are lazy and not optimized if they are good enough now.

But GO google-language already begins with a different approach. It highlights the stack in small 4K parts. There are also many "levelless" extensions to the programming language, such as free python, etc. that do the same.

The reason for this is quite simple, the more threads you have, the more address space is lost. For programs that are slower with 64-bit pointers, this is a serious problem. In practice, you cannot have more hundert themes. This is bad if you are writing a server that might want a server of 60,000 clients with a stream for each of them (wait for 100-core systems in the near future).

On 64-bit systems, this is 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 4,000 regular stream stacks with one single TLB record (given a page size of 16 MB and 4 KB of active stack space), you can see the difference. Do not spend 1020KB only on a stack that you almost never use.

Small granular multithreading will be a very important method in the future.

Answer 8

Almost infinite stack space will be very bad in case of infinite recursion, because it will turn an easily diagnosed error (stack overflow) into a much more problematic error (from memory). With a stack overflow, a look at the stack trace pretty quickly tells you what is going on. Otherwise, when the system goes out of memory, it may try to use other methods to solve it, for example, use swap space, which leads to serious performance degradation.

On the other hand, I rarely had problems removing the barrier due to recursion. However, I can come up with a couple of circumstances where this happened. However, switching to my own stack, implemented as std :: vector, was a simple solution to the problem.

Now, what would be neat if the language allowed me to mark a certain function as "highly recursive", and then make it work in its own stack space. That way, I usually get the advantage of stopping when my recursion fails, but I could still use extensive recursion whenever I wanted.

Answer 9

Why in each main language should the thread stack memory be statically allocated when creating the thread?

The size and distribution of the stack is not necessarily related to the language you use. It is rather a matter of processor and architecture.

Stack segments are limited to 4 GB on modern Intel processors.

This next link is a good read that may give you some of the answers you are looking for.

http://www.intel.com/Assets/PDF/manual/253665.pdf - Chapter 6.2

Answer 10

Old languages ​​have a static stack size, so most of the newer popular languages ​​(which just copied the old languages ​​and broke / fixed everything that they felt) have the same problem.

There is no logical reason to have a static stack size if you are not using formal methods. Why introduce errors where the code is correct? For example, Erlang does not do this because it handles errors, like any normal partial programming language.

Answer 11

Any code that causes a stack overflow on a typical stack of static length is erroneous in any case.

• You can make the stack a std :: vector-like object, but you would have extremely unpredictable performance when it decided to resize - and in any case, it will most likely just continue to do this until the whole heap has been exhausted, and it is more annoying.
• You can do it like std :: list, where it grew by O (1). However, the pointer arithmetic used in the static stack is so critical in all respects that program performance will be useless. Languages ​​were invented to have one return value and an arbitrary number of input parameters, because this corresponds to the static arithmetic paradigm of the stack / pointer.

Thus, dynamically resizing will be A) a performance nightmare, and B) will by no means make any difference, since your stack should not have been so deep.