for多层循环效率的讨论

hongtianyu

本人阅读了林锐的高质量C++/C编程指南,看到其中关于for多层循环效率问题,原文是这样阐述的:
"
【建议4-4-1】在多重循环中，如果有可能，应当将最长的循环放在最内层，最短的循环放在最外层，以减少CPU跨切循环层的次数。例如示例4-4(b)的效率比示例4-4(a)的高。

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

{

for ( col=0; col<5; col++ )

{

sum = sum + a[row][col];

}

}
示例4-4(a) 低效率：长循环在最外层

for (col=0; col<5; col++ )

{

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

{

sum = sum + a[row][col];

}

}
示例4-4(b) 高效率：长循环在最内层

"

我自己也测试了一下,发现在我的机器上测试结果刚好与林博士所说的相反,下面的是我的测试代码:
1 #include <iostream>
2 #include <time.h>
3 using namespace std;
4
5 #define COL 10000
6 #define ROW 100
7 int main(int argv,char *agrc[])
8 {
9 int col;
10 int row;
11 int i;
12 int a[COL][ROW];
13
14 time_t t1=clock();
15 for(row=0;row<ROW;row++)
16 for(col=0;col<COL;col++)
17 a[col][row]=col+row;
18
19 time_t t2=clock();
20 cout<<"ROW<COL time:"<<double(t2-t1)/CLOCKS_PER_SEC<<endl;
21
22 int b[COL][ROW];
23 t1=clock();
24 for(col=0;col<COL;col++)
25 for(row=0;row<ROW;row++)
26 b[col][row]=col+row;
27
28 t2=clock();
29 cout<<"COL>ROW time:"<<double(t2-t1)/CLOCKS_PER_SEC<<endl;
30 return 1;
31 }
在我的机器上,前一个用时大约:0.2s,后一个0.03s.

有谁能解释真正的原因不?

Edengundam

for (a)
{
  for (b)
    do sth.
}

理论分析得出的结论:
算法分析时候, 从第一层循环到第二层循环花费t1. 第二层执行花费t2
得出时间开销为a*t1 + a*b*t2;
因此当a < b时候, 开销就小了.

玄铁寒冰

据说和CPU cache有关

cornia

在你机器上运行，每次都是同样的结果？

hellioncu

应该跟Cache有关，对于二维数组[COL][ROW]的COL不变，数据是相邻的

cjaizss

原帖由 hellioncu 于 2007-1-4 15:04 发表
应该跟Cache有关，对于二维数组[COL][ROW]的COL不变，数据是相邻的

是的，要让程序贴近局部性原则

sevendays

林博士的这本书看看也就罢了，有些基本概念还是不错的，但在实际项目中，纠缠于这种东西太浪费时间了，效率也不一定能高到哪儿去

原帖由 hongtianyu 于 2007-1-2 11:15 发表
本人阅读了林锐的高质量C++/C编程指南,看到其中关于for多层循环效率问题,原文是这样阐述的:
"
【建议4-4-1】在多重循环中，如果有可能，应当将最长的循环放在最内层，最短的循环放在最外层，以减少CPU跨切 ...

beepbug

原帖由 hongtianyu 于 2007-1-2 11:15 发表
本人阅读了林锐的高质量C++/C编程指南,看到其中关于for多层循环效率问题,原文是这样阐述的:
"
【建议4-4-1】在多重循环中，如果有可能，应当将最长的循环放在最内层，最短的循环放在最外层，以减少CPU跨切 ...

这种说法是错误的。譬如，对数组操作的两层循环，如果数组的物理存储是行优先的（现在的数组都是如此），则应该外层对行，内层对列，才有高效率。这样才能充分发挥Cache的效果，即提高Cache的命中率。如果反过来做，特别是当列数很多、元素很大时，Cache的命中率会非常低。

namtso

世界级的大牛，比如写《深入C++对象模型》，或者C++之父BS，遇到效率问题，一般都会说：理论上可能如何如何，但是真正的结果一定要在具体的环境中实际测试。

hyvgs

优化除了有良好的算法结构以外，还涉及到很多的方面，硬件的处理方式必须有所了解

除了cache以外，现代CPU会对代码进行分支预测和预读取等优化执行效率的处理
如果代码编译后生成的机器语言更适合CPU的优化执行，执行效率也会高出不少

不过了解太多的底层实现来优化程序，成本太高。
大部分情况下，一般的设计人员只要有良好的代码结构就足够了。我估计林博士应该和我的观点是一样的^_^

[ 本帖最后由 hyvgs 于 2007-1-4 17:01 编辑 ]