# 第七章 缓存

> 作者：[Allen B. Downey](http://greenteapress.com/wp/)

> 原文：[Chapter 7  Caching](http://greenteapress.com/thinkos/html/thinkos008.html)

> 译者：[飞龙](https://github.com/)

> 协议：[CC BY-NC-SA 4.0](http://creativecommons.org/licenses/by-nc-sa/4.0/)

## 7.1 程序如何运行

为了理解缓存，你需要理解计算机如何运行程序。你应该学习计算机体系结构来深入理解这个话题。这一章中我的目标是给出一个程序执行的简单模型。

当程序启动时，代码（或者程序文本）通常位于硬盘上。操作系统创建新的进程来运行程序，之后“加载器”将代码从储存器复制到主存中，并且通过调用`main`来启动程序。

在程序运行之中，它的大部分数据都储存在主存中，但是一些数据在寄存器中，它们是CPU上的小型储存单元。这些寄存器包括：

+ 程序计数器（PC），它含有程序下一条指令（在内存中）的地址。
+ 指令寄存器（IR），它含有当前执行的指令的机器码。
+ 栈指针（SP），它含有当前函数栈帧的指针，其中包含函数参数和局部变量。
+ 程序当前使用的存放数据的通用寄存器。
+ 状态寄存器，或者位寄存器，含有当前计算的信息。例如，位寄存器通常含有移位来存储上个操作是否是零的结果。

在程序运行之中，CPU执行下列步骤，叫做“指令周期”：

+ 取指（Fetch）：从内存中抓取下一条指令，储存在指令寄存器中。
+ 译码（Decode）：CPU的一部分叫做“控制单元”，将指令译码，并向CPU的其它部分发送信号。
+ 执行（Execute）：收到来自控制单元的信号后会执行合适的计算。

大多数计算机能够执行几百条不同的指令，叫做“指令集”。但是大多数指令可归为几个普遍的分类：

+ 加载：将内存中的值送到寄存器。
+ 算术/逻辑：从寄存器加载操作数，执行算术运算，并将结果储存到寄存器。
+ 储存：将寄存器中的值送到内存。
+ 跳转/分支：修改程序计数器，使控制流跳到程序的另一个位置。分支通常是有条件的，也就是说它会检查位寄存器中的旗标，只在设置时跳转。

一些指令集，包括普遍的x86，提供加载和算术运算的混合指令。

在每个指令周期中，指令从程序文本处读取。另外，普通程序中几乎一半的指令都用于储存或读取数据。计算机体系结构的一个基础问题，“内存瓶颈”就在这里。

在当前的台式机上，CPU通常为2GHz，也就是说每0.5ns就会初始化一条新的语句。但是它用于从内存中传送数据的时间约为10ns。如果CPU需要等10ns来抓取下一条指令，再等10ns来加载数据，它可能需要40个时钟周期来完成一条指令。

## 7.2 缓存性能

这一问题的解决方案，或者至少是一部分的解决方案，就是缓存。“缓存”是CPU上小型、快速的储存空间。在当前的计算机上，储存通常为1~2MiB，访问速度为1~2ns。

当CPU从内存中读取数据时，它将一份副本存到缓存中。如果再次读取相同的数据，CPU就直接读取缓存，不用再等待内存了。

当最后缓存满了的时候，为了能让新的数据进来，我们需要将一些数据扔掉。所以如果CPU加载数据之后，过了一段时间再来读取，数据就可能不在缓存中了。

许多程序的性能受限于缓存的效率。如果CPU所需的数据通常在缓存中，程序可以以CPU的全速来运行。如果CPU时常需要不在缓存中的数据，程序就会受限于内存的速度。

缓存的“命中率”`h`，是内存访问时，在缓存中找到数据的比例。“缺失率”`m`，是内存访问时需要访问内存的比例。如果`Th`是处理缓存命中的时间，`Tm`是缓存未命中的时间，每次内存访问的平均时间是：

```
h * Th + m * Tm
```

同样，我们可以定义“缺失惩罚”，它是处理缓存未命中所需的额外时间，`Tp = Tm - Th`，那么平均访问时间就是：

```
Th + m * Tp
```

当缺失率很低时平均访问时间趋近于`Th`，也就是说，程序可以表现为内存具有缓存的速度那样。

## 7.3 局部性

当程序首次读取某个字节时，缓存通常加载一“块”或一“行”数据，包含所需的字节和一些相邻数据。如果程序继续读取这些相邻数据，它们就已经在缓存中了。

例如，假设块大小是64B，你读取一个长度为64的字符串，字符串的首个字节恰好在块的开头。当你加载首个字节之后，你触发了缺失惩罚，但是之后字符串的剩余部分都在缓存中。在读取整个字符串之后，命中率是63/64。如果字符串被分在两个块中，你应该会触发两次缺失惩罚。但是这个命中率是62/64，约为97%。

另一方面，如果程序不可预测地跳来跳去，从内存中零散的位置读取数据，很少两次访问到相同的位置，缓存的性能就会很低。

程序使用相同数据多于一次的倾向叫做“时间局部性”。使用相邻位置的数据的倾向叫做“空间局部性”。辛运的是，许多程序天生就带有这两种局部性：

+ 许多程序含有非跳转或分支的代码块。由于这些代码块，指令顺序指令，访问模式具有空间局部性。
+ 在循环中，程序执行多次相同指令，所以访问模式具有时间局部性。
+ 一条指令的结果通常用于下一指令的操作数，所以数据访问模式具有时间局部性。
+ 当程序执行某个函数时，它的参数和局部变量在栈上储存在一起。这些值的访问具有空间局部性。
+ 最普遍的处理模型之一就是顺序读写数据元素。这一模式也具有空间局部性。

下一节中我们会探索程序的访问模式和缓存性能的关系。

## 7.4 缓存性能的度量

当我还是UC伯克利的毕业生时，我是Brian Harvey计算机体系结构课上的助教。我最喜欢的练习之一涉及到一个迭代数组，读写元素并度量平均时间的程序。通过改变数组的大小，就有可能推测出缓存的大小，块的大小，和一些其它属性。

我的这一程序的修改版本在本书仓库的`cache`目录下。

程序的核心部分是个循环：

```c
iters = 0;
do {
    sec0 = get_seconds();

    for (index = 0; index < limit; index += stride) 
        array[index] = array[index] + 1;
    
    iters = iters + 1; 
    sec = sec + (get_seconds() - sec0);
    
} while (sec < 0.1);
```

内部的`for`循环遍历了数组。`limit`决定数组遍历的范围。`stride`决定跳过多少元素。例如，如果`limit`是16，`stride`是4，循环就会访问0、4、8、和12。

`sec`跟踪了CPU用于内循环的的全部时间。外部循环直到`sec`超过0.1秒才会停止，这对于我们计算出平均时间所需的精确度已经足够长了。

`get_seconds`使用系统调用`clock_gettime`，将结果换算成秒，并且以`double`返回结果。

```c
double get_seconds(){
    struct timespec ts;
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &ts);
    return ts.tv_sec + ts.tv_nsec / 1e9;
}
```

![](http://greenteapress.com/thinkos/html/thinkos001.png)

图 7.1：数据大小和间隔的平均缺失惩罚函数

为了将访问数据的时间分离出来，程序运行了第二个循环，它除了内循环不访问数据之外完全相同。它总是增加相同的变量：

```c
iters2 = 0;
do {
    sec0 = get_seconds();
    
    for (index = 0; index < limit; index += stride) 
        temp = temp + index;
    
    iters2 = iters2 + 1;
    sec = sec - (get_seconds() - sec0);

} while (iters2 < iters);
```

第二个循环运行和第一个循环相同数量的迭代。在每轮迭代之后，它从`sec`中减少了消耗的时间。当循环完成时，`sec`包含了所有数组访问的总时间，减去用于增加`temp`的时间。其中的差就是所有访问触发的全部缺失惩罚。最后，我们将它除以访问总数来获取每次访问的平均缺失惩罚，以ns为单位：

```
sec * 1e9 / iters / limit * stride
```

如果你编译并运行`cache.c`，你应该看到这样的输出：

```
Size:    4096 Stride:       8 read+write: 0.8633 ns
Size:    4096 Stride:      16 read+write: 0.7023 ns
Size:    4096 Stride:      32 read+write: 0.7105 ns
Size:    4096 Stride:      64 read+write: 0.7058 ns
```

如果你安装了Python和Matplotlib，你可以使用`graph_data.py`来使结果变成图形。图7.1展示了我运行在Dell Optiplex 7010上的结果。要注意数组大小和间隔以字节为单位表述，并不是数组元素数量。

花一分钟来考虑这张图片，并且看看你是否能推断出缓存信息。下面是一些需要思考的事情：

+ 程序多次遍历并读取数组，所以有大量的时间局部性。如果整个数组能放进缓存，平均缺失惩罚应几乎为0。
+ 当间隔是4的时候，我们读取了数组的每个元素，所以程序有大量的空间局部性。如果块大小足以包含64个元素，例如，即使数组不能完全放在缓存中，命中率应为63/64。
+ 如果间隔等于块的大小（或更大），空间局部性应为0，因为每次我们读取一个块的时候，我们只访问一个元素。这种情况下，我们会看到最大的缺失惩罚。

总之，如果数组比缓存大小更小，或间隔小于块的大小，我们认为会有良好的缓存性能。如果数组大于缓存大小，并且间隔较大时，性能只会下降。

在图7.1中，缓存性能对于所有间隔很好，只要数组小于`2 ** 22`字节。我们可以推测缓存大小近似4MiB。实际上，根据规范应该是3MiB。

当间隔为8、16或32B时，缓存性能良好。在64B时开始下降，对于更大的间隔，平均缺失惩罚约为9ns。我们可以推断出块大小为128B。

许多处理器都使用了“多级缓存”，它包含一个小型快速的缓存，和一个大型慢速的缓存。这个例子中，当数组大小大于`2 ** 14`B时，缺失惩罚似乎增长了一点。所以这个处理器可能也拥有一个访问时间小于1ns的16KB缓存。