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)
 2for (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)
10for (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 大熊猫 阅读(1386) 评论(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   博问   Chat2DB   管理