为什么 <= 比在 V8 中使用此代码片段的 < 慢？

javascript v8

2022-08-30 02:01:46

我正在阅读幻灯片打破Javascript速度限制与V8，有一个像下面的代码一样的例子。我不明白为什么比这种情况慢，任何人都可以解释一下吗？任何意见是值得赞赏的。<=<

慢：

this.isPrimeDivisible = function(candidate) {
    for (var i = 1; i <= this.prime_count; ++i) {
        if (candidate % this.primes[i] == 0) return true;
    }
    return false;
}

（提示：素数是长度prime_count数组）

更快：

this.isPrimeDivisible = function(candidate) {
    for (var i = 1; i < this.prime_count; ++i) {
        if (candidate % this.primes[i] == 0) return true;
    }
    return false;
}

【更多信息】速度提高显著，在我的本地环境测试中，结果如下：

V8 version 7.3.0 (candidate)

慢：

 time d8 prime.js
 287107
 12.71 user 
 0.05 system 
 0:12.84 elapsed

更快：

time d8 prime.js
287107
1.82 user 
0.01 system 
0:01.84 elapsed

答案 1

其他答案和注释提到，两个循环之间的区别在于第一个循环比第二个循环执行更多的迭代。这是事实，但是在增长到 25，000 个元素的数组中，一次迭代或多或少只会产生微小的差异。作为一个大概的猜测，如果我们假设它增长的平均长度是12，500，那么我们可能期望的差异应该在1/12，500左右，或只有0.008%。

此处的性能差异比那次额外迭代所解释的要大得多，并且问题在演示结束时进行了解释。

this.primes是一个连续的数组（每个元素都有一个值），元素都是数字。

JavaScript引擎可以将这样的数组优化为实际数字的简单数组，而不是碰巧包含数字但可能包含其他值或不包含值的对象数组。第一种格式的访问速度要快得多：它需要更少的代码，数组也小得多，因此它更适合缓存。但是，在某些情况下，可能会阻止使用此优化格式。

一个条件是缺少某些数组元素。例如：

let array = [];
a[0] = 10;
a[2] = 20;

现在的价值是什么？它没有价值。（甚至说它具有值是不正确的 - 包含该值的数组元素与完全缺少的数组元素不同。a[1]undefinedundefined

没有办法只用数字来表示这一点，所以JavaScript引擎被迫使用不太优化的格式。如果包含像其他两个元素一样的数值，则该数组可能仅优化为数字数组。a[1]

数组被强制转换为取消优化格式的另一个原因可能是，如果您尝试访问数组边界之外的元素，如演示文稿中所述。

第一个循环，用于尝试读取超过数组末尾的元素。该算法仍然正常工作，因为在上一次额外的迭代中：<=

this.primes[i]计算结果为因为已超过数组末尾。undefinedi
candidate % undefined（对于的任何值），计算结果为。candidateNaN
NaN == 0计算结果为。false
因此，不执行。return true

因此，就好像额外的迭代从未发生过一样 - 它对逻辑的其余部分没有影响。该代码生成的结果与没有额外迭代的结果相同。

但为了到达那里，它试图读取数组末尾之后不存在的元素。这迫使数组退出优化 - 或者至少在本文讨论时确实如此。

第二个循环仅读取数组中存在的元素，因此它允许优化的数组和代码。<

这个问题在演讲的第90-91页中有所描述，在此之前和之后的页面中都有相关的讨论。

我碰巧参加了这个非常Google I / O的演示，并在之后与演讲者（V8作者之一）进行了交谈。我一直在自己的代码中使用一种技术，该技术涉及读取数组的末尾，作为优化特定情况的错误（事后看来）尝试。他证实，如果你试图读过数组的末尾，这将阻止使用简单的优化格式。

如果 V8 作者所说的仍然是正确的，那么阅读数组的末尾将阻止它被优化，并且它必须回退到较慢的格式。

现在，V8 可能在此期间得到了改进，可以有效地处理这种情况，或者其他 JavaScript 引擎以不同的方式处理它。我不知道这方面有一种或另一种方式，但这种去优化就是演讲所谈论的。

答案 2

我在Google从事V8工作，并希望在现有答案和评论的基础上提供一些额外的见解。

作为参考，下面是幻灯片中的完整代码示例：

var iterations = 25000;

function Primes() {
  this.prime_count = 0;
  this.primes = new Array(iterations);
  this.getPrimeCount = function() { return this.prime_count; }
  this.getPrime = function(i) { return this.primes[i]; }
  this.addPrime = function(i) {
    this.primes[this.prime_count++] = i;
  }
  this.isPrimeDivisible = function(candidate) {
    for (var i = 1; i <= this.prime_count; ++i) {
      if ((candidate % this.primes[i]) == 0) return true;
    }
    return false;
  }
};

function main() {
  var p = new Primes();
  var c = 1;
  while (p.getPrimeCount() < iterations) {
    if (!p.isPrimeDivisible(c)) {
      p.addPrime(c);
    }
    c++;
  }
  console.log(p.getPrime(p.getPrimeCount() - 1));
}

main();

首先，性能差异与和操作员直接无关。因此，请不要为了避免在代码中跳过箍，因为在Stack Overflow上读到它很慢---它不是！<<=<=

其次，人们指出数组是“漏洞百出”的。从OP的帖子中的代码片段中看不出这一点，但是当您查看初始化的代码时，可以清楚地看出：this.primes

this.primes = new Array(iterations);

这会导致数组在 V8 中具有 HOLEY 元素类型，即使数组最终完全填充/打包/连续。通常，对多孔数组的操作比对打包数组的操作慢，但在这种情况下，差异可以忽略不计：每次我们在内命中循环时，它相当于1个额外的Smi（小整数）检查（以防止孔洞）。没什么大不了的！this.primes[i]isPrimeDivisible

TL;DR 数组是 HOLEY 不是这里的问题。

其他人指出，代码读出界外。通常建议避免读取超过数组的长度，在这种情况下，它确实可以避免性能的大幅下降。但为什么呢？V8 可以处理其中一些越界方案，但对性能的影响很小。那么，这个特殊情况有什么特别之处呢？

越界读取导致在此行上：this.primes[i]undefined

if ((candidate % this.primes[i]) == 0) return true;

这就把我们带到了真正的问题：运算符现在与非整数操作数一起使用！%

integer % someOtherInteger可以非常有效地计算;JavaScript引擎可以在这种情况下生成高度优化的机器代码。
integer % undefined另一方面，这相当于一种效率较低的方式，因为被表示为双精度。Float64Modundefined

代码片段确实可以通过更改以下行上的 into 来改进：<=<

for (var i = 1; i <= this.prime_count; ++i) {

...不是因为是某种优于的运算符，而只是因为这避免了在这种特殊情况下读取的越界。<=<