一个简单循环的优化问题 (2007-09-20)

Alright,终于开始用JavaEye的空间,顺便把之前写的别的东西转过来吧~~

==============转载开始==============
(2007-09-20)

昨晚回到宿舍之后,有同学问了我一个简单循环的优化问题.问题是,为何编译器要进行下述优化:

将优化前的代码:

for (int i = 0; i < 100; i++)
    for (int j = 0; j < 20; j++)
        a[j] = a[j] + 1;

优化为:

for (int j = 0; j < 20; j++)
    for (int i = 0; i < 100; i++)
        a[j] = a[j] + 1;

这让我一下疑惑了.我平时留意的循环相关优化主要是运算强度减弱(如乘法转换为加减法),不变量外提,短循环展开等.但这次的问题却跟前面三种情况都没什么关系.想了好一会才突然醒悟过来,原来是内存访问的问题.
可以观察到,优化前的代码里,外层循环里的所有语句都在内层循环里,而且外层循环控制变量i没有参与最内层循环体的运算,这为优化提供了可能性,意味着可以调换内外循环的顺序而不影响执行结果.

让我们来看看优化前的代码大概是被如何执行的(伪代码):

  lea reg0, a ; reg0 ← a
  and reg1, 0 ; reg1 ← i

outer_loop:
  cmp reg1, 100.
  jge end_outer_loop
  and reg2, 0 ; reg2 ← j
inner_loop:
  cmp reg2, 20.
  jge end_inner_loop
  mov reg3, reg0[reg2] ; //关键语句1_1
  incr reg3
  mov reg0[reg2], reg3 ; //关键语句1_2
  incr reg2
  jmp inner_loop
end_inner_loop:
  incr reg1
  jmp outer_loop

end_outer_loop:
  ...

而优化后的代码大概是这样(伪代码,实际上可以优化得更彻底):

  lea reg0, a ; reg0 ← a
  and reg2, 0 ; reg2 ← j

outer_loop:
  cmp reg2, 20.
  jge end_outer_loop
  and reg1, 0 ; reg1 ← i
  mov reg3, reg0[reg2] ; //关键语句2_1
inner_loop:
  cmp reg1, 100.
  jge end_inner_loop
  incr reg3
  incr reg1
  jmp inner_loop
end_inner_loop:
  mov reg0[reg2], reg3 ; //关键语句2_2
  incr reg2
  jmp outer_loop

end_outer_loop:
  ...

可以看到优化前后的代码长度几乎是一样的.也就是说这个优化跟减小目标代码的大小没有关系.最大的区别在于内存访问的语句的位置与内/外层循环体的位置关系.优化前,内层循环体每次执行都要进行两次内存访问,循环中需要进行的内存访问次数约为100 * 20 * 2 = 4000次.而优化后,内存访问被外提到了外层循环中,内层循环里不再需要访问内存,所以循环中需要进行的内存访问次数约为20 * 2 = 40次.
由于内存访问远远慢于寄存器访问,即使根据局部性(locality)原则a数组的内容都预先读到了高速cache中还是要比直接只使用寄存器要慢.所以综合各种条件后尽量减少内存的访问次数是优化的一个方向.而这个题目就展示了这一点.

为什么没一眼就看出来呢...我真是的.明明在debug的时候见得那么多的东西了...

=============续篇=============
(2007-09-24)

让我们来看看what's in the real world.下面两幅图分别是一个C++代码片段和对应的编译后结果的对照图.可以看到,前文中"优化后"代码对应的汇编在功能和顺序上跟我预期的没多少差别,只是具体指令用得不一样...嘛,寄存器清零确实xor用得最多.另外,两个版本在实际循环前都有一大段mov指令,这些就是a[20]的初始化语句所展开得到的.真正需要关心的地方从地址0x00401068开始.这循环次数实在太少,即使高精度记时器也未必能满足比较这两份代码消耗时间的需求,所以我们还是用观察法来分析两段代码的区别.





前一版本的代码("未优化版")的反汇编结果中我们可以看到,内层循环体里第一句是一个add指令.这对应于a[j] += 1;,这句指令实际上做了从内存取值,运算,将结果保存回内存这几步,也就是说内存访问次数大致可以认为有两次.综合来说,这个双层循环中内存的访问次数大约是100 * 20 * 2 = 4000次,与前面分析的一样.
后一版本的代码("优化版")的反汇编结果与前文的分析基本吻合,就不重复了.双层循环中内存的访问次树大致是20 * 2 = 40次.

很好,既然两次的编译结果都跟前面分析得差不多,那还有什么问题呢? 问题就是这优化是"我"而不是"编译器"做的.也就是说出这道问题的人光顾着理论研究而没管现实世界中的状况;也可能是没把想表达的意思说清楚;也有可能是转述的人记错了题目.Anyway,清华研究生入学考试考这种题也有够无聊的.这题实际想考的或许是与内存相关,不过也很可能只是下面提到的优化建议.

---------------------------------------------------------------------

Code Complete, 2nd Edition里,Chapter 26, 26.2 Loops一节提到了手工优化循环代码的一些建议,其中与本题相关的是:
Putting the Busiest Loop on the Inside

When you have nested loops, think about which loop you want on the outside and which you want on the inside. Following is an example of a nested loop that can be improved:

Java Example of a Nested Loop That Can Be Improved

for ( column = 0; column < 100; column++ ) {
    for ( row = 0; row < 5; row++ ) {
        sum = sum + table[ row ][ column ];
    }
}

The key to improving the loop is that the outer loop executes much more often than the inner loop. Each time the loop executes, it has to initialize the loop index, increment it on each pass through the loop, and check it after each pass. The total number of loop executions is 100 for the outer loop and 100 * 5 = 500 for the inner loop, for a total of 600 iterations. By merely switching the inner and outer loops, you can change the total number of iterations to 5 for the outer loop and 5 * 100 = 500 for the inner loop, for a total of 505 iterations. Analytically, you'd expect to save about (600 - 505) / 600 = 16 percent by switching the loops. Here's the measured difference in performance:

Language / Straight Time / Code-Tuned Time / Time Savings
C++ 4.75 / 3.19 / 33%
Java 5.39 / 3.56 / 34%
PHP 4.16 / 3.65 / 12%
Python 3.48 / 3.33 / 4%

The results vary significantly, which shows once again that you have to measure the effect in your particular environment before you can be sure your optimization will help.

---------------------------------------------------------------------

所以问题的关键是什么? 我觉得是"See it for yourself."