JavaScript 性能 : Modulus operation of negative Number within decrementing loop slowing the code by more than 100%

标签 javascript performance loops v8 spidermonkey

我正在浏览 Eloquent JavaScript (再次)遇到练习 "Chess Board" of Chapter 2 .在我第一次阅读它的那天，我写了一个不错的解决方案版本，并在 Elequent Javascript website 提供了另一个版本的解决方案。 .我是想成为 super 高效程序员的新手之一，他们脑子里只有一个问题:“我能让它工作得更快或更小吗？无论如何？”

所以，几个月前我在网上搜索时，遇到了 a question在 Stack Overflow 上，关于 for 循环与 while 循环的性能比较。因为在该线程中提到 for 循环比 while 慢，而递减迭代器的循环更快，所以我重写了代码以获得更好的性能。

这是新版本，其中 for 替换为 while 并为递减编辑了条件:

console.time("looping");
var gridSize = 5000, str = '', i = gridSize, j;
while (i--) {
  j = gridSize;
  while (j--) {
    if ((i - j) % 2 === 0)
      str += " ";
    else
      str += "#";
  }
  str += "\n";
}

//console.log(str);
console.timeEnd("looping");

但令我惊讶的是这段代码的性能更差。然后，过了一会儿我发现 if ((i - j) % 2 === 0) 是罪魁祸首，将减号替换为加号将总执行时间减少到 ~ 750 毫秒

//Checked on NODE.js = v6.11.2
Book version of code         -->    893.76 ms
while loop with subtraction  -->    1562.43 ms
while loop with addition     -->    749.62 ms


//firefox Benchmark v54.0 (64-bit) (OS Ubuntu 16.04)
Book version of code         -->    725.10 ms
while loop with subtraction  -->    1565.29 ms
while loop with addition     -->    601.12 ms

为什么减法对总执行时间有如此巨大的影响？

编辑 01 上午 6:30(格林威治标准时间)8 月 8 日

在查看@jaromandaX 的回答后，我很确定减慢循环速度的不是减法，而是负数的模数。 我又想知道是什么让负数的模变慢了

最佳答案

这远不是一个完整的答案，需要进一步调查(或了解 V8 实现细节的人的见解)。不过，这是我的发现:

Sidenode:使用以下命令行运行 Node.JS 收集结果:

node --expose-gc --print-code --code-comments --print-opt-code --trace-hydrogen --redirect-code-traces --redirect-code-traces-to=code.asm --trace_representation --trace-deopt --trace-opt 1.js

并查看了一些 V8 源代码。

1. 性能差异来自于在这些情况下生成不同的机器代码这一事实。对于 +，% 的代码是

                  ;;; <@134,#123> add-i
00000151A32DD74B   395  03c2           addl rax,rdx
00000151A32DD74D   397  0f807a030000   jo 1293  (00000151A32DDACD)
                  ;;; <@136,#126> mod-by-power-of-2-i
00000151A32DD753   403  85c0           testl rax,rax
00000151A32DD755   405  790f           jns 422  (00000151A32DD766)
00000151A32DD757   407  f7d8           negl rax
00000151A32DD759   409  83e001         andl rax,0x1
00000151A32DD75C   412  f7d8           negl rax
00000151A32DD75E   414  0f846e030000   jz 1298  (00000151A32DDAD2)
00000151A32DD764   420  eb03           jmp 425  (00000151A32DD769)
00000151A32DD766   422  83e001         andl rax,0x1
                  ;;; <@138,#200> smi-tag
00000151A32DD769   425  8bd8           movl rbx,rax
00000151A32DD76B   427  48c1e320       REX.W shlq rbx, 32
                  ;;; <@140,#130> gap
00000151A32DD76F   431  488bc2         REX.W movq rax,rdx

而 - 的代码要复杂得多:

                  ;;; <@136,#123> sub-i
00000151A32E57E1   417  412bc3         subl rax,r11
00000151A32E57E4   420  0f8039040000   jo 1507  (00000151A32E5C23)
                  ;;; <@138,#200> int32-to-double
00000151A32E57EA   426  c5f957c0       vxorpd xmm0,xmm0,xmm0
00000151A32E57EE   430  c5fb2ac0       vcvtlsi2sd xmm0,xmm0,rax
                  ;;; <@139,#200> gap
00000151A32E57F2   434  c5f928ca       vmovapd xmm1,xmm2
                  ;;; <@140,#126> mod-d
00000151A32E57F6   438  4989e2         REX.W movq r10,rsp
00000151A32E57F9   441  4883ec28       REX.W subq rsp,0x28
00000151A32E57FD   445  4883e4f0       REX.W andq rsp,0xf0
00000151A32E5801   449  4c89542420     REX.W movq [rsp+0x20],r10
00000151A32E5806   454  48b830d4124001000000 REX.W movq rax,000000014012D430
00000151A32E5810   464  ffd0           call rax
00000151A32E5812   466  488b642420     REX.W movq rsp,[rsp+0x20]
                  ;;; <@142,#126> lazy-bailout
                  ;;; <@144,#202> number-tag-d
00000151A32E5817   471  498b9dc06f0400 REX.W movq rbx,[r13+0x46fc0]
00000151A32E581E   478  488bc3         REX.W movq rax,rbx
00000151A32E5821   481  4883c010       REX.W addq rax,0x10
00000151A32E5825   485  493b85c86f0400 REX.W cmpq rax,[r13+0x46fc8]
00000151A32E582C   492  0f878f030000   ja 1409  (00000151A32E5BC1)
00000151A32E5832   498  498985c06f0400 REX.W movq [r13+0x46fc0],rax
00000151A32E5839   505  48ffc3         REX.W incq rbx
00000151A32E583C   508  4d8b5560       REX.W movq r10,[r13+0x60]
00000151A32E5840   512  4c8953ff       REX.W movq [rbx-0x1],r10
00000151A32E5844   516  c5fb114307     vmovsd [rbx+0x7],xmm0
                  ;;; <@146,#130> gap
00000151A32E5849   521  488b45a0       REX.W movq rax,[rbp-0x60]
00000151A32E584D   525  488b7db8       REX.W movq rdi,[rbp-0x48]
00000151A32E5851   529  488b75c0       REX.W movq rsi,[rbp-0x40]
00000151A32E5855   533  488b4dc8       REX.W movq rcx,[rbp-0x38]
00000151A32E5859   537  488b55b0       REX.W movq rdx,[rbp-0x50]
00000151A32E585D   541  4c8b4da8       REX.W movq r9,[rbp-0x58]
00000151A32E5861   545  4c8b4598       REX.W movq r8,[rbp-0x68]
00000151A32E5865   549  c5fb109578ffffff vmovsd xmm2,[rbp-0x88]

简而言之，不同之处在于，对于“加号”情况，Mod (%) 操作是使用高度特化的 mod-by-power-of-2-i 执行的机器代码，但对于“减号”情况，它是使用 mod-d 完成的，它是基于浮点的算术实现。

另请注意，mod-by-power-of-2-i 机器代码确实支持负值。它可以粗略地重写成这样:

if (rax < 0) {
    rax = -rax;
    rax = rax & 1;
    rax = -rax;
}
else {
    rax = rax & 1;
}

所以这不是只针对正值优化机器代码的情况。

2. 生成代码的差异似乎是因为类型推断的工作方式不同。 --trace_representation 生成的日志显示简化程序的“加号”和“减号”情况之间的以下区别:

var f_minus = function(log) {
    var str = '', i = gridSize, j;
    while (i--) {
      j = gridSize;
      while (j--) {
        var ttt = (i - j) % 2
      }
    }

  if(log) {
     if(ttt == -1)
        console.log(t);
   }
}


var f_plus = function(log) {
    var str = '', i = gridSize, j;
    while (i--) {
      j = gridSize;
      while (j--) {
        var ttt = (i + j) % 2
      }
    }

    if(log){
     if(ttt == -1)
        console.log(t);
    }
}

比较

[marking 00000025D4303E91 <JS Function f_minus (SharedFunctionInfo 00000278933F61C1)> for optimized recompilation, reason: small function, ICs with typeinfo: 8/12 (66%), generic ICs: 0/12 (0%)]
[compiling method 00000025D4303E91 <JS Function f_minus (SharedFunctionInfo 00000278933F61C1)> using Crankshaft OSR]
#37 Phi is used by real #110 Branch as v
#38 Phi is used by real #58 Add as t
#38 Phi is used by real #69 StackCheck as v
#38 Phi is used by real #70 LoadContextSlot as v
#38 Phi is used by real #122 CompareGeneric as t
#38 Phi is used by real #132 LoadGlobalGeneric as v
#38 Phi is used by real #134 LoadNamedGeneric as v
#38 Phi is used by real #136 LoadGlobalGeneric as v
#38 Phi is used by real #141 CallWithDescriptor as v
#38 Phi is used by real #156 Return as v
#38 Phi is used by real #101 Mod as t
#38 Phi is used by real #98 Sub as t
#38 Phi is used by real #95 StackCheck as v
#38 Phi is used by real #84 Add as t
#47 Phi is used by real #56 ForceRepresentation as s
#49 Phi is used by real #122 CompareGeneric as t
#77 Phi is used by real #83 ForceRepresentation as s
generalizing use representation 'v' of #40 Phi with uses of #47 Phi 's'
generalizing use representation 'v' of #42 Phi with uses of #49 Phi 't'
generalizing use representation 't' of #42 Phi with uses of #78 Phi 'v'
generalizing use representation 'v' of #49 Phi with uses of #78 Phi 'v'
generalizing use representation 'v' of #78 Phi with uses of #49 Phi 't'
Changing #101 Mod representation v -> i based on inputs
Changing #101 Mod representation i -> d based on output
Changing #98 Sub representation v -> s based on inputs
Changing #98 Sub representation s -> i based on use requirements
Changing #84 Add representation v -> i based on inputs
...

对此

[marking 000002C17CAAB341 <JS Function f_plus (SharedFunctionInfo 00000278933F6289)> for optimized recompilation, reason: small function, ICs with typeinfo: 8/12 (66%), generic ICs: 0/12 (0%)]
[compiling method 000002C17CAAB341 <JS Function f_plus (SharedFunctionInfo 00000278933F6289)> using Crankshaft OSR]
#37 Phi is used by real #110 Branch as v
#38 Phi is used by real #58 Add as t
#38 Phi is used by real #69 StackCheck as v
#38 Phi is used by real #70 LoadContextSlot as v
#38 Phi is used by real #122 CompareGeneric as t
#38 Phi is used by real #132 LoadGlobalGeneric as v
#38 Phi is used by real #134 LoadNamedGeneric as v
#38 Phi is used by real #136 LoadGlobalGeneric as v
#38 Phi is used by real #141 CallWithDescriptor as v
#38 Phi is used by real #156 Return as v
#38 Phi is used by real #101 Mod as t
#38 Phi is used by real #98 Add as t
#38 Phi is used by real #95 StackCheck as v
#38 Phi is used by real #84 Add as t
#47 Phi is used by real #56 ForceRepresentation as s
#49 Phi is used by real #122 CompareGeneric as t
#77 Phi is used by real #83 ForceRepresentation as s
generalizing use representation 'v' of #40 Phi with uses of #47 Phi 's'
generalizing use representation 'v' of #42 Phi with uses of #49 Phi 't'
generalizing use representation 't' of #42 Phi with uses of #78 Phi 'v'
generalizing use representation 'v' of #49 Phi with uses of #78 Phi 'v'
generalizing use representation 'v' of #78 Phi with uses of #49 Phi 't'
Changing #101 Mod representation v -> i based on inputs
Changing #98 Add representation v -> s based on inputs
Changing #98 Add representation s -> i based on use requirements
Changing #84 Add representation v -> i based on inputs
...

有趣的区别在于线条

Changing #101 Mod representation i -> d based on output

这只存在于 f_minus 而不是 f_plus 的情况。出于某种原因，编译器认为在 f_minus 情况下，类型应该是 Double 而不是 Integer，基于输出值的猜测。有趣的是，如果我换行

        var ttt = (i - j) % 2

到

        var ttt = (i - j + gridSize) % 2;

它再次开始生成快速 mod-by-power-of-2-i 代码。所以是的，输出值很可能会影响优化编译器。但目前尚不清楚为什么在这种特殊情况下会发生这种情况。

乍一看，这种行为看起来像是优化编译器中的一个错误，它没有注意到“减号”情况可以由 mod-by-power-of-2-i 处理为出色地。我无法追踪为什么会发生这种情况，只是浏览了源代码，所以欢迎进一步输入。

关于JavaScript 性能 : Modulus operation of negative Number within decrementing loop slowing the code by more than 100%，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45559380/

上一篇：javascript - Javascript 引用计数中的循环引用

下一篇：javascript - window.pageYOffset 与 IE11 上的 window.scrollY

相关文章：

java - Axis2 getSOAPEnvelope() 性能问题

java - 用按钮停止计时器

arrays - 在 Ruby 语言中的一个 if 语句中使用多个条件

javascript - 如何通过js或者批处理文件在IE中自动启用 "initialize and script activex controls not marked as safe for scripting(ActiveXObject)"

javascript - 使用 JavaScript 打开模式对话框 onClick 不起作用

javascript - 用ajax替换div内容

javascript - Javascript 对象实例化大小和方法的性能差异很大

java - 从映射表中获取一个查询中的数据

python - Pandas:迭代并插入具有组内条件的列复杂问题

javascript - 无法将两个 api 调用链接到 mongo 数据库

©2024 IT工具网  联系我们