百度的一道面试题（关于Cache的）

某型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、

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

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

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

3、

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

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

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

现在我们先不管A、B的循环嵌套的顺序，仅仅拿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的执行时间却是16的1.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的命中率。