关于for循环的执行效率问题

先提出这样一个问题,是我昨天去一家公司面试时遇到的问题,
模块一:
1  forint i= 0;i<N; i++)
2  {
3      A;
4      B;
5      C;
6  }
7 
模块二:
 1  forint i= 0;i<N; i++)
 2  {
 3      A;
 4  }
 5  forint i= 0;i<N; i++)
 6  {
 7      B;
 8  }
 9 
10  forint i= 0;i<N; i++)
11  {
12      C;
13  }
举出3个例子说明模块一比模块二执行效率高,同样举出3个例子证明模块二比模块一执行效率高。
头一次遇到这种问题,很棘手,我当时的思路是从cpu执行效率、内存使用效率这两个方面来考虑,列举了一些可能的情况,应付了过去。
回来仔细想了一下,查了一些相关的帖子好像都有提过,但都不是很全面,先把问题抛在这个地方等搞清楚了在写。

我以前遇到的问题大概都是这种类型的:
 1 for(int i = 0;i<100;i++)
 2 {
 3    for(int j = 0;j<10000;j++)
 4    {
 5       //balabala
 6    }
 7 }
 8 和
 9 for(int i = 0;i<10000;i++)
10 {
11    for(int j = 0;j<100;j++)
12    {
13       //balabala
14    }
15 }
这两个程序那个执行效率高,如果是以前我会毫不犹豫的说是第一个效率高,这是由于cpu切换的次数比较多导致性能下降,知道这句话不理解什么原理。我比较赞同下面的说法,
1. 最长循环放到内部可以提高I cache的效率,降低因为循环跳转造成cache的miss以及流水线flush造成的延时
2. 多次相同循环后也能提高跳转预测的成功率,提高流水线效率
3. 编译器会自动展开循环提高效率, 这个不一定是必然有效的
但不是绝对正确的,比如: 1 int x[1000][100];
 2 for(i=0;i<1000;i++)
 3   for(j=0;j<100;j++)
 4 {
 5   //access x[i][j]
 6 }
 7 
 8 int x[1000][100];
 9 for(j=0;j<100;j++)
10   for(i=0;i=1000;i++)
11 {
12   //access x[i][j]
13 }
14 
这时候第一个的效率就比第二个的高,原因嘛和硬件也有一些关系,CPU对于内存的访问都是通过数据缓存(cache)来进行的。
比如一个通用CPU,一级缓存(L1-Cache)的大小为16K,而其组织结构为每32个字节一组(cache line size=32byte),
也就是每次从二级缓存或内存取数据到一级缓存,都是一次性取32个字节。
对于上面的第一段代码,每次取数据到一级缓存,都有连续8次内存访问可以共享一条缓存。
而对于第二段代码,每次取数据到一级缓存后,访问一次后,基本上就没有机会被再次使用了;
上面这两段代码的区别在于第一段代码,每次内存访问后,地址值需要加常数4,而第二段代码,每次访问后,地址值加400。
如果没有对于缓存访问的区别,那么这时我们的确可以将长的循环放在里层,短的放在外层。但是而其主要原因不是一般人所想象的指令数目的区别的问题,
而主要由于分支预测错误会引起的流水线中断从而导致性能的降低。
     最后一个问题,有人说while比for循环效率高,不知道这个假设是否正确,先立在这搞清楚再补充。









posted on 2011-12-07 19:57 sheng 阅读(3202) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

统计

常用链接

留言簿(1)

随笔档案

收藏夹

同行

搜索

最新评论

阅读排行榜

评论排行榜