哪位达人可以告诉我 为什么说循环效率低？

duanius

不止一次看到说尽可能展开循环或分解循环  是和指令系统 缓存啥的有深入关系么   哪位可以指点一下？

chenzengjie

别听他们瞎说！


你没听他们都要把递归都要换成循环么？ 这又怎么说呀？

5毛党党员

怎么展开循环呢？

以前说递归效率低，需要循环替代递归。。。现在循环也低了？

雨过白鹭洲

循环不是正好利用时间和空间局部性原理吗？不明白。。。

duanius

　要充分利用CPU的指令缓存，就要充分分解小的循环。特别是当循环体本身很小的时候，分解循环可以提高性能。注意:很多编译器并不能自动分解循环。 不好的代码：



// 3D转化：把矢量 V 和 4x4 矩阵 M 相乘



for (i = 0； i < 4； i ++)



{



　　r = 0；



　　for (j = 0； j < 4； j ++)



　　{



　　　　r += M[j]*V[j]；



　　}



}



推荐的代码：



r[0] = M[0][0]*V[0] + M[1][0]*V[1] + M[2][0]*V[2] + M[3][0]*V[3]；



r[1] = M[0][1]*V[0] + M[1][1]*V[1] + M[2][1]*V[2] + M[3][1]*V[3]；



r[2] = M[0][2]*V[0] + M[1][2]*V[1] + M[2][2]*V[2] + M[3][2]*V[3]；



r[3] = M[0][3]*V[0] + M[1][3]*V[1] + M[2][3]*V[2] + M[3][3]*v[3]；

这是经典的速度优化，但许多编译程序(如gcc -funroll-loops)能自动完成这个事，所以现在你自己来优化这个显得效果不明显。



旧代码:



for (i = 0; i < 100; i++)



{



do_stuff(i);



}



新代码:



for (i = 0; i < 100; )



{



do_stuff(i); i++;



do_stuff(i); i++;



do_stuff(i); i++;



do_stuff(i); i++;



do_stuff(i); i++;



do_stuff(i); i++;



do_stuff(i); i++;



do_stuff(i); i++;



do_stuff(i); i++;



do_stuff(i); i++;



}



可以看出，新代码里比较指令由100次降低为10次，循环时间节约了90%。不过注意:对于中间变量或结果被更改的循环，编译程序往往拒绝展开，(怕担责任呗)，这时候就需要你自己来做展开工作了。



还有一点请注意，在有内部指令cache的CPU上(如MMX芯片)，因为循环展开的代码很大，往往cache溢出，这时展开的代码会频繁地在CPU 的cache和内存之间调来调去，又因为cache速度很高，所以此时循环展开反而会变慢。还有就是循环展开会影响矢量运算优化。

这个文档里面这么写   c专家编程里也提到过   我在一本算法的书上也看到过

duanius

原帖由 雨过白鹭洲 于 2008-10-17 16:51 发表
循环不是正好利用时间和空间局部性原理吗？不明白。。。

不是你昨天推荐给我的帖子么  我读了3遍。。。

局部性原理我觉得不是特别突出  因为缓存其实挺大的    想不命中都难

雨过白鹭洲

那楼主再看看《深入理解计算机系统》《代码优化：有效使用内存》《Write great code》之类的书

我是不太懂这些底层优化的东西

duanius

好 不过这是长远的  
明天搞不好就要面试了。。。
听说尽问这些问题。。。

yikaikai

哦，循环嵌套深了效率是低， 时间复杂度高了

cugb_cat

跳转太多容易使CPU的指令预测系统失效，使得CPU缓存的代码失效，需要重新从内存中读取代码，在嵌入式系统上，对这个要求比较多。