ES6 尾递归优化堆栈溢出
ES6 Tail Recursion Optimisation Stack Overflow
阅读 Dr Rauschmayer's description es6 中的递归尾部调用优化后,我一直在尝试重新创建 'zero-stack' 他详述的递归阶乘函数的执行。
使用 Chrome 调试器在堆栈帧之间步进,我看到尾部优化没有发生,并且正在为每个递归创建堆栈帧。
我还尝试通过在没有调试器的情况下调用函数来测试优化,而是将 100000
传递给阶乘函数。这会抛出一个 'maximum stack' 错误,这意味着它实际上没有经过优化。
这是我的代码:
const factorial = (n, acc = 1) => n <= 1 ? acc : factorial(n - 1, n * acc)
console.log( factorial(100000) )
结果:
Uncaught RangeError: Maximum call stack size exceeded
V8,Chrome 中的 JavaScript 引擎,有一段时间有 TCO 支持,但截至这个更新的答案(2017 年 11 月)它不再支持,并且在撰写本文时,有V8 中的 TCO 没有积极开发,并且计划 none。您可以在 the V8 tracking bug for it.
中阅读详细信息
TCO 支持似乎在 V8 中一度达到了不错的水平,但由于多种原因(调试问题、错误)仍然落后于一个标志。但随后发生了几件事,尤其是 2017 年 7 月的 the V8 team raised significant issues with TCO and strongly supported a spec change called syntactic tail calls (STCs) that would require that tail calls be flagged in source code intentionally (e.g., return continue doThat();
). That proposal became inactive。同样在 7 月,在没有完成 TCO 工作的情况下,V8 团队从 TurboFan* 的源代码中删除了支持 TCO 的代码,否则它会受到 bitrot 的影响。 (例如,成为维护难题和错误来源。)
所以目前(2017 年 11 月)尚不清楚 "invisible" TCO 是否会出现在 V8 中,是否会出现某种 STC,或者什么。 Chrome Platform Status page 表示来自 Mozilla (Firefox/SpiderMonkey) 和 Microsoft (Edge/Chakra) 的 "mixed" public 信号支持 TCO,Safari 附带 TCO,并且Web 开发人员 "positive" 关注该功能。我们将看看我们从这里去哪里。如果有的话。
*(TurboFan = V8 中当前最先进的 JIT 编译器,现在他们 switched 从 Full-Codegen [JIT] + Crankshaft [积极优化 JIT] 到 Ignition [interpreter+] 和 TurboFan [积极优化 JIT])
V8(Chrome 的 JS 引擎)团队暂时没有实施 TCO。它已从最新版本 (see this thread) 中删除。
在主要浏览器中,only Safari has actually implemented the feature (described in this 2016 Webkit blog post)。
在 Node.JS 版本 8 及更高版本中,TCO is not available。
实施 TCO 可能有一些希望:在 2017 WebAssembly meeting 中,Google 和所有其他在场的团体对进一步探索 TCO 实施持中立或积极态度。
阅读 Dr Rauschmayer's description es6 中的递归尾部调用优化后,我一直在尝试重新创建 'zero-stack' 他详述的递归阶乘函数的执行。
使用 Chrome 调试器在堆栈帧之间步进,我看到尾部优化没有发生,并且正在为每个递归创建堆栈帧。
我还尝试通过在没有调试器的情况下调用函数来测试优化,而是将 100000
传递给阶乘函数。这会抛出一个 'maximum stack' 错误,这意味着它实际上没有经过优化。
这是我的代码:
const factorial = (n, acc = 1) => n <= 1 ? acc : factorial(n - 1, n * acc)
console.log( factorial(100000) )
结果:
Uncaught RangeError: Maximum call stack size exceeded
V8,Chrome 中的 JavaScript 引擎,有一段时间有 TCO 支持,但截至这个更新的答案(2017 年 11 月)它不再支持,并且在撰写本文时,有V8 中的 TCO 没有积极开发,并且计划 none。您可以在 the V8 tracking bug for it.
中阅读详细信息TCO 支持似乎在 V8 中一度达到了不错的水平,但由于多种原因(调试问题、错误)仍然落后于一个标志。但随后发生了几件事,尤其是 2017 年 7 月的 the V8 team raised significant issues with TCO and strongly supported a spec change called syntactic tail calls (STCs) that would require that tail calls be flagged in source code intentionally (e.g., return continue doThat();
). That proposal became inactive。同样在 7 月,在没有完成 TCO 工作的情况下,V8 团队从 TurboFan* 的源代码中删除了支持 TCO 的代码,否则它会受到 bitrot 的影响。 (例如,成为维护难题和错误来源。)
所以目前(2017 年 11 月)尚不清楚 "invisible" TCO 是否会出现在 V8 中,是否会出现某种 STC,或者什么。 Chrome Platform Status page 表示来自 Mozilla (Firefox/SpiderMonkey) 和 Microsoft (Edge/Chakra) 的 "mixed" public 信号支持 TCO,Safari 附带 TCO,并且Web 开发人员 "positive" 关注该功能。我们将看看我们从这里去哪里。如果有的话。
*(TurboFan = V8 中当前最先进的 JIT 编译器,现在他们 switched 从 Full-Codegen [JIT] + Crankshaft [积极优化 JIT] 到 Ignition [interpreter+] 和 TurboFan [积极优化 JIT])
V8(Chrome 的 JS 引擎)团队暂时没有实施 TCO。它已从最新版本 (see this thread) 中删除。
在主要浏览器中,only Safari has actually implemented the feature (described in this 2016 Webkit blog post)。
在 Node.JS 版本 8 及更高版本中,TCO is not available。
实施 TCO 可能有一些希望:在 2017 WebAssembly meeting 中,Google 和所有其他在场的团体对进一步探索 TCO 实施持中立或积极态度。