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

Question

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

（提示：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

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没有执行。

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

但是为了到达那里，它试图读取数组末尾之后不存在的元素。这会迫使阵列脱离优化 - 或者至少在本次演讲时是这样。

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

该问题在演讲的 pages 90-91 中有所描述，相关讨论在其前后的页面中。

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

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

现在 V8 有可能同时得到改进以有效处理这种情况，或者其他 JavaScript 引擎以不同方式处理它。我对此一无所知，但演示文稿所谈论的正是这种去优化。

Answer 2

TL;DR 较慢的循环是由于访问数组 'out-of-bounds'，这会迫使引擎重新编译函数，而优化较少甚至没有优化，或者不使用任何这些优化来编译函数（如果 (JIT-)Compiler detected/suspected 在第一次编译 'version' 之前出现这种情况），请阅读下面的原因；

有人不得不说这个（完全惊讶没有人已经这样做了）：
曾经有一段时间，OP 的片段将成为初学者编程书中的一个实际示例，旨在 outline/emphasize javascript 中的 'arrays' 从 0 开始索引，而不是 1，并因此用作常见 'beginners mistake' 的示例（你不喜欢我如何避免短语 'programing error' ;)）： 越界数组访问。

示例 1：
a Dense Array（连续（意味着索引之间没有间隙）并且实际上每个索引处有一个元素）使用基于 0 的索引（总是在 ES262 中）的 5 个元素。

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

因此，我们并不是真正在谈论 < 与 <=（或 'one extra iteration'）之间的性能差异，而是在谈论：
'why does the correct snippet (b) run faster than erroneous snippet (a)'?

答案是2倍（尽管从ES262语言实现者的角度来看两者都是优化形式）：

数据表示：如何represent/store内存中的数组（对象、hashmap、'real'数值数组等）
Functional Machine-code：如何编译accesses/handles（read/modify）这些'Arrays'

项目 1 已由充分（正确地恕我直言）解释，但在 项目 2 上仅花费 2 个字 ('the code')：汇编.

更准确地说：JIT-编译，更重要的是 JIT-RE-编译 !

语言规范基本上只是一组算法的描述（'steps to perform to achieve defined end-result'）。事实证明，这是描述语言的一种非常漂亮的方式。并且它将引擎用来实现指定结果的实际方法留给实施者开放，从而提供充分的机会来提出更有效的方法来产生定义的结果。符合规范的引擎应该为任何定义的输入提供符合规范的结果。

现在，随着 javascript code/libraries/usage 的增加，并记住 'real' 编译器使用了多少资源 (time/memory/etc)，很明显我们不能让用户访问网页等待那么久（并要求他们有那么多可用资源）。

设想以下简单函数：

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

非常清楚，对吧？不需要任何额外的说明，对吧？ return 类型是 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 是什么类型...

现在想象一下这个相同的函数-代码实际上被用于不同类型甚至输入的变体，既完全按字面意义（在源代码中）描述，又在程序中动态生成'arrays'..

因此，如果您要编译函数 sum 一次，那么唯一的方法就是总是 return 为任何和所有类型的输入提供规范定义的结果，那么显然，只有通过执行所有规范规定的主要和子步骤可以保证符合规范的结果（如未命名的 pre-y2k 浏览器）。没有优化（因为没有假设）和极慢的解释脚本语言仍然存在。

JIT-Compilation（JIT 中的 Just In Time）是当前流行的解决方案。

因此，您开始使用关于功能的假设来编译函数，returns 并接受。
你想出了尽可能简单的检查来检测函数是否可能开始 returning 不符合规范的结果（比如因为它收到了意外的输入）。然后，扔掉以前编译的结果并重新编译成更精细的东西，决定如何处理你已经拥有的部分结果（是否有效以被信任或再次计算以确保），将函数绑定回程序和再试一次。最终回到规范中的逐步脚本解释。

所有这些都需要时间！

所有浏览器都在其引擎上工作，对于每个子版本，您都会看到改进和倒退。字符串在历史上的某个时刻确实是不可变的字符串（因此 array.join 比字符串连接更快），现在我们使用绳索（或类似的）来缓解这个问题。 return 符合规范的结果，这才是最重要的！

长话短说：仅仅因为 javascript 的语言语义经常得到我们的支持（就像 OP 示例中的这个无声错误）并不意味着 'stupid' 错误会增加我们的机会编译器吐出快速机器代码。它假设我们编写了 'usually' 正确的指令：我们 'users' （编程语言）必须拥有的当前口头禅是：帮助编译器，描述我们想要的，支持常见的习语（从 asm.js 基本了解浏览器可以尝试优化的内容以及原因）。

正因为如此，谈论性能既重要又重要雷区（而且由于所说的雷区，我真的想以指向（并引用）结束) 一些相关的 material:

Access to nonexistent object properties and out of bounds array elements returns the undefined value instead of raising an exception. These dynamic features make programming in JavaScript convenient, but they also make it difficult to compile JavaScript into efficient machine code.

...

An important premise for effective JIT optimization is that programmers use dynamic features of JavaScript in a systematic way. For example, JIT compilers exploit the fact that object properties are often added to an object of a given type in a specific order or that out of bounds array accesses occur rarely. JIT compilers exploit these regularity assumptions to generate efficient machine code at runtime. If a code block satisfies the assumptions, the JavaScript engine executes efficient, generated machine code. Otherwise, the engine must fall back to slower code or to interpreting the program.

来源：
"JITProf: Pinpointing JIT-unfriendly JavaScript Code"
伯克利出版社，2014 年，龚良、Michael Pradel、Koushik Sen.
http://software-lab.org/publications/jitprof_tr_aug3_2014.pdf

ASM.JS（也不喜欢越界数组访问）：

Ahead-Of-Time Compilation

Because asm.js is a strict subset of JavaScript, this specification only defines the validation logic—the execution semantics is simply that of JavaScript. However, validated asm.js is amenable to ahead-of-time (AOT) compilation. Moreover, the code generated by an AOT compiler can be quite efficient, featuring:

unboxed representations of integers and floating-point numbers;

absence of runtime type checks;

absence of garbage collection; and

efficient heap loads and stores (with implementation strategies varying by platform).

Code that fails to validate must fall back to execution by traditional means, e.g., interpretation and/or just-in-time (JIT) compilation.

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

最后是 https://blogs.windows.com/msedgedev/2015/05/07/bringing-asm-js-to-chakra-microsoft-edge/
在删除边界检查时是否有关于引擎内部性能改进的小节（而只是在循环外解除边界检查已经有 40% 的改进）。

编辑：
请注意，多个来源讨论不同级别的 JIT-Recompilation 直至解释。

理论示例 基于上述信息，关于 OP 的片段：

调用 isPrimeDivisible
使用一般假设（比如没有越界访问）编译 isPrimeDivisible
工作
BAM，突然数组访问越界（就在最后）。
废话，引擎说，让我们使用不同的（更少的）假设重新编译 isPrimeDivisible，并且这个示例引擎不会尝试弄清楚它是否可以重用当前的部分结果，所以
使用较慢的函数重新计算所有工作（希望它完成，否则重复，这次只是解释代码）。
Return 结果

因此时间是：
首先运行（最后失败）+ 每次迭代都使用较慢的机器代码重新完成所有工作 + 重新编译等。在这个理论示例中 显然需要 >2 倍的时间!

编辑 2： （免责声明：基于以下事实的推测）
我想得越多，我就越认为这个答案可能实际上解释了错误片段 a 上这个 'penalty' 的更主要原因（或片段 b 上的性能奖励，取决于你如何看待它），正是为什么我坚持将它（片段 a）称为编程错误：

很容易假设 this.primes 是一个 'dense array' 纯数值，它是

源代码中的硬编码文字（已知优秀的候选人成为 'real' 数组，因为编译器在编译时之前已经知道所有内容）或
最有可能是使用数值函数生成的，该函数按升序顺序填充预先设定好的 (new Array(/*size value*/))（另一个长期已知的成为 'real' 数组的候选）。

我们还知道 primes 数组的长度缓存为 prime_count ！（表明它的意图和固定大小）。

我们还知道大多数引擎最初将数组作为修改时复制（需要时）传递，这使得处理它们的速度更快（如果您不更改它们）。

因此可以合理地假设 Array primes 很可能已经是内部优化的数组，创建后不会更改（编译器很容易知道是否在之后没有代码修改数组创建），因此已经（如果适用于引擎）以优化的方式存储，几乎 就好像 它是 Typed Array.

正如我试图通过我的 sum 函数示例阐明的那样，传递的参数高度影响实际需要发生的事情以及特定代码如何被编译为机器-代码。将 String 传递给 sum 函数不应更改字符串，但会更改函数的 JIT 编译方式！将数组传递给 sum 应该编译一个不同的机器代码版本（对于这种类型，或者他们称之为 'shape'，他们称之为传递的对象，甚至可能是额外的）版本。

因为将 Typed_Array-like primes 数组即时转换为 something_else 似乎有点笨拙，而编译器知道这个函数甚至不会修改它！

根据这些假设，剩下 2 个选项：

Compile as number-c运行cher假设没有越界，运行最后变成越界问题，重新编译重做（如理论示例中所述）在上面的编辑 1 中）
编译器已经预先检测到（或怀疑？）越界访问，并且该函数是 JIT 编译的，就好像传递的参数是一个稀疏对象，导致功能机器代码变慢（因为它会有更多checks/conversions/coercions 等）。换句话说：该函数从来没有资格进行某些优化，它被编译为好像它收到了一个 'sparse array'(-like) 参数。

我现在很想知道这两个是哪一个！

Answer 3

我在 Google 从事 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 上读到它很慢 --- 它不是！

其次，人们指出数组是"holey"。这在 OP 的 post 中的代码片段中并不清楚，但是当您查看初始化 this.primes:

的代码时就很清楚了

this.primes = new Array(iterations);

这会导致 V8 中的数组具有 a HOLEY elements kind，即使该数组最终完全为 filled/packed/contiguous。通常，对空数组的操作比对压缩数组的操作慢，但在这种情况下，差异可以忽略不计：它相当于 1 个额外的 Smi（小整数）检查（以防止空洞) 每次我们在 isPrimeDivisible 内的循环中点击 this.primes[i]。没什么大不了的！

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

还有人指出代码读取越界。一般建议 avoid reading beyond the length of arrays, and in this case it would indeed have avoided the massive drop in performance. But why though? 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) {

...不是因为 <= 在某种程度上比 < 更优越，而是因为这避免了在这种特殊情况下的越界读取。

Answer 4

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

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

它测试了一个充满整数的数组的控制情况，并在保持在边界内的情况下循环执行模块化运算。它有 5 个测试用例：

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

这表明前 4 种情况确实对性能不利。越界循环比其他 3 个好一点，但所有 4 个都比最好的情况慢大约 98%。
new Array() 的情况几乎和原始数组一样好，只是慢了几个百分点。

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

Why is <= slower than < using this code snippet in V8?

javascript

v8