倒序循环真的更快吗?

295

我听过这个问题很多次。JavaScript 循环倒序计数真的更快吗?如果是这样,为什么呢?我看到一些测试套件示例显示反向循环更快,但我找不到任何解释为什么!

我猜这是因为循环不再需要每次评估一个属性来检查它是否完成,而只需针对最终数字值进行检查。

即:

for (var i = count - 1; i >= 0; i--)
{
  // count is only evaluated once and then the comparison is always on 0.
}

6
嘿嘿,那需要无限时间。试试i--。 - StampedeXV
6
倒序的 for 循环更快,因为上界(嘿嘿,下界)循环控制变量不需要被定义或从对象中获取;它是一个常数零。 - Josh Stodola
92
没有真正的区别。本地循环结构始终非常快。不必担心它们的性能。请放心使用。 - James Allardice
25
针对这类问题,请_展示_你所参考的文章。 - Lightness Races in Orbit
23
非常低端的和使用电池供电的设备存在重要的区别。这个区别在于,使用 i-- 时,将i与0进行比较以确定循环结束,而使用 i++ 时,将i与大于0的数字进行比较。我相信性能差异大约为20纳秒(类似于 cmp ax,0 vs. cmp ax,bx)- 如果你每秒循环数千次,那为什么不让每次循环多获得20纳秒的收益呢 :) - luben
显示剩余22条评论
34个回答

12

它取决于数组在内存中的位置以及访问该数组时内存页面的命中率。

在某些情况下,按列顺序访问数组成员比按行顺序更快,因为会增加命中率。


1
如果只有楼主问了为什么以不同顺序遍历相同的矩阵会花费不同的时间就好了。 - dcow
1
考虑到操作系统的内存管理是基于分页的,当一个进程需要的数据不在缓存页面中时,在操作系统中会发生页面错误,它必须将目标页面带到CPU缓存中并替换另一个页面,因此会导致处理中的开销比目标页面在CPU缓存中时花费更多的时间。假设我们定义了一个大数组,其中每行的大小都大于页面OS大小,并且我们按行顺序访问它,在这种情况下,页面错误率增加,结果比按列顺序访问该数组要慢。 - Akbar Bayati
页面错误并不等同于缓存未命中。只有在内存被分页到磁盘上时才会出现页面错误。按照存储在内存中的顺序顺序访问多维数组更快,因为它具有缓存局部性(在获取时使用缓存行的所有字节),而不是因为页面错误。(除非您的工作集对您正在使用的计算机来说太大了。) - Peter Cordes

10
上次我关注到它是在写6502汇编(8位,yeah!)时。最大的优势是大多数算术操作(特别是递减)会更新一组标志位之一为Z,表示“达到零”。因此,在循环结束时,您只需要执行两个指令:DEC(递减)和JNZ(如果不为零则跳转),无需比较!

在JavaScript中,显然不适用(因为它运行在没有这些操作码的CPU上)。最有可能的原因是使用i--而不是i++可以避免在循环作用域中引入额外的控制变量。请参见下面的答案... - Pavel P
1
没错,它确实不适用;但这是一种非常常见的C风格,对于那些习惯了它的人来说,它看起来更加清晰。 :-) - Javier
x86和ARM在这方面都像6502。对于x86情况,使用dec/jnz而不是inc/cmp/jne。你不会看到空循环运行得更快(两者都会饱和分支吞吐量),但是倒数计数略微减少了循环开销。当前的英特尔硬件预取器也不会受到以降序访问内存的模式的影响。旧的CPU可以追踪4个向后流和6或10个向前流,如果我没记错的话。 - Peter Cordes

8

你现在的做法并不更快(除非你是想写一个无限循环,我猜你应该是想写 i--)。

如果你想让它更快,可以这样做:

for (i = 10; i--;) {
    //super fast loop
}

当然,在这样一个小的循环中你可能不会注意到它。之所以更快是因为在检查i是否“为真”(当它达到0时,它将计算为“假”)时,你会递减i。

1
你是不是漏了一个分号?(i = 10; i--;) - searlea
是的,我已经修复了这个错误。如果我们要挑剔,我会指出你在i后面忘记了分号--!嘿。 - djdd87
为什么会更快呢?代码短并不意味着它会更快。你有进行过测试吗? - Greg Hewgill
4
是的,我已经测量过了。我并不是说源代码变短就一定更快,而是操作次数少才会更快。 - peirix
这里有一个演示差异的基准测试 - https://jsbench.me/1cknepoalw/1 - mindplay.dk

7
我做了一个 jsbench上的比较
正如alestani所指出的,升序循环中需要花费时间的一件事是,在每次迭代中计算数组的大小。在这个循环中:
for ( var i = 1; i <= array.length; i++ )

每次增加 i 时,你都会评估 .length。在这个例子中:

for ( var i = 1, l = array.length; i <= l; i++ )

当你声明 i 时,只会计算一次 .length。而在这个例子中:

for ( var i = array.length; i--; )

比较是隐式的,在递减i之前发生,代码非常易读。然而,让循环变得更加出色的是你在循环中放置的内容。

带有对函数的调用的循环(在其他地方定义):

for (i = values.length; i-- ;) {
  add( values[i] );
}

嵌入代码的循环:

var sum = 0;
for ( i = values.length; i-- ;) {
  sum += values[i];
}

如果您可以内联代码而不损失可读性,而不是调用函数,那么您可以使循环快上一个数量级!
注意:由于浏览器越来越善于内联简单函数,这真的取决于您的代码有多复杂。因此,在优化之前进行分析,因为
1. 瓶颈可能在其他地方(ajax、回流等) 2. 您可以选择更好的算法 3. 您可以选择更好的数据结构
但请记住:
代码是写给人们阅读的,机器只是偶然执行的。

为这个答案和基准测试点赞。我添加了forEach测试,并将基准测试重构为可在浏览器和Node中运行的独立文件。https://jsfiddle.net/hta69may/2/。对于Node,“反向循环,隐式比较,内联代码”是最快的。但在FF 50中进行测试时,结果很奇怪:不仅计时几乎少了10倍(!),而且“forEach”测试的速度与“反向循环”一样快。也许Node的开发者应该使用Mozilla的JS引擎而不是V8? :) - Fr0sT

7

这可以通过JavaScript(和所有语言)最终转换为操作码以在CPU上运行来解释。CPU始终有一个用于与零进行比较的单个指令,速度非常快。

另外,如果您可以保证count始终>= 0,则可以简化为:

for (var i = count; i--;)
{
  // whatever
}

1
较短的源代码并不一定意味着它会更快。你有进行过测量吗? - Greg Hewgill
哎呀,我错过了这个。你说得一点也没错,老兄。 - Robert
1
我想看一下汇编源代码,其中与0进行比较是不同的。虽然已经过了几年,但曾经我做了大量的汇编编码,我无论如何也想不出一种方法来进行针对0的比较/测试,以便对于任何其他整数同样快速。然而,你所说的确实是正确的。我很沮丧,因为我无法弄清楚原因! - Brian Knoblauch
7
如果你使用类似于“dec eax”(x86指令)的指令,那么该指令会自动设置Z(零)标志,你可以立即进行测试,而不必在中间使用另一个比较指令。 - Greg Hewgill
1
当解释JavaScript时,我怀疑操作码不会成为瓶颈。更可能的是,较少的标记意味着解释器可以更快地处理源代码。 - Todd Owen
显示剩余4条评论

7

for(var i = array.length; i--; )的速度并没有太大提升。但是,当你将array.length替换成super_puper_function()时,速度可能会显著提高(因为它在每次迭代中都被调用)。这就是区别所在。

如果您要在2014年更改它,您不需要考虑优化。如果您要使用“搜索和替换”更改它,则不需要考虑优化。如果您没有时间,您不需要考虑优化。但是现在,您有时间考虑它。

P.S.:i--i++慢。


7
简单来说:在JavaScript中执行这个操作没有任何区别。 首先,您可以自行测试: 不仅可以测试和运行任何JavaScript库中的任何脚本,还可以访问以前编写的所有脚本,并查看不同浏览器在不同平台上的执行时间差异。
因此,您可以看到,在任何环境中,性能都没有区别。
如果要改善脚本的性能,可以尝试以下方法:
  1. 在循环中加入var a = array.length;语句,这样你就不需要每次在循环中计算它的值
  2. 进行循环展开http://en.wikipedia.org/wiki/Loop_unwinding

但是你必须明白,你能获得的改进非常微不足道,大多数情况下你甚至不需要在意。

我个人认为为什么会出现这种错误观念(Dec vs Inc)

很久很久以前,有一种常见的机器指令,DSZ(递减并跳过零)。使用汇编语言编程的人们使用这个指令来实现循环以节省寄存器。现在这些古老的事实已经过时了,我非常确定你不会在任何语言中使用这个伪装的改进来提高性能。

我认为这种知识能够在我们这个时代传播的唯一方式是当你阅读别人的代码时。看到这样的结构并询问为什么要这样实现,答案是: "它可以与零进行比较,从而提高性能"。你惊讶于同事的高超知识,并想利用它变得更聪明 :-)


有趣的是,在您在Win7上使用Firefox 16.0.2运行测试时,递减循环要慢29%...编辑:请忽略上述内容。重复测试结果不确定,后续运行的测试结果中存在令人惊讶的噪音量。我不太确定为什么会这样。 - user462356
是的,我尝试通过关闭其他所有内容并仅运行测试来解决这个问题。但仍然得到了奇怪的结果。非常奇怪。 - user462356
我认为你错过了JavaScript中为什么将循环次数归零被认为是更好的真正要点。这主要是因为这种方式只有一个变量控制循环执行,例如这样优化器/JITer有更多的改进空间。使用array.length并不一定会产生性能损失,因为JS虚拟机足够聪明,可以找出数组是否被循环体修改。请参见下面的答案。 - Pavel P
1
吹毛求疵:这个古老的事实(汇编语言优化)并不过时,只是晦涩难懂。就像你不需要知道除非你真的需要。 :-) - Javier

6

这不取决于--++符号,而是取决于您在循环中应用的条件。

例如:如果变量具有静态值,则循环速度较快,而如果循环每次都检查条件(如数组长度或其他条件),则速度较慢。

但是不要担心这种优化,因为这次其效果只能以纳秒来衡量。


多个纳秒循环可能会变成秒... 当你有时间时进行优化从来不是一个坏主意。 - Buksy

5

++--在JavaScript中并不重要,因为JavaScript是一种解释性语言,而不是编译性语言。每个指令都会被翻译成多个机器语言,你不需要关心这些细节。

那些谈论使用--(或++)来有效利用汇编指令的人是错误的。这些指令适用于整数算术,而在JavaScript中没有整数,只有数字(链接到相关信息)

你应该编写易读的代码。


4
有时,我们对代码编写方式进行微小的更改可能会显著提高代码的运行速度。其中一个区域是在处理数组的for循环中。如果该数组是页面元素(例如单选按钮),那么更改将产生最大的影响,但即使该数组是JavaScript代码内部的,应用此更改仍然值得。
传统的处理数组的for循环方式如下:
for (var i = 0; i < myArray.length; i++) {...

这种方法的问题在于,使用myArray.length计算数组长度需要时间,而我们编写的循环方式意味着每次循环都必须执行此计算。如果数组包含1000个元素,则将计算数组长度1001次。如果我们正在查看单选按钮并且有myForm.myButtons.length,则评估长度需要更长的时间,因为必须首先定位指定表单内的适当按钮组,然后才能在每次循环中评估长度。
显然,在处理数组时我们不希望数组长度发生改变,因此所有这些重新计算长度只会增加处理时间。(当然,如果您在循环内部添加或删除数组条目的代码,则数组大小可以在迭代之间更改,因此我们无法更改测试它的代码)
对于固定大小的循环,我们可以在循环开始时仅评估一次长度,并将其保存在变量中。然后我们可以测试该变量以决定何时终止循环。与每次计算数组长度相比,这样做要快得多,特别是当数组包含超过几个条目或是网页的一部分时。
实现此方法的代码如下:
for (var i = 0, var j = myArray.length; i < j; i++) {...

现在我们只评估数组的大小一次,并在每次循环中将我们的计数器与保存该值的变量进行比较。这个额外的变量可以比评估数组大小更快地访问,因此我们的代码将比以前运行得更快。我们只需要在脚本中添加一个额外的变量。
通常情况下,只要处理数组中的所有条目,处理数组的顺序并不重要。在这种情况下,我们可以通过按相反的顺序处理数组来稍微加快我们的代码,从而省去刚刚添加的额外变量。
最有效处理我们的数组的最终代码如下:
for (var i = myArray.length-1; i > -1; i--) {...

这段代码仍然只在开始时计算了数组的大小,但是我们现在将循环计数器与一个常量进行比较,而不是与变量进行比较。由于常量比变量更有效地访问,并且我们比之前少使用了一条语句,因此我们的第三个版本的代码现在比第二个版本稍微更高效,并且比第一个版本大大更高效。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接