为什么堆栈溢出仍然存在问题？

Question

多年来这个问题让我很困惑,考虑到这个网站的名字,这是值得一提的地方.

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

为什么在每个主要语言中线程堆栈内存都必须在创建线程时静态分配？

我将在C#/ Java的上下文中发言,因为我最常使用它们,但这可能是一个更广泛的问题.

固定堆栈大小会导致巨大的问题:

• 除非你绝对确定递归的深度很小,否则无法编写递归算法.递归算法的线性存储器复杂性通常是不可接受的.
• 没有廉价的方法来启动新线程.您必须为堆栈分配大量内存来考虑线程的所有可能用途.
• 即使您不使用非常深的递归,由于堆栈大小是任意固定数,您总是有可能耗尽堆栈空间.考虑到StackOverflow通常是不可恢复的,这是我眼中的一个大问题.

现在,如果堆栈动态调整大小,上面的所有问题都会大大减轻,因为堆栈溢出只有在存在内存溢出时才有可能.

但事实并非如此.为什么？现代CPU有一些基本限制会使其变得不可能/效率低下吗？如果你考虑重新分配所带来的性能ArrayList损失,它应该是可以接受的,因为人们一直使用结构而不会遭受太多痛苦.

所以,问题是,我错过了什么,StackOverflow不是问题,或者我错过了什么,有很多语言有动态堆栈,还是有一些很大的原因让这个不可能/难以实现？

编辑: 有人说性能会是个大问题,但请考虑一下:

• 我们保持编译后的代码不变.堆栈访问保持不变,因此"通常情况"性能保持不变.
• 我们处理CPU异常,当代码试图访问未分配的内存并启动我们的"重新分配"例程时会发生这种异常.重新分配不会频繁,因为<将您通常的ArrayList参数放在此处>.应该在大多数保护模式CPU上工作而不会降低性能.没有？

Answer 1

我从来没有遇到过不是由无限递归引起的堆栈溢出.在这些情况下,动态堆栈大小无济于事,只需要更长的时间就会耗尽内存.

Answer 2

1)为了调整堆栈大小,你必须能够移动内存,这意味着堆栈调整大小后堆栈上任何东西的指针都会变得无效.是的,您可以使用另一级别的间接来解决此问题,但请记住,堆栈的使用非常非常频繁.

2)它使事情变得更加复杂.堆栈上的推/弹操作通常只需在CPU寄存器上执行一些指针算法即可.这就是为什么堆栈上的分配比免费存储上的分配更快的原因.

3)某些CPU(特别是微控制器)直接在硬件上实现堆栈,与主存储器分开.

此外,您可以在使用创建新线程时设置线程堆栈的大小beginthread(),因此如果您发现不需要额外的堆栈空间,则可以相应地设置堆栈大小.

根据我的经验,堆栈溢出通常是由无限递归或在堆栈上分配大型数组的递归函数引起的.根据MSDN,链接器设置的默认堆栈大小为1MB(可执行文件的标头可以设置它们自己的默认值),这对于大多数情况来说似乎足够大.

固定堆栈机制适用于大多数应用程序,因此没有必要对其进行更改.如果没有,您可以随时推出自己的堆栈.

Answer 3

我不能代表"主要语言".许多"次要"语言执行堆分配的激活记录,每次调用使用一堆堆空间而不是线性堆栈块.这允许递归与您要分配的地址空间一样深.

这里的一些人声称深度错误的递归,并且使用"大线性堆栈"就好了.那是不对的.我同意,如果你必须使用整个地址空间,你会遇到某种问题.但是,当一个人有非常大的图形或树结构时,你想要允许深度递归,你不想先猜测你需要多少线性堆栈空间,因为你会猜错.

如果你决定并行,并且你有很多(千万到几百万个"粒子"[想想,小线程])你不能为每个线程分配10Mb的堆栈空间,因为你将浪费千兆字节的RAM.你怎么会有一百万粒？容易:大量的谷物彼此互锁; 当谷物被冻结等待锁定时,你无法摆脱它,但你仍然想要运行其他谷物来使用你的可用CPU.这最大化了可用工作量,因此可以有效地使用许多物理处理器.

该PARLANSE并行编程语言使用上的函数调用这个超大型数的平行的颗粒模型,堆分配.我们设计了PARLANSE来实现非常大的源计算机程序(例如,数百万行代码)的符号分析和转换.这些产生了......巨大的抽象语法树,巨型控制/数据流图,巨型符号表,拥有数千万个节点.并行工人有很多机会.

堆分配允许PARLANSE程序在词法范围内,甚至跨越并行边界,因为可以将"堆栈"实现为仙人掌堆栈,其中叉子出现在子堆的"堆栈"中,并且每个粒子因此可以看到激活记录(其呼叫者的父范围).这使得在递归时传递大数据结构变得便宜; 你只是在词汇上引用它们.

有人可能认为堆分配会降低程序的速度.它确实; PARLANSE在性能上损失了大约5%的损失,但却能够并行处理非常大的结构,并且地址空间可以容纳多少颗粒.

Answer 4

叠层被动态地调整大小-或更准确地说,动态地生长.当堆栈无法进一步增长时,您会遇到溢出,这并不是说它耗尽了地址空间,而是变得与用于其他目的的一部分内存冲突(例如,进程堆).

也许你的意思是堆栈不能动态移动？其根源可能是堆栈与硬件紧密耦合.CPU具有专用于线程堆栈管理的寄存器和成堆逻辑(尤其是ebp,x86上的调用/返回/进入/离开指令).如果您的语言被编译(甚至是jitted),那么您将被绑定到硬件机制并且无法移动堆栈.

这种硬件"限制"可能会留下来.在线程执行期间重新创建线程堆栈似乎远非硬件平台的合理需求(并且增加的复杂性将严重妨碍在这样的虚拟CPU上执行的所有代码,甚至编译).人们可以想象一个完全虚拟化的环境,这种限制并不成立,但由于这样的代码无法进行攻击 - 这将是无法忍受的缓慢.你不可能做任何与之互动的事情.

Answer 5

我将总结到目前为止答案中的论点，因为我发现没有足够好的答案涵盖这个主题。

静态堆栈调查

动机

不是每个人都需要它。

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

实施困难

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

• 除非您有无限的地址空间，否则仅调整堆栈大小是不够的。有时您还需要重新定位堆栈。
• 堆栈重定位需要更新指向堆栈上分配的数据结构的所有指针。虽然对于内存中的数据来说很简单（至少在托管语言中），但对于线程的 CPU 寄存器中的数据却没有简单的方法。
• 一些CPU（特别是微控制器）直接在硬件上实现堆栈，与主存储器分开。

现有实施

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

• 某些运行时库（哪个？）不会预先提交分配给堆栈的整个内存块。这可以缓解该问题，特别是对于 64 位系统，但并不能完全消除它。
• Ira Baxter 向我们介绍了PARLANSE，这是一种专门为处理具有高度并行性的复杂数据结构而设计的语言。它使用小堆分配的工作“颗粒”而不是堆栈。
• fuzzy lolipop告诉我们“正确编写的 Erlang不会有 stackoverflows！”
• 据说 Google Go 编程语言有一个动态堆栈。（有链接就好了）

我想在这里看到更多例子。

我希望我没有忘记关于这个主题的任何重要信息。使其成为社区维基，以便任何人都可以添加新信息。