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

html5 • • 问答

我正在将一种语言的编译器优化为 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. 请注意，唯一的区别是(() => ...)()在 的返回周围添加了一个立即调用的 lambda, add。为什么这个添加的调用使我的程序快两倍？

[1] MacBook Pro 13" 2020，2.3 GHz 四核 Intel Core i7，Node.js v15.3.0

回答

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

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

一点背景知识：将一个函数内联到另一个函数（而不是调用它）是优化编译器执行以实现更好性能的标准技巧之一。不过，这是一把双刃剑：从好的方面来说，它避免了调用开销，并且通常可以实现进一步的优化，例如常量传播或消除重复计算（请参见下面的示例）。不利的一面是，它会导致编译需要更长的时间（因为编译器会做更多的工作），并且会导致生成更多的代码并将其存储在内存中（因为内联函数有效地复制了它），并且在像 JavaScript 这样的动态语言中优化的代码通常依赖于受保护的假设，

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

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

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

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

现在，在了解发生了什么之后，我们可以回到“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)简单地实现as return n + m，那么它会在 2 毫秒内终止——算法优化胜过优化编译器可能完成的任何事情:-)

附录：优化的好处示例。考虑这两个函数：

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

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

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

  1. 评估 temp1 = (x ** 2)
  2. 调用InternalDetail参数x, 0,2
  3. 评估 temp2 = (x + 0)
  4. 评估 temp3 = temp2 ** 2
  5. 返回temp3给调用者
  6. 评估 temp4 = temp1 + temp3
  7. 返回temp4。

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

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

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

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

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

  1. 评估 temp1 = (x ** 2)
  2. 评估 temp2 = temp1 + temp1
  3. 返回 temp2

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

  • Outstanding answer, as always, and +1 for "*algorithmic optimization beats anything an optimizing compiler could possibly accomplish*" alone 🙂
以上是为什么添加立即调用的lambda会使我的JavaScript代码速度提高2倍？的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>