CSDN|如何写出让 CPU 跑得更快的代码？( 三 )

本文插图
如果内存中的数据已经在 CPU Cahe 中了，那 CPU 访问一个内存地址的时候，会经历这 4 个步骤：

根据内存地址中索引信息，计算在 CPU Cahe 中的索引，也就是找出对应的 CPU Line 的地址；
找到对应 CPU Line 后，判断 CPU Line 中的有效位，确认 CPU Line 中数据是否是有效的，如果是无效的， CPU 就会直接访问内存，并重新加载数据，如果数据有效，则往下执行；
对比内存地址中组标记和 CPU Line 中的组标记，确认 CPU Line 中的数据是我们要访问的内存数据，如果不是的话， CPU 就会直接访问内存，并重新加载数据，如果是的话，则往下执行；
根据内存地址中偏移量信息，从 CPU Line 的数据块中，读取对应的字。

到这里，相信你对直接映射 Cache 有了一定认识，但其实除了直接映射 Cache 之外，还有其他通过内存地址找到 CPU Cache 中的数据的策略，比如全相连 Cache （Fully Associative Cache）、组相连 Cache （Set Associative Cache）等，这几种策策略的数据结构都比较相似，我们理解流直接映射 Cache 的工作方式，其他的策略如果你有兴趣去看，相信很快就能理解的了。如何写出让 CPU 跑得更快的代码？我们知道 CPU 访问内存的速度，比访问 CPU Cache 的速度慢了 100 多倍，所以如果 CPU 所要操作的数据在 CPU Cache 中的话，这样将会带来很大的性能提升。访问的数据在 CPU Cache 中的话，意味着缓存命中，缓存命中率越高的话，代码的性能就会越好， CPU 也就跑的越快。于是，「如何写出让 CPU 跑得更快的代码？」这个问题，可以改成「如何写出 CPU 缓存命中率高的代码？」。在前面我也提到，L1 Cache 通常分为「数据缓存」和「指令缓存」，这是因为 CPU 会别处理数据和指令，比如 1+1=2 这个运算， + 就是指令，会被放在「指令缓存」中，而输入数字 1 则会被放在「数据缓存」里。因此，我们要分开来看「数据缓存」和「指令缓存」的缓存命中率。如何提升数据缓存的命中率？假设要遍历二维数组，有以下两种形式，虽然代码执行结果是一样，但你觉得哪种形式效率最高呢？为什么高呢？

本文插图
经过测试，形式一 array[i][j] 执行时间比形式二 array[j][i] 快好几倍。
之所以有这么大的差距，是因为二维数组 array 所占用的内存是连续的，比如长度 N 的指是 2 的话，那么内存中的数组元素的布局顺序是这样的：

本文插图
形式一用 array[i][j] 访问数组元素的顺序，正是和内存中数组元素存放的顺序一致。当 CPU 访问 array[0][0] 时，由于该数据不在 Cache 中，于是会「顺序」把跟随其后的 3 个元素从内存中加载到 CPU Cache ，这样当 CPU 访问后面的 3 个数组元素时，就能在 CPU Cache 中成功地找到数据，这意味着缓存命中率很高，缓存命中的数据不需要访问内存，这便大大提高了代码的性能。
而如果用形式二的 array[j][i] 来访问，则访问的顺序就是：

本文插图
你可以看到，访问的方式跳跃式的，而不是顺序的，那么如果 N 的数值很大，那么操作 array[j][i] 时，是没办法把 array[j+1][i] 也读入到 CPU Cache 中的，既然 array[j+1][i] 没有读取到 CPU Cache ，那么就需要从内存读取该数据元素了。很明显，这种不连续性、跳跃式访问数据元素的方式，可能不能充分利用到了 CPU Cache 的特性，从而代码的性能不高。