为什么堆栈溢出仍然是一个问题?

这个问题多年来让我感到神秘,考虑到这个网站的名字,这是要问的地方。

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

为什么在每种主要语言中,线程堆栈内存都必须在创建线程时进行静态分配?

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

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

  • 除非您确定递归的深度很小,否则无法编写递归算法。 递归算法的线性内存复杂度通常是不可接受的。
  • 没有便宜的方法来开始新的线程。 您必须为堆栈分配巨大的内存块来说明线程的所有可能用途。
  • 即使你不使用非常深的递归,由于堆栈大小是一个任意的固定数字,你总会有堆栈空间不足的风险。 考虑到StackOverflow通常是不可恢复的,这在我眼中是一个大问题。
  • 现在,如果动态调整堆栈大小,上述所有问题都将得到缓解,因为堆栈溢出只有在存在内存溢出时才可能发生。

    但事实并非如此。 为什么? 现代CPU有一些基本限制会使它变得不可能/效率低下吗? 如果你考虑重新分配会带来的性能问题,那么它应该是可以接受的,因为人们ArrayList使用像ArrayList这样的结构而不会受到太大的影响。

    所以,问题是,我错过了什么,并且StackOverflow不是问题,还是我错过了一些东西,并且有很多使用动态堆栈的语言,还是有一些很大的原因使得这不可能/难以实现?

    编辑:有人说,表现将是一个大问题,但考虑到这一点:

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

  • 我从来没有亲自遇到过不是由无限递归造成的堆栈溢出。 在这些情况下,动态堆栈大小无济于事,只会花费更长的时间来耗尽内存。


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

    2)它使事情变得更加复杂。 通常通过在CPU寄存器上执行一些指针运算来对堆栈上的push / pop操作进行操作。 这就是为什么在堆栈上分配比在免费店分配更快的原因。

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

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

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

    固定堆栈机制对于大多数应用程序来说工作得很好,所以没有必要去改变它。 如果没有,你可以随时推出自己的堆栈。


    我不能说“主要语言”。 许多“小”语言都会分配堆激活记录,每次调用都使用一堆堆空间而不是线性堆栈块。 这可以使递归尽可能深地分配空间。

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

    如果你决定走并行,并且你有很多(千万到百万的“谷物”[思考,小线程]),你不能有10Mb的堆栈空间分配给每个线程,因为你会浪费千兆字节的RAM。 你究竟能有一百万粒? 容易:大量互相联锁的谷物; 当谷物被冻结等待锁定时,您无法摆脱它,但您仍想运行其他谷物来使用可用的CPU。 这可以最大限度地提高可用工作量,从而可以有效地使用许多物理处理器。

    PARLANSE并行编程语言使用这种非常大数量的并行颗粒模型,并在函数调用中使用堆分配。 我们设计了PARLANSE,可以对非常大型的源计算机程序(比如数百万行代码)进行符号分析和转换。 这些产生巨大的抽象语法树,巨大的控制/数据流图,巨型符号表,数千万个节点。 平行工作者有很多机会。

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

    有人可能会认为堆分配会减慢程序的速度。 它确实; PARLANSE支付约5%的性能损失,但可以并行处理非常大的结构,并且可以容纳尽可能多的谷物。

    链接地址: http://www.djcxy.com/p/80269.html

    上一篇: Why are stack overflows still a problem?

    下一篇: Is an entire process’s virtual address space split into pages