为什么添加立即调用的 lambda 会使我的 JavaScript 代码快 2 倍？

Question

我正在将一种语言的编译器优化到 JavaScript，并且发现了一个非常有趣的案例：

function add(n,m) {
  return n === 0 ? m : add(n - 1, m) + 1;
};
var s = 0;
for (var i = 0; i < 100000; ++i) {
  s += add(4000, 4000);
}
console.log(s);

在我的机器上需要 2.3s 才能完成[1]。但是如果我做一个很小的改变：

function add(n,m) {
  return (() => n === 0 ? m : add(n - 1, m) + 1)();
};
var s = 0;
for (var i = 0; i < 100000; ++i) {
  s += add(4000, 4000);
}
console.log(s);

它在 1.1s 内完成。请注意，唯一的区别是在 add 的 return 周围添加了一个立即调用的 lambda (() => ...)()。 为什么这个添加的调用使我的程序快两倍？

[1] MacBook Pro 13" 2020，2.3 GHz 四核英特尔酷睿 i7，Node.js v15.3.0

Answer 1

有意思！从代码来看，很明显 IIFE 包装版本应该更慢，而不是更快：在每次循环迭代中，它都会创建一个新的函数对象并调用它（优化编译器最终会避免这种情况，但事实并非如此） t 马上开始），所以通常只会做更多的工作，应该需要更多的时间。

这种情况下的解释是内联。

一些背景知识：将一个函数内联到另一个函数（而不是调用它）是优化编译器执行以实现更好性能的标准技巧之一。不过，这是一把双刃剑：从好的方面来说，它避免了调用开销，并且通常可以实现进一步的优化，例如常量传播或消除重复计算（请参见下面的示例）。不利的一面是，它会导致编译时间更长（因为编译器做了更多工作），并且会导致生成更多代码并将其存储在内存中（因为内联函数有效地复制了它），并且在 [= 这样的动态语言中115=] 在优化代码通常依赖于谨慎假设的情况下，它增加了这些假设之一被证明是错误的风险，并且因此不得不丢弃大量优化代码。

一般来说，做出完美的内联决策（不要太多，也不要太少）需要预测未来：提前知道代码执行的频率和参数。那当然是不可能的，因此优化编译器使用各种规则/“启发式”来猜测什么可能是一个合理的好决定。

V8 目前的一个规则是：不要内联递归调用。

这就是为什么在您的代码的更简单版本中，add 不会内联到自身中。 IIFE 版本本质上有两个函数相互调用，这被称为“相互递归”——事实证明，这个简单的技巧足以愚弄 V8 的优化编译器并使其避开其“不要内联递归调用”规则.相反，它愉快地将未命名的 lambda 内联到 add，并将 add 内联到未命名的 lambda 中，依此类推，直到其内联预算在约 30 轮后用完。（旁注：“内联多少”是一种有点复杂的启发式方法，特别是考虑了函数大小，因此我们在这里看到的任何特定行为确实是特定于这种情况的。）

在这种涉及的函数非常小的特定场景中，内联很有帮助，因为它避免了调用开销。所以在这种情况下，内联提供了更好的性能，即使它是递归内联的（伪装的）情况，这通常对性能不利。它确实是有代价的：在简单版本中，优化编译器仅花费 3 毫秒编译 add，为其生成 562 字节的优化代码。在 IIFE 版本中，编译器花费 30 毫秒为 add 生成了 4318 字节的优化代码。这就是为什么它不像得出“V8 应该总是内联更多”那么简单的原因之一：编译的时间和电池消耗，内存消耗也很重要，以及在一个简单的 10 行中可接受的成本（并显着提高性能）在 100,000 行的应用程序中，演示可能会产生不可接受的成本（甚至可能会降低整体性能）。

现在，了解了发生了什么，我们可以回到“IIFE 有开销”的直觉，并制作一个更快的版本：

function add(n,m) {
  return add_inner(n, m);
};
function add_inner(n, m) {
  return n === 0 ? m : add(n - 1, m) + 1;
}

在我的机器上，我看到：

简单版：1650 毫秒
IIFE 版本：720 毫秒
add_inner 版本：460 毫秒

当然，如果您将 add(n, m) 简单地实现为 return n + m，那么它会在 2 毫秒后终止——算法优化胜过优化编译器可能完成的任何事情:-)

附录：优化优势示例。考虑这两个函数：

function Process(x) {
  return (x ** 2) + InternalDetail(x, 0, 2);
}

function InternalDetail(x, offset, power) {
  return (x + offset) ** power;
}

（显然，这是愚蠢的代码；但我们假设它是在实践中有意义的东西的简化版本。）
天真地执行时，会发生以下步骤：

评价temp1 = (x ** 2)
使用参数 x、0、2

InternalDetail

评价temp2 = (x + 0)
评价temp3 = temp2 ** 2
return temp3 给来电者
评价temp4 = temp1 + temp3
return temp4.

如果优化编译器执行内联，那么作为第一步它将得到：

function Process_after_inlining(x) {
  return (x ** 2) + ( (x + 0) ** 2 );
}

允许两个简化：x + 0 可以折叠为 x，然后 x ** 2 计算发生两次，因此第二次出现可以通过重用来自的结果来替换第一个：

function Process_with_optimizations(x) {
  let temp1 = x ** 2;
  return temp1 + temp1;
}

因此与原始执行相比，我们从 7 步减少到 3 步：

评价temp1 = (x ** 2)
评价temp2 = temp1 + temp1
return temp2

我并不是预测现实世界的性能会从 7 个时间单位变为 3 个时间单位；这只是为了直观地说明为什么内联可以帮助减少一定量的计算负载。
脚注：为了说明所有这些东西有多么棘手，请考虑仅用 x 替换 x + 0 在 JavaScript 中并不总是可行的，即使编译器知道 x 总是一个数字：如果 x 恰好是 -0，则向其添加 0 会将其更改为 +0，这很可能是可观察到的程序行为 ;-)

为什么添加立即调用的 lambda 会使我的 JavaScript 代码快 2 倍？

Why does adding in an immediately invoked lambda make my JavaScript code 2x faster?

javascript

optimization

v8

compiler-optimization

node.js