Chinaunix首页 | 论坛 | 博客
  • 博客访问: 963081
  • 博文数量: 128
  • 博客积分: 10012
  • 博客等级: 上将
  • 技术积分: 2050
  • 用 户 组: 普通用户
  • 注册时间: 2008-10-15 17:49
文章分类

全部博文(128)

文章存档

2011年(16)

2009年(57)

2008年(55)

分类: C/C++

2008-12-04 12:09:29

某型CPU的一级数据缓存大小为16K字节,cache块大小为64字节;二级缓存大小为256K字节,cache块大小为4K字节,采用二路组相联。经测试,下面两段代码运行时效率差别很大,请分析哪段代码更好,以及可能的原因。

为了进一步提高效率,你还可以采取什么办法?

A段代码:

int matrix[1023][15];

const char *str = "this is a str";

int i, j, tmp, sum = 0;

tmp = strlen(str);

for(i = 0; i < 1023; i++)

   for(j = 0; j < 15; j++)

      sum += matrix[i][j] + tmp;

B段代码 :

int matrix[1025][17];

const char *str = "this is a str";

int i, j, sum = 0;

for(i = 0; i < 17; i++)

   for(j = 0; j < 1025; j++)

      sum += matrix[j][i] + strlen(str);

A段代码效率要远远高于B段代码,原因有三:

1、   

B 效率低最要命的地方就是每次都要调用strlen()函数,这是个严重问题,属于逻辑级错误。假设A的两层循环都不改变,仅仅是把A的那个循环里面的 temp换成strlen()调用,在Windows 2000 (Intel 双) 下测试,竟然是A的执行时间的3.699倍。(这里没有涉及不同CPU有不同的Cache设计)仅仅是这一点就已经说明B段代码垃圾代码。

2

       这也是一个逻辑级的错误。在这里我们再做个试验,AB段代码分别采用大小一样的数组[1023][15][1023][16][1023][17],只是在循环上采取了不同的方式。两者在运行时间上也是有很大差异的了。B的运行时间大概是A1.130倍。

       那么这是因为什么呢?其实也很简单,那就是A段代码中的循环执行语句对内存的访问是连续的,而B段代码中的循环执行语句对内存的访问是跳跃的。直接降低了B代码的运行效率。

       这里不是内层循环执行多少次的问题,而是一个对内存访问是否连续的问题。

3、

A的二维数组是[1023][15],B的二维数组是[1027][17],在这里B段代码有犯了一个CPU级错误(或者是Cache级的错误)。

因为在Cache中数据或指令是以行为单位存储的(也可以说是Cache),一行又包含了很多字。如现在主流的设计是一行包含64Byte。每一行拥有一个Tag。因此,假设CPU需要一个标为Tag 1的行中的数据,它会通过CAMCache中的行进行查找,一旦找到相同Tag的行,就对其中的数据进行读取。

A的是15 *4B 60B,一个Cache行刚好可以存储。B的是17*4B 68B,超过了一个Cache行所存储的数据。很明显17的时候命中率要低于15的时候。

现在我们先不管AB的循环嵌套的顺序,仅仅拿A段代码来做个试验,我们将会分三种情况来进行:

[1023][15]           [1023][16]     [1023][17]

运行结果并没有出乎意料之外 17 的时候的运行时间大概是 15 的时候的1.399倍,除去有因为17的时候多执行循环,17/15 1.133 。进行折算,17的时候大概是15的时候的1.265倍。

16的时候的执行时间要比15的时候的执行时间要短,因为是16的时候,Cache命中率更高。16/15 1.066 ,而15的执行时间却是161.068倍,加上16多执行的消耗,进行折算,15的时候大概是16的时候执行时间的1.134倍。

因为A段代码是15,而B段代码是17,在这一点上B段代码的效率要低于A段代码的效率。这是一个CPU级的错误(或者是Cache级的错误),这里涉及到Cache的块大小,也就涉及到Cache命中率,也就影响到代码效率。

不再假设什么,仅仅对A段和B段代码进行测试,B段代码的执行效率将是A段代码执行效率的3.95倍。当然最大的罪魁祸首就是B中的重复调用strlen()函数。后面两个错误告诉我们当需要对大量数据访问的时候,一定要注意对内存的访问要尽量是连续而且循环内层的访问接近Cache的块大小,以提高Cache的命中率,从而提高程序的运行效率。  

所以可以对代码进行一下修改:

#define XX    15   

#define YY    1023

int matrix[XX][YY];

const char *str = "this is a str";

int i, j, tmp, sum = 0;

tmp = strlen(str);

for(i = 0; i < XX; i++)

   for(j = 0; j < YY; j++)

      sum += matrix[i][j] + tmp;

这个程序仅仅是把数组的声明给颠倒了一下,循环也颠倒了一下,看起来和运行起来和上面给出的A段代码没有多大的区别。但是如果当XX很小,比如:8,那么这段程序和给出的A段代码就有区别了。这是因为这样做可以提高Cache的命中率。

阅读(2369) | 评论(0) | 转发(3) |
给主人留下些什么吧!~~