为什么 < = 比 < 在 V8中使用这个代码片段要慢？

我正在阅读的幻灯片 用 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;
}

(提示: primes 是一个长度为 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
14558 次浏览
小开

其他的回答和注释提到这两个循环之间的区别在于第一个循环比第二个循环多执行一次迭代。这是事实，但是在一个增长到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 引擎以不同的方式处理它。我不知道该怎么做，但是这种去优化就是演讲中所说的。

小开

较慢的循环是由于访问数组“出界”，这要么迫使引擎重新编译函数的优化较少，甚至没有优化或不编译函数的任何这些优化开始(如果(JIT -)编译器检测到/怀疑这种情况之前的第一个编译“版本”) ，阅读下面的原因;

有人只是 已经这样说(完全惊讶没有人已经这样做了) :
曾经有一段时间，OP 的代码片段实际上是一本初学者编程书籍的例子，这本书旨在概述/强调 javascript 中的“数组”是从0开始索引的，而不是从1开始索引的，因此被用作一个常见的“初学者错误”的例子(难道你不喜欢我如何避免使用短语“编程错误”;)) : 越界数组访问。

例子一:
使用基于0的索引(始终在 ES262中) ，由5个元素组成的 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



因此，我们实际上并不是在讨论 <和 <=之间的性能差异(或者“一次额外的迭代”) ，而是在讨论:
‘为什么正确的代码段(b)比错误的代码段(a)运行得更快?’？

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

  1. 数据表示: 如何在内存中表示/存储数组(对象、散列表、实数数组等)
  2. Functional Machine-code: 如何编译访问/处理(读取/修改)这些“数组”的代码

项目1是充分(并正确地 IMHO)的解释由 接受的答案，但只花2个字(“代码”)在 项目2: 汇编。

更准确地说: JIT-编译，甚至更重要的是 JIT-< em > RE -编译！

语言规范基本上只是一组算法的描述(“为实现已定义的最终结果而执行的步骤”)。事实证明，这是一种非常美丽的描述语言的方式。 而且它把引擎用来实现特定结果的实际方法留给了实现者，给了他们足够的机会去想出更有效的方法来产生特定的结果。 一个规格合格的引擎应该为任何已定义的输入提供规格合格的结果。

现在，随着 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)

看到问题所在了吗? 那么考虑到这只是勉强刮掉了大量可能的排列..。 我们甚至不知道函数返回的类型，直到我们完成..。

现在想象一下这个相同的函数—— 密码实际上被用于不同类型的输入，甚至是输入的变体，包括完全字面(在源代码中)描述的和程序中动态生成的“数组”。.

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

JIT 编译(JIT 即时编译)是当前流行的解决方案。

因此，您开始使用关于函数的功能、返回和接受的假设来编译函数。
您可以进行尽可能简单的检查，以检测函数是否可能开始返回非规范一致性结果(比如因为它接收到意外输入)。 然后，抛弃之前的编译结果，重新编译成更复杂的结果，决定如何处理已经得到的部分结果(是否可以信任或再次计算以确保有效) ，将函数绑定到程序中，然后再试一次。最终回归到逐步的脚本解释，就像在规范中那样。

这一切都需要时间！

所有的浏览器都在自己的引擎上工作，对于每一个子版本，你都会看到事情的进步和倒退。字符串在历史上的某个时刻是真正不可变的字符串(因此 array.join 比字符串连接更快) ，现在我们使用了绳子(或类似的东西)来缓解这个问题。两者都返回符合规范的结果，这才是最重要的！

长话短说: 仅仅因为 javascript 语言的语义常常得到我们的支持(就像 OP 例子中的这个无声的 bug)并不意味着“愚蠢”的错误会增加编译器吐出快速机器码的机会。它假设我们写了“通常”正确的指令: 当前我们“用户”(编程语言)必须有的口头禅是: 帮助编译器，描述我们想要的，喜欢常见的习惯用法(从 asm.js 获取提示，以便基本理解浏览器可以尝试优化什么和为什么)。

正因为如此，谈论性能既重要，又是一个 雷区(因为上述雷区，我真的想以指出(并引用)一些相关材料作为结束:

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

...

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

来源:
“ JIT 教授: 精确定位 JIT 不友好的 JavaScript 代码”
伯克利出版社，2014年，作者: 梁功，迈克尔 · 普拉德尔，库什克 · 森。
Http://software-lab.org/publications/jitprof_tr_aug3_2014.pdf

ASM.JS (也不喜欢出界数组访问) :

提前编译

因为 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 片段的理论例子:

  • 调用 isPrimeDiability
  • 使用一般假设(比如无出界访问)编译 isPrimeDiible
  • 干活
  • 突然数组访问出界(在最后)。
  • 糟糕，engine 说，让我们使用不同的(更少的)假设重新编译 isPrimeDiible，这个示例引擎并不试图弄清楚它是否可以重用当前的部分结果，因此
  • 使用较慢的函数重新计算所有工作(希望它完成，否则重复，这次只是解释代码)。
  • 返回结果

因此，当时的情况是:
第一次运行(最后失败) + 再次使用较慢的机器代码为每次迭代做所有的工作 + 重新编译等。显然需要超过2倍的时间 在这个理论例子中！



编辑2: < em > (免责声明: 基于以下事实的猜测)
我越想越觉得这个答案实际上可以解释错误代码片段 a (或者代码片段 b 的性能奖励，取决于你如何看待它)受到“惩罚”的更主要的原因，确切地说，为什么我坚持把它(代码片段 a)称为编程错误:

假设 this.primes是一个“密集数组”纯数值是非常诱人的

  • 源代码中的硬编码文字(编译器 之前在编译时已经知道所有内容，这是成为“实数”数组的优秀候选者)或
  • 最有可能使用一个数值函数生成，该函数按照升序顺序填充预先设定的大小(new Array(/*size value*/))(另一个长期以来已知的候选者成为一个“真正的”数组)。

我们还知道，primes数组的长度是 缓存作为 prime_count! (表明它的意图和固定的大小)。

我们还知道，大多数引擎最初通过数组作为拷贝修改(当需要时) ，这使得处理它们更快(如果你不改变它们)。

因此，我们可以合理地假设 Array primes很可能已经是一个内部优化的数组，它在创建后不会改变(编译器很容易知道在创建后是否没有代码修改数组) ，因此已经(如果适用于引擎)以优化的方式存储，基本上 好像是一个 Typed Array。

正如我在我的 sum函数示例中试图说明的那样，传递的参数对实际需要发生的事情以及特定代码如何编译成机器码有很大的影响。将 String传递给 sum函数不应该更改字符串，而应该更改函数的 JIT 编译方式！将 Array 传递给 sum应该编译一个不同版本的机器代码(也许甚至为传递的对象的这种类型(或者他们称之为“形状”)增加一个版本。

因为当编译器知道这个函数不会修改它的时候，将类似于 Type _ Array 的 primes Array 动态转换为 something _ else 似乎有点不明智！

在这些假设下，只剩下两种选择:

  1. 作为数字处理器进行编译，假设没有出界，最后遇到出界问题，重新编译和重做工作(如上面编辑1中的理论例子所概述的)
  2. 编译器已经检测到(或怀疑?)这个函数是 JIT 编译的，就好像传递的参数是一个稀疏对象，导致函数机器代码变慢(因为它会有更多的检查/转换/强制等)。换句话说: 该函数从来没有资格进行某些优化，它的编译就好像它接收到了一个“稀疏数组”(类似)参数。

我现在真的不知道这两个是哪一个！

小开
最佳答案

我在 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元素的数组，即使该数组最终完全填充/打包/连续。一般来说，对多孔阵列的操作比对填充阵列的操作要慢，但在这种情况下，这种差别可以忽略不计: 每次在 isPrimeDivisible的循环中我们碰到 this.primes[i]时，它相当于1次额外的 Smi (小整数)检查(以防止出现多孔)。没什么大不了的！

DR 这里的问题不在于数组是 HOLEY。

其他人指出代码读出界限。通常建议使用 避免读取超出数组长度的内容，在这种情况下，它确实可以避免性能的大幅下降。但是为什么呢？那么，这个特例有什么特别之处呢？

越界读取导致 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) {

... 不是因为 <=比 <更优秀，而是因为在这种情况下，它避免了出界读取。

小开

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

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

它测试一个充满 int 和 loop 的数组的控制同余关系，同时保持在一定范围内。它有5个测试案例:

  • 1. 循环出界
  • 2. 多孔阵列
  • 3. 同余关系对抗 NaNs
  • 4. 完全未定义的价值观
  • 5. 使用 new Array()

结果表明，前4例 真的对性能均有不良影响。循环出界比其他3种情况稍微好一点，但是所有4种情况都比最好的情况大约慢98% 。
new Array()几乎和原始数组一样好，只是慢了几个百分点。


提交答案