为什么在V8中使用此代码片段时,<=比<慢?

2022-06-15 00:00:00 javascript v8

我正在阅读幻灯片Breaking the Javascript Speed Limit with 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

解决方案

我在谷歌研究V8,希望在现有答案和评论的基础上提供一些其他见解。

作为参考,以下是the slides中的完整代码示例:

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的POST中的代码片段并不清楚这一点,但当您查看初始化this.primes

的代码时,就会清楚地看到这一点
this.primes = new Array(iterations);

这将导致在V8中使用a HOLEY elements kind的数组,即使该数组最终完全填满/打包/连续。一般来说,对孔数组的操作比对压缩数组的操作慢,但在这种情况下,差异可以忽略不计:每次我们在isPrimeDivisible内的循环中点击this.primes[i]时,它相当于额外的一个SMI(小整数)检查(以防止出现漏洞)。没什么大不了的!

TL;DR阵列HOLEY不是此处的问题。


其他人指出,代码读取超出了界限。一般建议avoid reading beyond the length of arrays,在这种情况下,确实可以避免性能的大幅下降。但为什么呢?V8 can handle some of these out-of-bound scenarios with only a minor performance impact.那么这个特殊的案例有什么特别之处呢?

越界读取导致this.primes[i]在该行undefined

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

这就引出了真正的问题:%运算符现在用于非整数操作数!

  • integer % someOtherInteger可以非常高效地计算;JavaScript引擎可以为这种情况生成高度优化的机器码。

  • integer % undefined另一方面,Float64Mod的效率较低,因为undefined表示为双精度。

确实可以通过将该行上的<=更改为<来改进代码片段:

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

...不是因为<=在某种程度上是比<更高级的运算符,而是因为这避免了在此特定情况下的越界读取。

相关文章