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

Question

我正在阅读幻灯片使用V8破解Javascript速度限制,并且有一个示例,如下面的代码.我无法弄清楚为什么<=比<这种情况慢,有人可以解释一下吗？任何评论都表示赞赏.

慢:

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

Answer 1

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

这里的性能差异远大于一次额外迭代所解释的,并且在演示结束时解释了问题.

this.primes 是一个连续的数组(每个元素都有一个值),元素都是数字.

JavaScript引擎可以将这样的数组优化为实际数字的简单数组,而不是碰巧包含数字但可能包含其他值或没有值的对象数组.第一种格式访问速度要快得多:它占用的代码更少,而且数组更小,因此它更适合缓存.但是有些条件可能会阻止使用这种优化格式.

一个条件是如果缺少一些数组元素.例如:

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

现在有什么价值a[1]？它没有任何价值.(说它具有值是不正确的undefined- 包含该undefined值的数组元素与完全缺失的数组元素不同.)

没有办法用数字表示这一点,因此JavaScript引擎被迫使用较不优化的格式.如果a[1]包含与其他两个元素类似的数值,则该数组可能仅被优化为数字数组.

如果您尝试访问数组边界之外的元素,则强制进入去优化格式的数组的另一个原因可能是如演示文稿中所述.

第一个循环<=尝试读取超过数组末尾的元素.算法仍能正常工作,因为在最后一次额外迭代中:

• this.primes[i]评估为undefined因为i超过了数组结束.
• candidate % undefined(对于任何值candidate)评估为NaN.
• NaN == 0评估为false.
• 因此,return true不执行.

所以就好像额外的迭代从未发生过 - 它对其余逻辑没有影响.代码产生与没有额外迭代时相同的结果.

但到了那里,它试图在数组末尾读取一个不存在的元素.这迫使阵列退出优化 - 或者至少在本次谈话时做到了.

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

该问题在谈话的第90-91页中有所描述,在此之前和之后的页面中进行了相关讨论.

我碰巧参加了这个Google I/O演示,然后与演讲者(V8作者之一)进行了交谈.我一直在自己的代码中使用一种技术,包括读取数组末尾作为误导(事后看来)尝试优化某种特定情况.他证实,如果你甚至试图读过数组的末尾,那么就会阻止使用简单的优化格式.

如果V8作者所说的仍然是真的,那么读取数组的末尾将阻止它被优化,并且它将不得不回退到较慢的格式.

现在,V8可能在此期间得到了改进,以有效地处理这种情况,或者其他JavaScript引擎以不同的方式处理它.我不知道这种方式或其他方式,但这种去优化是演示文稿所讨论的内容.

Answer 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);

这导致数组中的HOLEY元素种类在V8中,即使数组最终完全填充/打包/连续.通常,对多孔数组的操作比打包数组上的操作慢,但在这种情况下,差异可以忽略不计:每当我们进入循环内部时,它相当于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另一方面,相当于效率较低的方式Float64Mod,因为undefined它表示为双倍.

通过更改此行中的<=into <,确实可以改进代码片段:

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

...不是因为<=某种程度上是一个优越的运算符<,而是因为这避免了在这种特殊情况下读取的越界.

Answer 3

TL; DR较慢的循环是由于访问数组'越界',这会强制引擎以较少甚至不优化的方式重新编译函数,或者不使用任何这些优化来开始编译函数(如果(JIT-)编译器在第一次编译"版本"之前检测到/怀疑这种情况,请在下面阅读原因;

有人不得不这样说(完全没有人说过):
曾经有一段时间,OP的片段将成为初学者编程书中的一个事实上的例子,旨在概述/强调javascript中的'数组'已编入索引在0,而不是1,并因此被用作常见的'初学者错误'的例子(你不喜欢我如何避免短语'编程错误' ;)):越界数组访问.

示例1:使用基于0的索引(总是在ES262中)的5个元素的
a Dense Array(连续的(在索引之间没有间隙)和实际上每个索引的元素).

var arr_five_char=['a', 'b', 'c', 'd', 'e']; // arr_five_char.length === 5
//  indexes are:    0 ,  1 ,  2 ,  3 ,  4    // there is NO index number 5

因此,我们并没有真正谈论<vs <=(或"一次额外迭代")之间的性能差异,但我们正在谈论:
'为什么正确的代码段(b)比错误的代码段(a)运行得更快？

答案是2倍(尽管从ES262语言实现者的角度来看,两者都是优化形式):

1. 数据表示:如何在内存中表示/存储Array(对象,hashmap,'real'数值数组等)
2. 功能机器代码:如何编译访问/处理(读/修)这些'数组'的代码

项目1足够(并且正确地恕我直言)由接受的答案解释,但是在第2项:编译中仅花费2个单词("代码").

更准确地说:JIT-Compilation,更重要的是JIT- RE -Compilation!

语言规范基本上只是对一组算法的描述("为实现定义的最终结果而执行的步骤").事实证明,这是描述语言的一种非常美妙的方式.它留下了引擎用于实现指定结果的实际方法,这些方法对实现者开放,提供了充分的机会来提出更有效的方法来产生定义的结果.符合规范的引擎应该为任何定义的输入提供符合规范的结果.

现在,随着javascript代码/库/使用量的增加,以及记住"真实"编译器使用了多少资源(时间/内存/等),显然我们不能让访问网页的用户等待那么久(并且需要它们)有这么多资源可用).

想象一下以下简单的功能:

function sum(arr){
  var r=0, i=0;
  for(;i<arr.length;) r+=arr[i++];
  return r;
}

完全清楚,对吗？不需要任何额外的澄清,对吗？返回类型是Number吧？
嗯..不,不,不...这取决于您传递给命名函数参数的参数arr...

sum('abcde');   // String('0abcde')
sum([1,2,3]);   // Number(6)
sum([1,,3]);    // Number(NaN)
sum(['1',,3]);  // String('01undefined3')
sum([1,,'3']);  // String('NaN3')
sum([1,2,{valueOf:function(){return this.val}, val:6}]);  // Number(9)
var val=5; sum([1,2,{valueOf:function(){return val}}]);   // Number(8)

看到问题？然后考虑这只是几乎没有抓住大量可能的排列...我们甚至不知道什么类型的函数RETURN直到我们完成...

现在想象一下这个相同的函数代码实际上用于不同类型甚至输入的变化,完全按字面意思(在源代码中描述)和动态程序生成的'数组'.

因此,如果你要编译函数sumJUST ONCE,那么总是返回任何和所有类型输入的规范定义结果的唯一方法,显然,只有通过执行所有规范规定的主要和子步骤才能保证规范符合结果(就像一个未命名的pre-y2k浏览器).没有优化(因为没有假设)和死慢的解释脚本语言仍然存在.

JIT-Compilation(Just in Time中的JIT)是当前流行的解决方案.

因此,您开始使用关于它的功能,返回和接受的假设来编译函数.
你想出了尽可能简单的检查,以检测函数是否可能开始返回非符合规范的结果(例如因为它接收到意外的输入).然后,抛弃先前的编译结果并重新编译为更精细的内容,决定如何处理您已经拥有的部分结果(是否可以信任或再次计算以确保),将函数绑定到程序中并且再试一次.最终回归到规则中的逐步脚本解释.

所有这些都需要时间!

所有浏览器都在他们的引擎上工作,对于每个子版本,您将看到事物改进和退化.字符串在历史中的某些时刻是真正不可变的字符串(因此array.join比字符串连接更快),现在我们使用绳索(或类似)来缓解问题.两者都返回符合规范的结果,这才是最重要的!

简而言之:只是因为javascript语言的语义经常让我们退缩(就像在OP的例子中这个无声的错误)并不意味着'愚蠢'的错误增加了编译器吐出快速机器代码的机会.它假设我们编写了"通常"正确的指令:我们'用户'(编程语言)必须具备的当前口头禅是:帮助编译器,描述我们想要的东西,支持常见习语(从asm.js中获取基本理解的提示)什么浏览器可以尝试优化和为什么).

因此,谈论性能既重要又是一个雷区(并且由于所说的雷场,我真的想以指向(和引用)一些相关材料结束:

访问不存在的对象属性和超出范围的数组元素将返回undefined值而不是引发异常.这些动态特性使得JavaScript编程变得方便,但它们也使得将JavaScript编译成高效的机器代码变得困难.

...

有效的JIT优化的一个重要前提是程序员以系统的方式使用JavaScript的动态特性.例如,JIT编译器利用这样的事实:对象属性通常以特定顺序添加到给定类型的对象中,或者很少发生超出范围的数组访问.JIT编译器利用这些规律性假设在运行时生成有效的机器代码.如果代码块满足假设,则JavaScript引擎执行有效的生成的机器代码.否则,引擎必须回退到较慢的代码或解释程序.

资料来源:
"JITProf:精确定位JIT不友好的JavaScript代码"
伯克利出版,2014年,由两宫,迈克尔·普拉德尔,科希克参议员
http://software-lab.org/publications/jitprof_tr_aug3_2014.pdf

ASM.JS(也不喜欢out out bound array access):

提前编译

因为asm.js是JavaScript的严格子集,所以此规范仅定义验证逻辑 - 执行语义只是JavaScript的执行语义.但是,经过验证的asm.js可以进行提前(AOT)编译.此外,AOT编译器生成的代码非常高效,具有以下特点:

• 整数和浮点数的未装箱表示;
• 没有运行时类型检查;
• 没有垃圾收集; 和
• 高效的堆加载和存储(实现策略因平台而异).

无法验证的代码必须通过传统方式(例如,解释和/或即时(JIT)编译)回退到执行.

http://asmjs.org/spec/latest/

最后https://blogs.windows.com/msedgedev/2015/05/07/bringing-asm-js-to-chakra-microsoft-edge/
在删除边界时,有一小部分关于引擎内部性能改进的小部分 -检查(虽然只是提升界限 - 在循环外检查已经有40%的改善).

编辑:
请注意,多个来源谈论不同级别的JIT重新编译到解释.

基于以上信息的理论示例,关于OP的片段:

• 打电话给isPrimeDivisible
• 使用一般假设编译isPrimeDivisible(比如没有越界访问)
• 做工作
• BAM,突然阵列访问超出范围(在最后).
• Crap,说引擎,让我们使用不同的(较少)假设重新编译isPrimeDivisible,这个示例引擎不会试图弄清楚它是否可以重用当前的部分结果,所以
• 使用较慢的函数重新计算所有工作(希望它完成,否则重复,这次只是解释代码).
• 返回结果

因此,时间是:
第一次运行(最后失败)+使用较慢的机器代码再次完成所有工作,每次迭代+重新编译等.在这个理论示例中,显然需要> 2倍 !

编辑2 :( 免责声明:基于以下事实的猜想)
我越想到它,我越认为这个答案可能实际上解释了对错误片段的这种"惩罚"的更主要原因(或者在片段b上的表现奖励) ,取决于你如何看待它,正是为什么我喜欢称它(片段a)编程错误:

假设这this.primes是一个"密集阵列"的纯数字,这是非常诱人的

• 源代码中的硬编码文字(已知的优秀候选者成为'真实'数组,因为在编译时编译器已经知道所有内容)或
• 最有可能使用数字函数生成,new Array(/*size value*/)以递增的顺序填充预先大小的()(另一个长时间已知的候选者成为"真正的"数组).

我们也知道primes数组的长度被缓存为prime_count!(表明它的意图和固定大小).

我们也知道大多数引擎最初都会将Arrays作为修改后的副本(需要时),这样可以更快地处理它们(如果你不改变它们).

因此可以合理地假设Array primes很可能已经是内部优化的数组,在创建后不会被更改(如果在创建后没有代码修改数组,编译器很简单),因此已经是(如果适用的话)引擎以优化的方式存储,就像它是一个Typed Array.

正如我试图用我的sum函数示例说明的那样,高通过的参数会影响实际需要发生的事情,以及如何将特定代码编译为机器代码.传递String给sum函数不应该改变字符串,而是改变函数JIT编译的方式!传递一个数组sum应该编译一个不同的(可能甚至是这个类型的附加,或者他们称之为'形状',已经通过的对象)版本的机器代码.

因为看起来有点bonkus将类似Typed_Array的primes数组转换为something_else,而编译器知道这个函数甚至不会修改它!

根据这些假设,有两个选择:

1. 编译为数字计算器,假设没有越界,最后遇到越界问题,重新编译和重做工作(如上面编辑1中的理论示例所述)
2. 编译器已经检测到(或怀疑？)超出绑定的访问权限,并且函数是JIT-Compiled,好像传递的参数是一个稀疏对象导致功能较慢的机器代码(因为它会有更多的检查/转换/强制等等.).换句话说:函数永远不能用于某些优化,它被编译为好像它收到了一个'稀疏数组'( - like)参数.

我现在真的很想知道这两个中的哪一个!

Answer 4

为了增加一些科学性,这里有一个jsperf

https://jsperf.com/ints-values-in-out-of-array-bounds

它测试一个充满int的数组的控制情况,并在保持在边界内的情况下进行模数运算.它有5个测试用例:

• 1.循环出界
• 2.多孔阵列
• 3.针对NaN的模块化算法
• 4.完全未定义的值
• 5.使用 new Array()

它表明前4个案例对性能非常不利.循环越界比其他3更好,但所有4比最好的情况慢大约98%.
这个new Array()案例几乎与原始数组一样好,只有几个百分点慢.