免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12下一页
最近访问板块 发新帖
查看: 8765 | 回复: 12

for多层循环效率的讨论 [复制链接]

论坛徽章:
0
发表于 2007-01-02 11:15 |显示全部楼层
本人阅读了林锐的高质量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.

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

论坛徽章:
0
发表于 2007-01-02 11:23 |显示全部楼层
for (a)
{
  for (b)
    do sth.
}

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

论坛徽章:
0
发表于 2007-01-02 14:26 |显示全部楼层
据说和CPU cache有关

论坛徽章:
0
发表于 2007-01-03 11:07 |显示全部楼层
在你机器上运行,每次都是同样的结果?

论坛徽章:
297
射手座
日期:2013-08-23 12:04:38射手座
日期:2013-08-23 16:18:12未羊
日期:2013-08-30 14:33:15水瓶座
日期:2013-09-02 16:44:31摩羯座
日期:2013-09-25 09:33:52双子座
日期:2013-09-26 12:21:10金牛座
日期:2013-10-14 09:08:49申猴
日期:2013-10-16 13:09:43子鼠
日期:2013-10-17 23:23:19射手座
日期:2013-10-18 13:00:27金牛座
日期:2013-10-18 15:47:57午马
日期:2013-10-18 21:43:38
发表于 2007-01-04 15:04 |显示全部楼层
应该跟Cache有关,对于二维数组[COL][ROW]的COL不变,数据是相邻的

论坛徽章:
3
2015年迎新春徽章
日期:2015-03-04 09:56:11数据库技术版块每日发帖之星
日期:2016-08-03 06:20:00数据库技术版块每日发帖之星
日期:2016-08-04 06:20:00
发表于 2007-01-04 15:06 |显示全部楼层
原帖由 hellioncu 于 2007-1-4 15:04 发表
应该跟Cache有关,对于二维数组[COL][ROW]的COL不变,数据是相邻的

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

论坛徽章:
0
发表于 2007-01-04 16:37 |显示全部楼层
林博士的这本书看看也就罢了,有些基本概念还是不错的,但在实际项目中,纠缠于这种东西太浪费时间了,效率也不一定能高到哪儿去

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

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

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

论坛徽章:
0
发表于 2007-01-04 16:57 |显示全部楼层
世界级的大牛,比如写《深入C++对象模型》,或者C++之父BS,遇到效率问题,一般都会说:理论上可能如何如何,但是真正的结果一定要在具体的环境中实际测试。

论坛徽章:
0
发表于 2007-01-04 16:58 |显示全部楼层
优化除了有良好的算法结构以外,还涉及到很多的方面,硬件的处理方式必须有所了解

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

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

[ 本帖最后由 hyvgs 于 2007-1-4 17:01 编辑 ]
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP