降序循环总是比升序循环快？

刚才看到有人在论坛Java版的一帖里提到：

wujiazhao88 写道

如果有两层以上的循环，要将多次计算的循环放在里面，少的放在外面；
另外for(int i=n;i>0;i--)的效率比for(int i=0;i<n;i++)的效率高

Well...关于循环顺序的问题，这个笼统的说降序循环比升序循环效率高恐怕还是比较有误导性的，因为不是所有环境下都如此。

在许多体系结构上，整数的算术运算会设置条件码，诸如“是否有算术溢出”、“是否大于零”、“是否小于零”、“是否为零”，之类的。
例如在x86上，inc指令会更新OF、SF、ZF、AF、PF标志位，并保留CF标志位的值；add指令则会更新OF、SF、ZF、AF、CF、PF标志位。其中，
OF: overflow，算术溢出标志位；0为无溢出，1为有溢出
SF: sign flag，符号标志位；0为正或零，1为负
ZF: zero flag，零标志位；0为非零值，1为零
AF: adjust flag，调整标志位；这个主要用于BCD算术，一般的补码运算不会用到它
CF: carry flag，进位标志位；0为无进位，1为有进位
PF: parity flag，奇偶校验标志位；只检查结果的最低有效字节中二进制位为1的个数的奇偶性，0为个数是奇数，1为个数是偶数

要比较两个数的大小，并根据条件进行跳转，在x86上要怎么做呢？一般是用cmp指令与带调教的jmp指令组合使用。cmp其实就是普通减法，只不过它不保存减的结果，只用于设置标志位；跟add一样，它也会更新OF、SF、ZF、AF、CF、PF标志位。带条件的jmp会根据相应的标志位为0或1决定是跳转到指定的目标还是继续执行下一条指令。
举例如下：
（NASM语法）

cmp eax, ecx
jl  LABEL

（jl是jump if less）
就是：

if (eax < ecx) {
    goto LABEL;
}

// ...

LABEL:
  // ...

但如果是要跟0比较大小，就有机会不用cmp，而是直接靠之前的整数运算设置的标志位来控制跳转。本来降序循环的优势就是基于这一点：由于循环条件是与0比较的，编译器在优化的时候就可以少生成一条cmp指令。
升序循环可能是这样的：

for (int i = 0; i < N; i++) {
    // ...
}

      xor ecx, ecx  ; 循环变量清零
LOOP:               ; ...循环体内容
      inc ecx       ; 循环变量自增
      cmp ecx, N    ; 循环条件
      jl  LOOP      ; 小于的时候继续循环
NEXT:
; ...循环之后别的代码

在执行了inc后，它设置的标志位全部都没能用上，被cmp全部冲掉了之后才决定是否跳转。

降序循环可能是这样的：

for (int i = (N - 1); i >= 0; i--) {
    // ...
}

      mov ecx, N    ; 循环变量初始化到N-1
      dec ecx
LOOP:               ; ...循环体内容
      dec ecx       ; 循环变量自减，同时也设置了标志位，构成循环条件
      jge LOOP      ; 大于等于的时候继续循环
NEXT:
; ...循环之后别的代码

dec在完成自减的同时也设置了标志位，紧接着带条件的jmp就用上了标志位。这样就比升序循环少一条指令。爽不？

问题是我们手写汇编的话很容易控制运行时准确的行为，但首先程序有可能是被解释执行的，其次编译器也未必一定会做这种优化。


于是上微型测试来看看。实验环境是Sun的JDK 1.6.0 update 14 server VM，Windows XP SP3 32位，Core 2 Duo。
代码如下：

public class Test {
    private static void foo(int[] src, int[] dest) {
        for (int i = 0; i < src.length; i++) {
            dest[i] = src[i];
        }
    }
    
    private static void bar(int[] src, int[] dest) {
        for (int i = src.length - 1; i >= 0; i--) {
            dest[i] = src[i];
        }
    }
    
    public static void main(String[] args) {
        int[] dummy = new int[10000];
        
        for (int i = 0; i < 3000; i++) {
            foo(dummy, dummy);
        }
        
        for (int i = 0; i < 3000; i++) {
            bar(dummy, dummy);
        }
    }
}

没有在代码里测时间，在main()里循环调用foo()和bar()只是为了激发它们被HotSpot编译而已。

先看上面的Java源码被javac编译为字节码之后的样子：
foo()

0:   iconst_0
1:   istore_2
2:   iload_2
3:   aload_0
4:   arraylength
5:   if_icmpge    20
8:   aload_1
9:   iload_2
10:  aload_0
11:  iload_2
12:  iaload
13:  iastore
14:  iinc    2, 1
17:  goto    2
20:  return

bar()

0:   aload_0
1:   arraylength
2:   iconst_1
3:   isub
4:   istore_2
5:   iload_2
6:   iflt    21
9:   aload_1
10:  iload_2
11:  aload_0
12:  iload_2
13:  iaload
14:  iastore
15:  iinc    2, -1
18:  goto    5
21:  return

JVM在概念上并没有条件码，而是用if-*指令根据当前求值栈顶的两个值（或者栈顶值与0）的关系）决定是否跳转。从字节码上看，升序循环与降序循环没有多少差异。上面的例子中，foo()中的if_icmpge指令是把栈顶两个值弹出来做比较，而bar()中的iflt指令是把栈顶的一个值与弹出来与0比较，与前面提到的省一条cmp指令的优化有异曲同工之妙。

这里foo()与bar()比较显著的不同来自是：前者每轮循环都要执行arraylength指令用于获取数组长度，而后者只在循环开头处要执行一次arraylength指令。这只是因为javac基本上不做优化而已。如果手动把foo()中数组length提取到循环外，如下

private static void foo(int[] src, int[] dest) {
    int length = src.length;
    for (int i = 0; i < length; i++) {
        dest[i] = src[i];
    }
}

那对应的字节码就变成：

0:  aload_0
1:  arraylength
2:  istore_2
3:  iconst_0
4:  istore_3
5:  iload_3
6:  iload_2
7:  if_icmpge  22
10: aload_1
11: iload_3
12: aload_0
13: iload_3
14: iaload
15: iastore
16: iinc  3, 1
19: goto  5
22: return

这样就与bar()的字节码更加相似了，arraylength指令不在循环体内出现。这个版本的foo()与bar()在解释模式上执行的性能特征没有区别。

如果foo()与bar()被以解释模式执行，而解释器又不做什么优化的话，字节码形式的代码倒也能反映出运行时的性能特点。但像HotSpot这样的动态编译器会选择最耗时间的代码（也就是“热点”）进行编译，实际上代码是被编译到native code来执行的。
那么HotSpot的server VM中的编译器分别把foo()与bar()编译成了怎样的native code呢？下面把两者的循环体部分的代码贴出来：（AT&T语法）
foo()

0x00becc80: movq   0xc(%ecx,%edi,4),%xmm0
0x00becc86: movq   %xmm0,0xc(%edx,%edi,4)
0x00becc8c: movq   0x14(%ecx,%edi,4),%xmm0
0x00becc92: movq   %xmm0,0x14(%edx,%edi,4)
0x00becc98: movq   0x1c(%ecx,%edi,4),%xmm0
0x00becc9e: movq   %xmm0,0x1c(%edx,%edi,4)
0x00becca4: movq   0x24(%ecx,%edi,4),%xmm0
0x00beccaa: movq   %xmm0,0x24(%edx,%edi,4)
0x00beccb0: movq   0x2c(%ecx,%edi,4),%xmm0
0x00beccb6: movq   %xmm0,0x2c(%edx,%edi,4)
0x00beccbc: movq   0x34(%ecx,%edi,4),%xmm0
0x00beccc2: movq   %xmm0,0x34(%edx,%edi,4)
0x00beccc8: movq   0x3c(%ecx,%edi,4),%xmm0
0x00beccce: movq   %xmm0,0x3c(%edx,%edi,4)
0x00beccd4: movq   0x44(%ecx,%edi,4),%xmm0
0x00beccda: movq   %xmm0,0x44(%edx,%edi,4)
0x00becce0: add    $0x10,%edi
0x00becce3: cmp    %ebp,%edi
0x00becce5: jl     0x00becc80

bar()

0x00bed1b0: lea    (%edx,%esi,4),%ebp
0x00bed1b3: mov    0x4(%esp),%ebx
0x00bed1b7: lea    (%ebx,%esi,4),%ebx
0x00bed1ba: movq   0x8(%ebx),%xmm0
0x00bed1bf: movq   %xmm0,0x8(%ebp)
0x00bed1c4: movq   (%ebx),%xmm0
0x00bed1c8: movq   %xmm0,0x0(%ebp)
0x00bed1cd: movq   -0x8(%ebx),%xmm0
0x00bed1d2: movq   %xmm0,-0x8(%ebp)
0x00bed1d7: movq   -0x10(%ebx),%xmm0
0x00bed1dc: movq   %xmm0,-0x10(%ebp)
0x00bed1e1: movq   -0x18(%ebx),%xmm0
0x00bed1e6: movq   %xmm0,-0x18(%ebp)
0x00bed1eb: movq   -0x20(%ebx),%xmm0
0x00bed1f0: movq   %xmm0,-0x20(%ebp)
0x00bed1f5: movq   -0x28(%ebx),%xmm0
0x00bed1fa: movq   %xmm0,-0x28(%ebp)
0x00bed1ff: movq   -0x30(%ebx),%xmm0
0x00bed204: movq   %xmm0,-0x30(%ebp)
0x00bed209: add    $0xfffffff0,%esi
0x00bed20c: cmp    %ecx,%esi
0x00bed20e: jg     0x00bed1b0

看起来黑压压的……是什么来的？
mov是x86上移动数据用的指令，q是AT&T语法中表示数据宽度为QWORD（64位整型）指令后缀。循环体中连续的出现一大堆movq可以这样看：

movq   0xc(%ecx,%edi,4),%xmm0
movq   %xmm0,0xc(%edx,%edi,4)

这样的一组指令先把源数组里连续的64位数据移动到一个寄存器（%xmm0）上，然后再把数据从寄存器移到目标数组里。要分两条是因为x86的数据移动指令接受源与目标两个参数，但其中只能有一个是内存参数。

Java里int不是32位的么？为什么要移动64位呢？而且原本代码里每轮循环只复制了一个int，为什么编译出来之后循环体里有那么多组movq？
这就是编译器的一种常见优化技巧，“循环展开”（loop unrolling）的体现。通过提高每轮循环做的工作量，循环次数就可以显著减少，相应的就可以降低循环带来的开销。这个例子中foo()与bar()的循环体都被优化展开，然后通过“superword”优化重新组合成向量化的、更大数据宽度的操作，每轮循环复制8个QWORD也就是16个int。

将两个int复制合并为一个64位复制操作的优化由以下参数控制：

product(bool, UseSuperWord, true, "Transform scalar operations into superword operations")

循环展开的优化则由以下一些参数控制：

product_pd(intx,  LoopUnrollLimit, "Unroll loop bodies with node count less than this")
product(intx,  LoopUnrollMin, 4, "Minimum number of unroll loop bodies before checking progress of rounds of unroll,optimize,..")

但……在本文前半部分提到降序循环可以减少一个cmp指令的优化，HotSpot却没有做。在bar()里还是可以看到做了减法（add 0xFFFFFFF0就是减去16）还是有cmp指令；当然咯，这里实际不是固定与0在做比较。每轮循环都复制16个int，那如果数组长度不是16的倍数怎么办呢？头尾多出来的部分就得用别的代码来处理了。因此这个主循环结束时，%esi可能还没到0，就无法消除cmp指令。

在经过的间接层越多的语言实现中，我们就越难把握实际运行时执行的代码的状况。也正是因为如此，一些在底层语言（例如C）里有效的优化技巧在较高级的语言中（例如Java）中就未必适用。使用错误的抽象层次去思考优化技巧是比较危险的……还是优先考虑代码的整洁性、可阅读性来得实在些。

===========================================================================

有趣的是，HotSpot server VM给foo()编译出来的代码与bar()的应用的优化取舍有点不同。可以看到foo()中每条movq指令的内存参数都是“基地址+放大倍数×偏移量”的方式计算地址的，而bar()中则是在循环体的开头处先用“基地址+放大倍数×偏移量”的方式算出了一个中间结果，后面就直接用“基地址+偏移量”的方式计算地址。看起来应该是后者更高效些。不过嘛……这里差得不会太多就是了。而且这个差异跟升序/降序没有直接关系，纯粹是HotSpot有RPWT，居然一个有CSE的效果另一个没有……所以单独开一段放在结尾提一提就算了 orz

===========================================================================

另一个题外话：Array Bounds Check Elimination in the CLR
在这篇文章里，Dave Detlefs讲解了当时CLR在做数组边界检查削除优化的一些场景和限制。当时CLR的JIT编译器在升序的计数循环里能削除数组边界检查，而在降序循环里就没做削除。这会使得降序循环里访问数组元素比较慢。
像这种由编译器实现而造成升序/降序循环速度差异的例子并不是仅此一家。靠拍脑袋去猜测然后说某种形式的代码一定快于另一种形式的代码，自然是不靠谱的。

Have fun ^_^

评论

9 楼 RednaxelaFX 2009-12-11  

andyu2008 写道

本人严重不支持两层循环，第二层循环完全可以使用Map代替！

这个……跟本文有什么关系么？
这帖里main的循环只是为了引发foo()与bar()被HotSpot执行的被编译为本地代码而已。真正的测试对象是foo()与bar()中的单层循环。

8 楼 mooninday 2009-12-11  

LZ很强大, 我没领会要领

7 楼 andyu2008 2009-12-11  

本人严重不支持两层循环，第二层循环完全可以使用Map代替！

6 楼 wujiazhao88 2009-12-10  

呵呵，说得好，还是楼主理解深刻，我危言耸听了。。 

5 楼 RednaxelaFX 2009-12-10  

其实这篇就是杂技4的1/3内容的缩减版……之前有些人看过草稿了，不过还是太零碎，组织好之前都不太想发…… =_=|||

seen 写道

如果能深入一点就更好 比如说说循环中localization对性能的影响 以及L1/L2 cache对性能的影响

杂记1提到过locality。这篇是看到了论坛的讨论实在忍不住就写了点针对性的……好吧事实是再深入下去我就漏底了 XDD

4 楼 幸存者 2009-12-10  

刚才找了下，那篇杂记1：缓存，局部性，循环太监了，说起来楼主太监的系列不少。印象中某篇“杂记3”因为不满楼主的行为从草稿箱里跳了出来。

3 楼 幸存者 2009-12-10  

我记得楼主以前发过一篇关于locality的文章。

2 楼 seen 2009-12-10  

能把一个老话题说的这么生动还是蛮有能力的
如果能深入一点就更好 比如说说循环中localization对性能的影响 以及L1/L2 cache对性能的影响

1 楼 幸存者 2009-12-10  

原来HotSpot还有这样的优化技巧。
文中只贴了循环体内的汇编码，我想知道HotSpot操作数组的时候作不作边界检查，或者在循环体外检查的？如果不作的话，是不是可以干点坏事呢，呵呵。