为什么堆栈溢出仍然是一个问题? [英] Why are stack overflows still a problem?

问题描述

这个问题使我困惑了很多年，考虑到该站点的名称，这是一个可以询问的地方.

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

为什么我们程序员仍然有这个StackOverflow问题?

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?

我将在C#/Java的背景下发言，因为我使用它们最多，但这可能是一个更广泛的问题.

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:

• 除非您完全确定递归的深度很小，否则无法编写递归算法.递归算法的线性内存复杂度通常是不可接受的.
• 没有廉价的方法来启动新线程.您必须为堆栈分配大量内存，以解决线程的所有可能使用.
• 即使您不使用非常深的递归，由于堆栈大小是一个任意的固定数字，也总是有耗尽堆栈空间的风险.考虑到StackOverflow通常是不可恢复的，在我看来这是一个大问题.

现在，如果动态调整堆栈大小，上述所有问题都将得到缓解，因为只有在内存溢出时才可能发生堆栈溢出.

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.

但这不是事实.为什么?现代CPU是否存在一些基本限制，这些限制将使其不可能/效率低下?如果考虑重新分配会带来的性能损失，那应该是可以接受的，因为人们一直使用ArrayList这样的结构而不会遭受太大的痛苦.

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.

所以，问题是，我是否缺少某些内容，而 StackOverflow 没问题，还是我缺少某些内容，并且动态堆栈有很多语言，还是有一些大的原因?因为这不可能/很难实现?

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?

修改: 有人说性能会是个大问题，但请考虑以下问题:

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

• 我们保持编译后的代码不变.堆栈访问保持不变，因此通常情况"下的性能保持不变.
• 我们处理CPU异常，该异常在代码尝试访问未分配的内存并启动重新分配"例程时发生.重新分配不会很频繁，因为<在此放置您通常的ArrayList参数>.应该可以在大多数保护模式的CPU上工作，而不会损失性能.不是吗?

推荐答案

到目前为止，我将总结答案中的论点，因为我找不到涵盖该主题的足够好的答案.

I am going to summarize the arguments in the answers so far because I find no answer covering this topic good enough.

并不是每个人都需要它.

Not everyone needs it.

• 大多数算法不使用深度递归或大量线程，因此没有很多人需要动态堆栈.
动态堆栈会导致无限递归堆栈溢出，这是一个容易犯的错误，难以诊断. (内存溢出与当前进程的堆栈溢出一样致命，对其他进程也很危险)
• 每个递归算法都可以使用类似的迭代算法进行仿真.

• Most algorithms do not use deep recursion or a lot of threads, thus not a lot of people need dynamic stacks.
• Dynamic stack would make an infinite-recursion stack overflow, which is an easy mistake to make, harder to diagnose. (memory overflow, while being as deadly as a stack overflow to the current process, is hazardous for other processess as well)
• Every recursive algorithm can be emulated with a similar iterative one.

动态堆栈的实现并不像看起来那样简单.

Dynamic stack implementation turns out to be not as straightforward as it seems.

• 仅堆栈大小调整是不够的，除非您有无限的地址空间.有时您也需要重新定位堆栈.
• 堆栈重定位将要求更新指向分配在堆栈上的数据结构的所有指针.尽管内存中的数据很简单(至少使用托管语言)，但没有简单的方法可以对线程的CPU寄存器中的数据进行同样的操作.
• 某些CPU(特别是微控制器)直接在与主存储器分开的硬件上实现堆栈.

有些语言或运行时库已经具有动态堆栈功能或类似的功能.

There are some languages or runtime libraries that already have the dynamic stack feature or something similar to it.

• 某些运行时库(哪个?)未预先提交分配给堆栈的整个内存块.这可以缓解该问题，特别是对于64位系统，但不能完全消除它.
• 伊拉克·巴克斯特 PARLANSE ，一种专为处理具有高度并行性的复杂数据结构而设计的语言.它使用小的堆分配的工作"而不是堆栈.
• fuzzy lolipop 告诉我们，正确编写的Erlang
• 据说Google Go编程语言具有动态堆栈. (链接会很好)

• Some runtime libraries (which?) do not pre-commit the entire block of memory allocated for stack. This can alleviate the problem, expecially for 64-bit systems, but not completely eliminate it.
• Ira Baxter told us about PARLANSE, a language specifically designed for dealing with complex data structures with high degree of parallelism. It uses small heap-allocated "grains" of work instead of stack.
• fuzzy lolipop told us that "Properly written Erlang doesn't have stackoverflows!"
• Google Go programming language is said to have a dynamic stack. (a link would be nice)

我想在这里看到更多示例.

I would like to see more examples here.

我希望我不会忘记有关此主题的任何重要信息.将其设置为社区Wiki，以便任何人都可以添加新信息.

I hope I didn't forget any important pieces of information on this subject. Making this a community wiki so that anyone can add new information.

这篇关于为什么堆栈溢出仍然是一个问题?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！