ES6 尾递归优化堆栈溢出

IT技术 javascript recursion optimization ecmascript-6 stack-overflow
2021-03-10 04:52:35

阅读Rauschmayer 博士对 es6 中递归尾调用优化的描述后,我一直在尝试重新创建他详细介绍的递归阶乘函数的“零堆栈”执行。

使用 Chrome 调试器在堆栈帧之间步进,我看到尾部优化没有发生,并且正在为每次递归创建一个堆栈帧。

我还尝试通过在没有调试器的情况下调用函数来测试优化,而是传递100000给阶乘函数。这会引发“最大堆栈”错误,这意味着它实际上并未优化。

这是我的代码:

const factorial = (n, acc = 1) => n <= 1 ? acc : factorial(n - 1, n * acc)
console.log( factorial(100000) )

结果:

Uncaught RangeError: Maximum call stack size exceeded
2个回答

V8(Chrome 中的 JavaScript 引擎)支持 TCO 已有一段时间,但截至此更新的答案(2017 年 11 月),它不再支持,在撰写本文时,V8 中的 TCO 没有积极开发,也没有计划。您可以阅读V8 跟踪错误中的详细信息

V8 中的 TCO 支持似乎在某一时刻达到了不错的水平,但由于多种原因(调试问题、错误)仍然落后于标志。但随后发生了几件事,尤其是V8 团队提出了 TCO 的重大问题,并强烈支持称为句法尾调用 (STC)的规范更改,该更改要求有意在源代码中标记尾调用(例如,return continue doThat();)。不过,该提案于 2017 年 7 月失效同样在 7 月,由于没有完成 TCO 工作,V8 团队从 TurboFan* 的源代码中删除了支持 TCO 的代码,否则它会受到 bitrot 的影响。(例如,成为维护的痛苦和错误的来源。)

因此,目前(2017 年 11 月)尚不清楚“隐形”TCO 是否会出现在 V8 中,是否会出现某种 STC,或者什么。Chrome平台状态页此表示的支持TCO“混合”公共来自Mozilla的(火狐/ SpiderMonkey的)和微软(边缘/查克拉)的信号,Safari浏览器与TCO出货,而Web开发人员是“积极的”了解的功能。我们会看看我们从这里往哪里去。如果在任何地方。

*(涡轮风扇=在V8当前尖端JIT编译器,现在他们已经切换从全代码生成[JIT] +曲轴[侵略性优化JIT]至点火[解释+]和涡扇[侵略性优化JIT])

@TJCrowder 你是对的,它可能不会完全陷入困境 - 在这次 WebAssembly 会议上,没有一个在场的团体投票反对进一步考虑(都是中立的或积极的)。感谢您的推动,让我们多看几眼!github.com/WebAssembly/meetings/blob/master/2017/...
2021-04-26 04:52:35
我不知道这个,嗯......所以通常使用 ES6 只是为了进行这种尾调用优化并没有太大的优势,我认为最好在内部运行一个虚拟语言(它优化了尾调用)在编译时或运行时调用)。
2021-04-30 04:52:35
@captain-yossarian - 我没有听说过。据我所知,这仍然处于僵局:JavaScriptCore 实现了它们,V8 和 SpiderMonkey 没有。我认为没有人有兴趣以任何可以解决的方式推动它解决问题(从规范中删除它们,V8 和 SpiderMonkey 按原样实现它们,或用显式语法替换它们 [Apple 2016 年不喜欢])。这说明了当前路径建议所采取的智慧(尾调用早于),其中在有 2 个以上的实现之前,规范中不会出现这些内容。
2021-05-07 04:52:35
不幸的是,Chrome(以及 Internet 的扩展)可能永远不会有适当的尾调用实现。请参阅下面的答案。
2021-05-12 04:52:35
那么对于优化内部语言的尾调用,假设它是 ES3,可以避免创建下一个范围等......你认为这可能吗?
2021-05-13 04:52:35

V8(Chrome 的 JS 引擎)团队暂时没有实施 TCO。它已从最新版本中删除(请参阅此线程)。

在主流浏览器中,只有 Safari 真正实现了该功能

在 Node.JS 版本 8 及更高版本中,TCO 不可用

TCO 实施可能有一些希望:在2017 年的 WebAssembly 会议上,谷歌和所有其他出席的团体对进一步探索 TCO 实施持中立或积极态度。

@ftor:不过,这就是我们所在的地方。“……我们目前没有计划在 V8 中处理尾调用。” .
2021-04-23 04:52:35
@TJCrowder 真的很有趣,我很欣赏讨论!我们在任何地方都继续朝着 FP 迈进,这将是非常好的一步。
2021-05-01 04:52:35
@jamesh625 已更新,谢谢,看起来它已从 repo 中删除,但仍存在于以前的 repo 版本中。
2021-05-03 04:52:35
我更新了帖子以提及 V8 而不是 Chromium,谢谢。但是,我认为所引用的线程非常清楚,除非进一步发展,否则它已死在水中。我很想听听是否有其他信息!就我个人而言,我绝对希望在 JS 中使用此功能。 7 月的 V8 签入删除了所有 TCO 工作说:“尾调用实现......已知在各种情况下都会被破坏,包括 clusterfuzz 安全问题(请参阅示例 Chromium 问题下)。为了避免让实现在主干上进一步变慢,此补丁将其删除。”
2021-05-06 04:52:35
@TJCrowder 感谢您跟进此主题。这真的是一个很大的失望!
2021-05-14 04:52:35