VC++ C++ C# Algorithm

C++博客 首页 新随笔 联系 聚合 管理
  21 Posts :: 3 Stories :: 31 Comments :: 0 Trackbacks
今天偶尔看道了计算机体系结构中有关编译器优化对提高Cache性能的影响一节,其中说道如果有数组,假设int a[5000][100],我们写下如下代码,则第一种效率高于第二种。原因是第二个循环以100*4字节的跨距访问存储器,势必造成Cache失效次数增加,增大了访存时间,而第一种循环顺序地访问一个Cache块中地元素,减少了失效次数,提高了Cache性能。
 14-4(a)
 2
for (row=0; row<5000; row++)
 
3{
 
4  for ( col=0; col<100; col++ )
 
5  {
 
6     sum = sum + a[row][col];
 
7  }

 
8}

 
94-4(b)
10
for (col=0; col<100; col++ )
11{
12  for (row=0; row<5000; row++)
13  {
14    sum = sum + a[row][col];
15  }

16}

但我又想起了林锐博士的高质量C++编程手册,其中写到:在多重循环中,如果有可能,应当将最长的循环放在最内层,最短的循环放在最外层,以减少CPU 跨切循环层的次数。按照他的说法,上面二种写法,后一种比较好,这不就跟体系结构书上说的矛盾了吗?我不知道谁对谁错,也不知道减少CPU 跨切循环层的次数是怎么具体影响效率,大家不知有何看法。
posted on 2006-12-17 23:14 大熊猫 阅读(1366) 评论(4)  编辑 收藏 引用

Feedback

# re: 循环的效率 2006-12-18 11:14 LOGOS
写成 for (i=0; i<row*col; ++i)如何?  回复  更多评论
  

# re: 循环的效率 2006-12-18 12:38 shephard
CPU一个才多少钱,人脑一个要多少钱
两种写法的CPU周期才差多少,在一个团队里沟通两种写法的区别又要花多少人月
说实话,觉得这样在意效率真的没什么意思
毕竟近五年内,可能的巨大效率提升还是会发生在多线程上  回复  更多评论
  

# re: 循环的效率 2006-12-18 12:49 WeiFeng
原来早就有人对这点产生怀疑了,去看看吧
http://www.linuxsir.org/bbs/printthread.php?t=248134  回复  更多评论
  

# re: 循环的效率 2006-12-18 18:24 liuliu
这个例子其实不好,因为这里的效率差别主要在于对内存中数组元素的访问是否连续了。如果把内层循环内容改为空或者改为sum=1之类,对于for本身的耗费应该可以看到差别。
如果没有其他影响因素,把循环次数多的for写在内层肯定是有好书的。
首先,对于内层,每个for“本身”都执行了100*5000次,而对于外层,却是不同,分别为100和5000,这里可能有些差别。
另外,我想也是更主要的一点,(a)的内层循环连续执行100次后要被打断一次执行外部循环,如果内层有内容,连续执行肯定可以更有效的利用register和cache,而每次打断可能会需要一些外部的交换操作。相比之下,(b)就是连续执行5000次后被打断一次,一共被打断100次,这里的开销差别如果在苛刻的条件下,肯定需要考虑的。
不过,一般情况下,应该差别不大,特别是相对于内存甚至IO操作,比如上面这个例子的col和row。如果这两者影响同时存在,考虑了for的问题而忘记了内存操作,那就是本末倒置了,毕竟一个是register或cache级别的,一个是memory级别的,差大了。
个人理解,不一定对:)  回复  更多评论
  


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