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

2020/10/27 18:42 · javascript ·  · 0评论

我正在阅读使用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

我在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表示为double ,因此效率较低

实际上,可以通过将以下代码段更改<=来改进代码段<

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

...不是因为<=某种程度上比运算符优越<,而是因为这样可以避免在这种情况下读取越界。

其他答案和评论提到这两个循环之间的区别在于,第一个循环比第二个循环执行更多的迭代。的确如此,但是在一个增长到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引擎可以不同地处理它。我不知道其中的一种或另一种方法,但是这种非优化正是演示文稿所讨论的。

TL; DR较慢的循环归因于访问数组的“越界”,这要么迫使引擎以更少的优化甚至没有优化就重新编译函数,或者不以任何以这些优化开头的函数来编译函数(如果(JIT-)编译器在第一次编译“版本”之前检测到/怀疑此情况),请继续阅读下面的原因;



有人刚刚
说这(完全惊讶没人已经这样做):

曾经有一段时间,当OP的片断将是一个初学编程的书旨在勾勒出一个事实上的例子/强调的是“阵列”在javascript是索引的起点为0,而不是1,因此可以用作常见“初学者错误”的示例(您不喜欢我如何避免使用“编程错误”这一短语
;)):越界数组访问

实施例1:

一个
Dense Array(是连续的(在索引之间没有间隙的装置),实际上在每个索引处的元素)使用基于0的索引5种元素的(总是在ES262)。

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. 数据表示:如何在内存中内部表示/存储数组(对象,哈希图,“实际”数字数组等)
  2. 功能性机器码:如何编译访问/处理(读取/修改)这些“数组”的代码

接受的答案足以充分说明第1项(正确的恕我直言),但是第2项:编译仅花费了2个字(“代码”)

更准确地说:JIT编译,更重要的是JIT 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)

看到问题了吗?然后考虑一下,这只是勉强刮除大量可能的排列...在完成之前,我们甚至不知道函数RETURN是哪种类型...

现在想象一下,实际上是在不同类型甚至输入的变体上使用了相同的功能代码,完全按字面意义(在源代码中)进行了描述,并在程序中动态生成了“数组”。

因此,如果您要编译函数sumJUST ONCE,那么唯一可以始终返回任何类型和所有类型输入的规范定义结果的唯一方法,显然,只有执行所有规范规定的main AND子步骤,才能保证符合规范的结果(如未命名的y2k之前的浏览器)。没有优化(因为没有任何假设),而且仍然存在缓慢的解释性脚本语言。

JIT编译(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(也不喜欢超出范围的数组访问):

提前编译

由于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,突然数组访问超出范围(在最后)。
  • 引擎说,废话,让我们使用不同的(较少)假设重新编译isPrimeDivisible,并且该示例引擎不会尝试确定它是否可以重用当前的部分结果,因此
  • 使用较慢的功能重新计算所有工作(希望它完成了,否则重复一下,这次仅是解释代码)。
  • 返回结果

因此,时间就是:

第一次运行(最终失败)+对每次迭代使用较慢的机器代码再次进行所有工作+重新编译等。
在该理论示例中,显然要花费> 2倍的时间

编辑2 :( 免责声明:基于以下事实的猜想)

我想得越多,我就越认为此答案实际上可以解释对错误代码段a(或代码段b的性能奖励)进行“惩罚”的更主要的原因,具体取决于您的想法),这正是我为什么称它为代码错误(代码段a)的原因:

假设这this.primes是一个“密集数组”纯数字,或者是

  • 源代码中的硬编码文字(已知的优秀候选者将成为“真实”数组,因为编译器编译时就已经知道了所有内容)或
  • 最有可能是使用new Array(/*size value*/)以递增的顺序填充预大小(的数值函数生成的(另一个长期以来已知的候选对象成为“真实”数组)。

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

我们还知道,大多数引擎最初都会通过Arrays-on-modify(需要时复制)传递Array,从而使处理它们的速度更快(如果您不更改它们)。

因此,可以合理地假设Arrayprimes最有可能在内部已经是一个优化的数组,它在创建后不会更改(对于编译器来说很容易知道,是否没有代码在创建后修改该数组),因此已经存在(如果适用于引擎)以优化的方式存储,就好像它是一样Typed Array

正如我试图通过sum函数示例弄清楚的那样,传递的参数会影响实际需要发生的事情,以及如何将特定代码编译为机器代码。将a传递String给该sum函数不应更改字符串,而应更改该函数的JIT编译方式!将数组传递给时,sum应该编译不同版本的机器代码(可能是这种类型的附加形状,或者称为“形状”)。

由于将类Typed_Array的primes数组即时转换为something_else似乎有些无聊,而编译器知道此函数甚至都不会对其进行修改!

在这些假设下,有两个选择:

  1. 假设没有越界,作为数字压缩器进行编译,最后遇到越界问题,重新编译和重做工作(如以上编辑1中的理论示例所述)
  2. 编译器已经预先检测到(或怀疑?)超出范围的访问权限,并且该函数是JIT编译的,就好像传递的参数是一个稀疏对象导致了较慢的机器代码运行(因为它将进行更多的检查/转换/强制)等等。)。换句话说:该函数从来没有资格进行某些优化,而是像接收到“稀疏数组”(类似)参数一样进行编译。

我现在真的很奇怪这是哪两个!

为了增加一些科学性,这是一个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()情况几乎与原始阵列一样好,只是速度慢了几个百分点。

本文地址:http://javascript.askforanswer.com/weishenmezaiv8zhongshiyongcidaimaduan.html
文章标签: ,  
版权声明:本文为原创文章,版权归 javascript 所有,欢迎分享本文,转载请保留出处!

文件下载

老薛主机终身7折优惠码boke112

上一篇:
下一篇:

评论已关闭!