2

我听说某些语言不支持尾调用优化 (TCO) 的一个原因是,如果/当调试需要查看堆栈跟踪时,这种优化是以混淆调用堆栈为代价的。(我听说过其他原因,例如“虚拟机不支持它”,但我们暂时先不管Java。)

似乎在某些情况下,在某些语言中 TCO 是可能的,但在不执行 TCO 的情况下,堆栈帧的唯一目的是维护元数据,以便生成任何最终的堆栈跟踪。即,堆栈帧可以是最小的,只包含足够的信息来生成堆栈跟踪。

问题:最小化此类堆栈帧的大小是否没有意义?它不会最小化堆栈空间的使用,从而在空间耗尽之前允许更深层次的递归吗?是否在这种思想适用的语言中进行了尝试?(我特别想到了 Python。)或者这对于节省的实际空间来说是一种失​​败的努力?(我想生成漂亮的堆栈跟踪所需的元数据实际上与堆栈帧中的正常数据相比要多得多。)

简而言之:最小化堆栈帧的大小作为 TCO 的替代方案。

PS。我的想法不是基于任何实际的基准。我可能会离开这里。

4

2 回答 2

2

如果正在调试,则不需要打开所有优化,除非您正在调试优化本身。因此,尾递归优化 (TRO) 不必在调试期间禁用回溯,除非开发环境脑残(例如,没有“禁用优化”选项)。

如果您确实记录了元数据,那么它所占用的空间非常小;基本上它说,“进行了递归调用”。具有少量字节元素的链表可以解决问题。但我认为在 TRO 面前记录回溯元数据是没有意义的;如果您正在优化,您可能也不想支付记录元数据的额外时间成本,因为有人可能想稍后进行调试。

我不确定您所说的“最小化堆栈帧的大小”是什么意思,因为您是在 TRO 的上下文中询问的。一般来说,一个好的编译器会自动最小化大小,方法是只分配足够的空间来完成堆栈帧实例所代表的(子)例程的整个计算。一种标准优化是让具有非重叠生命周期的变量在堆栈帧中共享相同的空间。可以通过几种不同的方式做到这一点:a)不重叠的子程序主体内的嵌套范围可以在类似堆栈的规则中轻松共享它们的空间,并且 b)将“堆栈帧”视为一个堆栈,但作为一堆用于存储溢出值的寄存器;寄存器着色算法可以很好地处理这个问题。

有时堆栈帧最小化会因操作系统(缺乏)支持而受损。有关Windows 如何大量捕获损坏堆栈帧大小的讨论,请参阅此内容。

于 2013-09-01T19:07:01.860 回答
1

您基本上可以在“优化”尾递归或维护“准确”调用堆栈之间进行选择。您要么维护某种“面包屑”并且不完全优化尾递归,要么在丢失堆栈跟踪的同时优化尾递归。

每个精心设计的语言实现(对运行时性能和“足迹”完全感兴趣)“最小化”堆栈帧大小。

但是,就像计算中的几乎所有事情一样,竞争因素之间存在权衡——性能、“足迹”、实现的简单性/可靠性、灵活性(例如,多种语言)、可调试性等。

于 2013-09-01T19:29:51.143 回答