JavaScript运行时Bun中的算法优化

现在，您可以选择在浏览器之外运行 JavaScript 的三种选择：Node、Deno 和 Bun。

Bun是一个 JavaScript 运行时，刚刚发布了 1.0 版本！

Bun的卖点之一就是速度！为了实现这一目标，它做出了一些有趣的决定。

其一，Bun 是使用Zig进行编程的。这导致了一个令人兴奋的宇宙：

• Node 由C++制成，
• Deno 由Rust制成，
• Bun 由Zig制成。

核心不同：

• Node 和 Deno 是基于 V8 构建的， V8 是 Chrome 的 JavaScript 引擎。
• 而 Bun 是基于 JavaScriptCore 构建的。JavaScriptCore 是 Safari 的引擎。

它们有很多有趣的差异，但我们将重点关注 JavaScriptCore 实现而 V8 没有的：尾部调用优化。

尾部调用优化
让我们通过编写一些真正的代码来深入研究！想象一下您需要实现以下功能：

*
  返回从 1 到金额的数字数组。

  Examples:
    count(3) => [1, 2, 3]
    count(5) => [1, 2, 3, 4, 5]
    count(-1) => []
*/
function count(amount: number): number[];

如果你愿意的话就自己尝试一下吧！我想大多数人都会想出这样的解决方案：

function count(amount: number): number[] {
    let nums: number[] = [];
    for (let i = 1; i <= amount; i++) nums.push(i);
    return nums;

这是一个很好的解决方案，效果很好！

但现在，我将提出一个任意挑战来介绍尾调用优化。你能将其表示为递归函数吗？

试一试。经过一番思考，您可能会想到：

const count = (amount: number) => (amount > 0 ? [...count(amount - 1), amount] : []);

这是一个简洁的解决方案！数学课上的递归关系可能看起来很熟悉。

你可能会想，“看起来循环可以用递归更优雅地表达！” 

但是，现在我有一些悲伤的事情要分享。尝试做：

• count(100000)（Deno 和 Bun 允许直接运行 TypeScript）。
• 你会得到错误Maximum call stack size exceeded。

递归占用了调用堆栈上宝贵的内存！
可能有命令可以增加程序的调用堆栈大小，但操作系统只允许这么多。

堆上的内存受到的限制要少得多。我们怎样才能使用递归而不用担心超出调用堆栈呢？
答案是：希望你的 JavaScript 引擎实现 TCO，并以可优化的方式编写你的递归！

重写函数以进行尾调用优化的过程通常涉及将状态移至参数。递归调用必须是函数 AST 中的最后一件事。我们的递归函数的 TCO 版本如下所示：

const count = (amount: number, cur: number[] = []) =>
    cur.length >= amount ? cur : count(amount, [...cur, cur.length + 1]);

它稍微不那么简洁和优雅，但现在可以对尾调用进行优化！如果我们 count(100000)使用 Deno 运行，我们仍然会得到 error: Uncaught RangeError: Maximum call stack size exceeded. 有了Bun，程序现在成功运行了！

但还有一个问题……这个解决方案真的很慢。

count(100000)使用此 TCO 解决方案只需 7 秒即可完成。原始的 for 循环解决方案采用.01s. 我们怎样才能在仍然使用递归的情况下获得与 for 循环解决方案类似的性能？

我们使用突变：

function count(amount: number, cur: number[] = []) {
    if (cur.length >= amount) return cur;
    cur.push(cur.length + 1);
    return count(amount, cur);
}

这个函数开始看起来很像原来的 for 循环解决方案。它不再非常简洁或优雅。但是，它运行count(100000)是.01s

结论
我内心极简主义的部分非常喜欢 TCO。它使语言能够表达复杂而高效的程序，而无需命令式循环。就 JavaScript 而言，这意味着该语言的较小子集可以表达所有程序。大多数初学者都被教导循环语句，就好像它们是每种语言的基础或必需的一样。但事实并非如此。使用 TCO，您可以使用递归表达任何循环语句并获得类似的性能。

像 LISP 这样依赖递归的语言通常指定必须在其语言规范中实现 TCO。遗憾的是，TCO 仅在 JavaScriptCore 中实现。值得庆幸的是，Bun 和 Safari 使用 JavaScriptCore！