请教一个for嵌套循环的优化问题。(已解决)

落叶黄

1. 
   
2. for(int i=0;i<1000;i++){
   
3.      for(int j=0;j<100;j++){
   
4.           for(int k=0;k<10;k++){
   
5.                 function(i,j,k);
   
6.            }
   
7.       }
   
8. }
   

复制代码

请问该怎么优化，简述理由。

lenovo

循环次数越少的放到最外层，以此类推。
利用cpu的流水线功能。

落叶黄

循环次数越少的放到最外层，以此类推。
利用cpu的流水线功能。
lenovo 发表于 2010-06-14 11:24

    谢谢，明白了.

ah13k

回复 2# lenovo


    我知道在数组访问的时候像你说 的那么做可以较大的提高速度，因为利用了cache。
但是对于函数执行，我不大明白为什么将小的循环放到外面可以提高效率。希望前辈能示下^^

pagx

最小循环的放最外边这个做法有时候得到相反的效果。这种优化还是交给机器弄。把代码写的容易明白就行了。

ah13k

回复 2# lenovo



我做了下测试，过程如下：
代码：

1. 
   
2. #define L1 200
   
3. #define L2 600
   
4. #define L3 1000
   
5. 
   
6. int func(int a, int b, int c)
   
7. {
   
8.     return a + b + c;
   
9. }
   
10. 
    
11. int main(int argc, char** argv, char** env)
    
12. {
    
13.     for(int i=0; i<L1; i++)
    
14.         for(int j=0; j<L2; j++)
    
15.             for(int k=0; k<L3; k++)
    
16.                 func(i, j, k);
    
17.    
    
18.     return 0;
    
19. }
    

复制代码

编译参数：
     gcc -std=c99 -O0 test.c
耗时（两次结果）：

1. 
   
2. real        0m0.687s
   
3. user        0m0.684s
   
4. sys        0m0.004s
   

复制代码

1. 
   
2. real        0m0.657s
   
3. user        0m0.652s
   
4. sys        0m0.000s
   

复制代码

另外一个版本：

1. 
   
2. #define L1 1000
   
3. #define L2 600
   
4. #define L3 200
   
5. 
   
6. int func(int a, int b, int c)
   
7. {
   
8.     return a + b + c;
   
9. }
   
10. 
    
11. int main(int argc, char** argv, char** env)
    
12. {
    
13.     for(int i=0; i<L1; i++)
    
14.         for(int j=0; j<L2; j++)
    
15.             for(int k=0; k<L3; k++)
    
16.                 func(i, j, k);
    
17.    
    
18.     return 0;
    
19. }

复制代码

同前面一样的编译参数。
执行结果（2次）：

1. 
   
2. real        0m0.661s
   
3. user        0m0.656s
   
4. sys        0m0.004s
   

复制代码

1. 
   
2. real        0m0.708s
   
3. user        0m0.684s
   
4. sys        0m0.004s
   

复制代码

看不出效率有什么大的差别。
希望前辈能示下^^谢谢了
当然，我知道书上确实是讲的将大的循环次数放到内部，小的放到外部，但是貌似书上讨论这个问题 的前提是在访问数组的时候，因为数组是按行存储的，所以按书上的做可以充分利用cache
哎，研究这个花了好多时间还是不明白。

ah13k

回复 2# lenovo


    哦，我的gcc版本如下

1. gcc (Ubuntu 4.4.3-4ubuntu5) 4.4.3

复制代码

lenovo

你把循环次数继续加大，越大区别越明显。
而且最内层循环只是一个函数调用，如果
是很多行代码的话，效果也会好一些。
要知道不只数据可以cache，
代码一样也要cache的。

zhainx

a，b声明为寄存器变量， 最内层的循环次数减少N倍， 然后在循环里面复制N次， 被调用函数声明为内联. 这样差不多可以优化明显点， 如果被调用函数比较简单的话， 编译器做的优化差不多也就是这样，在里面直接复制N次，干脆去掉for，减少cpu中断去判断循环变量的次数

没本

gcc -O3 -funroll-loops 会让编译器尝试展开循环。