为什么堆栈溢出仍然是一个问题？
这个问题多年来让我感到迷惑，考虑到这个网站的名字，这是要问的地方。
为什么我们程序员仍然有这个StackOverflow问题？
为什么在每一种主要语言中，线程堆栈的内存都必须在创build线程时静态分配？
我将在C＃/ Java的背景下讲，因为我使用它们最多，但这可能是一个更广泛的问题。
固定的堆栈大小会导致巨大的问题：
- 除非你确定recursion的深度很小，否则没有办法写一个recursionalgorithm。 recursionalgorithm的线性内存复杂度通常是不可接受的。
- 没有便宜的方法来开始新的线程。 你必须为堆栈分配巨大的内存块来说明线程的所有可能的用途。
- 即使不使用非常深的recursion，由于堆栈大小是一个任意的固定数字，您总会有堆栈空间不足的风险。 考虑到StackOverflow通常是不可恢复的，这是我眼中的一个大问题。
现在，如果dynamic调整堆栈大小，上述所有问题都将得到缓解，因为堆栈溢出只有在存在内存溢出时才可能发生。
但事实并非如此。 为什么？ 现代CPU有没有一些基本的限制，会使它变得不可能/效率低下？ 如果你考虑重新分配会带来的性能问题，那么应该是可以接受的，因为人们ArrayList使用像ArrayList这样的结构而不会受到太大的影响。
所以，问题是，我错过了什么， StackOverflow是不是一个问题，或者我错过了一些东西，有很多语言与dynamic堆栈，还是有一些很大的原因，这是不可能的/难以实现？
编辑：有人说，performance将是一个大问题，但考虑到这一点：
- 我们保持编译的代码不变。 堆栈访问保持不变，因此“通常情况下”的性能保持不变。
- 我们处理当代码尝试访问未分配的内存并启动我们的“重新分配”例程时发生的CPUexception。 重新分配将不会经常发生，因为<将您通常的ArrayList参数放在这里>。 应该在大多数保护模式CPU上工作而不会损失性能。 没有？
我从来没有亲自遇到过不是由无限recursion造成的堆栈溢出。 在这些情况下，dynamic堆栈大小将无济于事，只会花费更长的时间来耗尽内存。
1）为了调整堆栈大小，你必须能够移动内存，这意味着在堆栈大小调整之后，指向堆栈上的任何东西的指针可能会失效。 是的，你可以使用另一个间接的层次来解决这个问题，但要记住，堆栈的使用非常频繁。
2）它使事情变得更加复杂。 堆栈上的push / pop操作通常只需在CPU寄存器上进行一些指针运算即可。 这就是为什么在堆栈上分配比在免费店铺分配更快的原因。
3）一些CPU（特别是微控制器）直接在硬件上实现堆栈，与主存储器分开。
另外， 在使用beginthread()创build新线程时 ， 可以设置线程堆栈的大小 ，因此，如果发现多余的堆栈空间是不必要的，则可以相应地设置堆栈大小。
根据我的经验，堆栈溢出通常是由在堆栈上分配巨大数组的无限recursion或recursion函数引起的。 根据MSDN的说法，链接器设置的默认堆栈大小为1MB（可执行文件的头文件可以设置自己的默认值） ，对于大多数情况来说，这似乎已经足够大了。
固定堆栈机制对大多数应用程序来说已经足够了，所以没有必要去改变它。 如果没有，你总是可以推出自己的堆栈。
我不能说“主要语言”。 许多“小”语言都会分配堆激活logging，每个调用使用一堆堆空间而不是线性堆栈块。 这使得recursion可以尽可能深地分配空间。
这里的一些人声称深度recursion是错误的，而使用“大线性堆栈”就好了。 那是不对的。 我同意，如果你必须使用整个地址空间，你会遇到某种问题。 但是，如果有一个非常大的graphics或树结构，则希望允许深度recursion，并且不要猜测首先需要多less线性堆栈空间，因为您会猜错。
如果你决定走并行，而且你有很多（千万到几百万的“谷物”[想想，小线程]），你不能有10Mb的堆栈空间分配给每个线程，因为你会浪费千兆字节的RAM。 你怎么可能有一百万粒？ 容易：大量的粮食互相联锁; 当谷物被冻结等待locking，你不能摆脱它，但你仍然想运行其他谷物使用你的可用CPU。 这可以使可用工作量最大化，从而可以有效地使用许多物理处理器。
PARLANSE并行编程语言使用这种非常大数量的并行粒度模型，并且在函数调用上使用堆分配。 我们devise了PARLANSE，可以对非常大的源计算机程序（比如数百万行代码）进行符号分析和转换。 这些产生巨大的抽象语法树，巨大的控制/数据stream图，巨型符号表，有数千万个节点。 平行工作者有很多机会。
堆分配允许PARLANSE程序在词汇范围上，即使在并行性边界上，因为可以将“堆栈”实现为仙人掌堆栈，其中在子堆栈的“堆栈”中出现叉，每个粒子因此可以看到激活logging父范围）的调用者。 这使得在recursion时传递大数据结构便宜; 你只是在词汇上引用它们。
有人可能会认为堆分配会减慢程序的速度。 它确实; PARLANSE支付约5％的性能损失，但能够并行处理非常大的结构，并且可以容纳的地址空间数量与谷仓一样多。
dynamic调整堆栈大小 – 或者准确地说，dynamic增长堆栈大小。 当堆栈无法进一步增长时，会发生溢出，这并不是说它耗尽了地址空间，而是增长到与用于其他目的的内存部分（例如，进程堆）冲突。
也许你的意思是堆栈不能dynamic移动 ？ 其根源可能在于堆栈与硬件密切相关。 CPU具有专用于线程堆栈pipe理的专用寄存器和堆栈（尤其是在x86上的ebp，call / return / enter / leave指令）。 如果你的语言被编译（甚至是疯狂），你就会被绑定到硬件机制上，不能移动堆栈。
这个硬件的“限制”可能在这里停留。 在线程执行期间重新构build线程堆栈似乎远没有硬件平台的合理要求（并且增加的复杂性会严重妨碍在这样的虚拟CPU上执行的所有代码，甚至编译）。 人们可以描绘出一个完全虚拟化的环境，但这个限制并不成立，但是由于这样的代码不可能被搞砸，所以它的速度会慢得令人难以忍受。 没有一个机会，你可以做任何事情互动。
我现在要总结一下答案中的论点，因为我没有find涵盖这个主题的答案。
静态堆栈调查
动机
不是每个人都需要它。
- 大多数algorithm不使用深度recursion或大量的线程，因此不是很多人需要dynamic堆栈。
- dynamic堆栈会造成无限recursion堆栈溢出，这是一个容易犯的错误，难以诊断。 （内存溢出，虽然像当前进程的堆栈溢出一样致命，但对其他进程也是危险的）
- 每个recursionalgorithm都可以用一个类似的迭代来仿真。
执行困难
dynamic堆栈实现结果并不像看起来那么简单。
- 除非你拥有无限的地址空间，否则单独调整堆栈是不够的。 您有时也需要重新定位堆栈。
- 堆栈重定位需要更新所有指向堆栈上分配的数据结构的指针。 虽然对于内存中的数据来说（至less在托pipe语言中）是直截了当的，但是对于线程的CPU寄存器中的数据也没有简单的方法。
- 一些CPU（特别是微控制器）直接在硬件上实现堆栈，与主内存分开。
现有的实现
有一些语言或运行时库已经具有dynamic堆栈function或类似的东西。
- 一些运行时库（哪些？）不预先提交为堆栈分配的整个内存块。 这可以缓解这个问题，特别是对于64位系统，但是不能完全消除这个问题。
- Ira Baxter 向我们介绍了PARLANSE ，这是一种专门用于处理高度并行性的复杂数据结构的语言。 它使用小堆分配“工作”而不是堆栈。
- 模糊的lolipop告诉我们，“正确的书面Erlang 没有stackoverflows ！”
- 据说Google Go编程语言有一个dynamic堆栈。 （一个链接会很好）
我想在这里看到更多的例子。
我希望我没有忘记关于这个主题的任何重要信息。 使这个社区维基，这样任何人都可以添加新的信息。
为什么我们程序员仍然有这个StackOverflow问题？
固定大小的堆栈很容易实现，对于99％的程序是可以接受的。 “堆栈溢出”是一个小问题，这是有点罕见的。 所以没有真正的理由来改变事情。 而且，这不是一个语言问题，它更多地涉及平台/处理器devise，所以你必须处理它。
除非你确定recursion的深度很小，否则没有办法写一个recursionalgorithm。 recursionalgorithm的线性内存复杂度通常是不可接受的。
现在这是不正确的。 在recursionalgorithm中，您可以（几乎？）总是用实际的recursion调用replace某种types的容器列表，std :: vector， stack ，array，FIFO队列等，这将起到堆栈的作用。 计算将从容器的末端“popup”参数，并将新的参数推入容器的末端或开始处。 通常，这种容器的大小的唯一限制是RAM的总量。
这是一个粗略的C ++示例：
#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; }
不如recursion优雅，但没有stackoverflow的问题。 从技术上讲，我们在这种情况下“模拟”recursion。 你可以认为，stackoverflow是你必须处理的硬件限制。
我想我们会在几年后看到这个限制。
固定大小的堆栈根本没有根本的技术原因。 它们的存在是出于历史的原因，因为编译器和虚拟机的程序员是懒惰的，如果现在足够好，就不会优化。
但谷歌语言已经开始了不同的方法。 它分配在小4K块的堆栈。 还有很多“无堆栈”的编程语言扩展，如堆栈python等，他们也是这样做的。
原因很简单，就是你拥有更多地址空间的线程被浪费了。 对于使用64位指针的程序来说，这是一个严重的问题。 在实践中你不可能真的有更多的线索。 如果你编写的服务器可能需要为每个服务器提供一个线程（在不久的将来等待100个核心/ CPU系统），这是不好的。
在64位系统上，它并不那么严重，但仍然需要更多的资源。 例如，页面的TLB条目对于良好的性能来说是非常严重的。 如果只有一个TLB条目可以满足4000个正常的线程堆栈（给定的页面大小为16MB和4KB的活动堆栈空间），则可以看到差异。 不要为了堆栈而浪费1020KB，几乎从不使用。
小粒度的multithreading将是非常重要的技术。
实际上无限的堆栈空间在无限recursion的情况下会非常糟糕，因为它会将一个容易诊断的错误（堆栈溢出）变成一个更有问题的错误（内存不足）。 堆栈溢出时，看一下堆栈跟踪会很快地告诉你发生了什么。 或者，当系统内存不足时，可能会尝试其他解决方法，例如使用交换空间，导致严重的性能下降。
另一方面，由于recursion，我很less碰到堆栈溢出障碍的问题。 但是，我可以想到发生的情况。 但是，移动到我自己的堆栈实现为一个std ::向量是一个简单的解决scheme的问题。
现在，如果语言允许我将一个特定的函数标记为“重度recursion”，然后让它在自己的栈空间中运行，那将是一件好事。 这样，当我的recursion失败时，我通常会得到停止的优势，但是当我想要的时候，仍然可以使用广泛的recursion。
为什么在每一种主要语言中，线程堆栈的内存都必须在创build线程时静态分配？
堆栈大小和分配不一定与您正在使用的语言有关。 这更多的是处理器和架构的问题。
当前的英特尔处理器上的堆栈段数限制为4GB。
这下面的链接是一个很好的阅读，这可能会给你一些你寻求的答案。
Assets/PDF/manual/253665.html – 第6.2章
旧的语言实现具有静态堆栈大小，因此大多数新的stream行语言（只是复制旧的语言，并打破/固定任何他们感觉）具有相同的问题。
有一个静态堆栈大小是没有合理的理由，除非你在一个正式的方法设置。 为什么在代码正确的地方引入错误？ 例如Erlang不会这样做，因为它处理错误，就像任何理智的部分编程语言一样。
无论如何，任何会导致典型静态长度堆栈溢出的代码都是错误的。
- 你可以把堆栈变成一个std :: vectortypes的对象，但是当它决定resize时，你的性能会非常不可预测 – 无论如何，它最有可能会一直持续下去，直到所有的堆都耗尽为止。更烦人。
- 你可以使它像一个std :: list，它生长在O（1）。 然而，在静态堆栈上使用的指针algorithm在编程性能的各个方面是非常关键的，因为它将会无用的慢。 语言被发明具有一个返回值和任意数量的input参数，因为这符合静态堆栈/指针algorithm范例。
所以一个dynamicresize的堆栈将是A）性能噩梦和B）无价值，因为你的堆栈不应该得到那么深。
