教你编写对高速缓存Cache友好的代码

如果还没有阅读过本系列第一篇 《Cache 的基本概念与工作原理》 ，小伙伴们可以点击链接先阅读第一篇介绍的基础知识。

本文想要讲述的内容如下：

1、如何写出对高速缓存友好的代码？

2、这背后的原理是什么？

一个编写良好的计算机程序常常具有良好的局部性。也就是说，这些程序倾向于访问最近引用过的数据项周边的数据项，或者最近引用过的数据项本身。这种倾向性，被称为局部性原理（principle of locality）。这个概念在计算机系统中使用得非常广泛，对硬件和软件系统的设计和性能都有着极大的影响。

在上一篇文章中，简要介绍了局部性的两种形式：

• 时间局部性

在一个具有良好时间局部性的程序中，被引用过一次的内存位置很可能在不远的将来再被多次引用。

• 空间局部性

在一个具有良好空间局部性的程序中，如果一个内存位置被引用了一次，那么程序很可能在不远的将来引用附近的一个内存位置。

这是一个非常重要的概念，因为在计算机系统的各个层次，从硬件到操作系统、再到应用程序，他们都利用了局部性，下面举几个简单的例子：

1、在 CPU 中，设计者通过引入高速缓存（Cache）来保存最近被引用的指令和数据。

2、在操作系统中，局部性原理允许系统使用主存（DRAM）作为虚拟地址空间最近被引用块的缓存。

3、Web 浏览器将最近被引用的文档放在本地磁盘上。

4、当你玩游戏进入一张新的地图时，整张地图被加载到内存中作为缓存，这样你就可以到处玩耍而不用忍受卡顿了。

2.1 数据引用的局部性

2.1.1 引用一维数组

考虑如下函数，该函数对一个数组中的元素求和：

1int sum_array(int array[N])
2{
3    int i, sum = 0;
4
5    for (i = 0; i < N; i++)
6        sum += array[i];
7
8    return sum;
9}

对于变量 sum 来说，它在每次循环迭代中被引用一次，因此，对 sum 来说，有好的时间局部性。另外，对于 sum 来说，没有空间局部性。

数组 array 中的元素是被顺序读取的，一个接着一个，按照它们在内存中的顺序。因此，对于变量 array，函数具有很好的空间局部性，但是时间局部性很差，因为每个 array 中的元素只被访问一次。因为对于循环体中的每个变量，这个函数要么有好的空间局部性，要么有很好的时间局部性，所以我们可以断定 sum_array() 函数具有良好的局部性。

像 sum_array() 这样的顺序访问数组中每个元素的函数，称其为具有步长为 1 的引用模式。在一个连续的引用地址空间中，每隔 k 个元素进行访问，就称为步长为 k 的引用模式。一般而言，随着步长的增加，空间局部性下降。

2.1.1 引用多维数组

对于引用多维数组的程序来说，步长是一个很重要的问题。如果是按照内层循环先读第一行的元素，然后读第二行，以此类推的话，其结果就能得到一个很好的步长为 1 的引用模式，具有良好的空间局部性。但是如果按照列的顺序来扫描数组，而不是按照行的顺序，就会得到步长为 N 的引用模式，考虑如下函数：

 1int sum_array_cols(int a[M][N])
 2{
 3    int i, j, sum = 0;
 4
 5    for (j = 0; j < N; j++)
 6        for (i = 0; i < M; i ++)
 7            sum += a[i][j];
 8
 9    return sum;
10}

该函数的空间局部性很差，因为它是按列进行数组扫描，每次引用数据的地址间隔为 N，也就是说使用步长为 N 的引用模式来扫描二维数组。

2.2 取指令的局部性

因为 CPU 在执行指令前，必须要先取出要执行的指令。因此我们也能够评价一个程序关于取指令的局部性。例如 2.1.1 节中提到的 for 循环体中，这些指令是按照连续的内存顺序执行的，因此具有良好的空间局部性。因为循环体会被执行多次，所以也具有良好的时间局部性。

3.1 为什么这样做

程序的性能指执行程序所用的时间，显然程序的性能与程序执行时访问指令和数据所用的时间有很大关系，而指令和数据的访问时间与相应的 Cache 命中率、命中时间和和缺失损失有关。对于给定的计算机系统而言，命中时间和缺失损失是确定的。因此，指令和数据的访存时间主要由 Cache 命中率决定，而 Cache 的命中率则主要由程序的空间局部性和时间局部性决定。

一个优秀的软件工程师应当写出具有良好访问局部性的程序，也就是对高速缓存友好的代码。下面向大家来介绍一些确保代码对高速缓存友好的基本方法。

• 让最常见的情况运行得快

程序通常把大部分时间都花在少量的核心函数上，而这些函数通常把大部分时间都花在了少量循环上。所以要把注意力集中在核心函数里的循环上，而忽略其他部分。

• 尽量减少每个循环内部的缓存不命中数量

  
  

在其他条件相同的情况下，不命中率较低的循环运行得更快。

3.2 举一个简单的栗子

我们仍然通过观察最初的小例子来试图理解上面介绍的原理是如何工作的。

1int sum_array(int array[N])
2{
3    int i, sum = 0;
4
5    for (i = 0; i < N; i++)
6        sum += array[i];
7
8    return sum;
9}

对于局部变量 i 和 sum，循环体有着良好的时间局部性。实际上，因为他们都是局部变量，任何合理的优化编译器都会把他们缓存在寄存器中，也就是存储器层次结构的最高层中。