6.5 编写高速缓存友好的代码

在 6.2 节中，我们介绍了局部性的思想，而且定性地谈了一下什么会具有良好的局部性。明白了高速缓存存储器是如何工作的，我们就能更加准确一些了。局部性比较好的程序更容易有较低的不命中率，而不命中率较低的程序往往比不命中率较高的程序运行得更快。因此，从具有良好局部性的意义上来说，好的程序员总是应该试着去编写高速缓存友好（cache friendly）的代码。下面就是我们用来确保代码高速缓存友好的基本方法。

1. 让最常见的情况运行得快。程序通常把大部分时间都花在少量的核心函数上，而这些函数通常把大部分时间都花在了少量循环上。所以要把注意力集中在核心函数里的循环上，而忽略其他部分。
2. 尽量减小每个循环内部的缓存不命中数量。在其他条件（例如加载和存储的总次数）相同的情况下，不命中率较低的循环运行得更快。

为了看看实际上这是怎么工作的，考虑 6.2 节中的函数 sumvec：

int sumvec(int v[N])
{
    int i, sum = 0;

    for (i = 0; i < N; i++)
        sum += v[i];
    return sum;
}

这个函数高速缓存友好吗？首先，注意对于局部变量 i 和 sum，循环体有良好的时间局部性。实际上，因为它们都是局部变量，任何合理的优化编译器都会把它们缓存在寄存器文件中，也就是存储器层次结构的最高层中。现在考虑一下对向量 v 的步长为 1 的引用。一般而言，如果一个高速缓存的块大小为 B 字节，那么一个步长为 k 的引用模式（这里 k 是以字为单位的）平均每次循环迭代会有

min(1, (wordsize × k) / B)

次缓存不命中。当 k = 1 时，它取最小值，所以对 v 的步长为 1 的引用确实是高速缓存友好的。例如，假设 v 是块对齐的，字为 4 个字节，高速缓存块为 4 个字，而高速缓存初始为空（冷高速缓存）。然后，无论是什么样的高速缓存结构，对 v 的引用都会得到下面的命中和不命中模式：

v[i]	i = 0	i = 1	i = 2	i = 3	i = 4	i = 5	i = 6	i = 7
访问顺序，命中 [h] 或不命中 [m]	1 [m]	2 [h]	3 [h]	4 [h]	5 [m]	6 [h]	7 [h]	8 [h]

在这个例子中，对 v[0] 的引用会不命中，而相应的包含 v[0]～v[3] 的块会被从内存加载到高速缓存中。因此，接下来三个引用都会命中。对 v[4] 的引用会导致不命中，而一个新的块被加载到高速缓存中，接下来的三个引用都命中，依此类推。总的来说，四个引用中，三个会命中，在这种冷缓存的情况下，这是我们所能做到的最好的情况了。

总之，简单的 sumvec 示例说明了两个关于编写高速缓存友好的代码的重要问题：

• 对局部变量的反复引用是好的，因为编译器能够将它们缓存在寄存器文件中（时间局部性）。
• 步长为 1 的引用模式是好的，因为存储器层次结构中所有层次上的缓存都是将数据存储为连续的块（空间局部性）。

在对多维数组进行操作的程序中，空间局部性尤其重要。例如，考虑 6.2 节中的 sumarrayrows 函数，它按照行优先顺序对一个二维数组的元素求和：

int sumarrayrows(int a[M][N])
{
    int i, j, sum = 0;

    for (i = 0; i < M; i++)
        for (j = 0; j < N; j++)
            sum += a[i][j];
    return sum;
}

由于 C 语言以行优先顺序存储数组，所以这个函数中的内循环有与 sumvec 一样好的步长为 1 的访问模式。例如，假设我们对这个高速缓存做与对 sumvec 一样的假设。那么对数组 a 的引用会得到下面的命中和不命中模式：

a[i][j]	j = 0	j = 1	j = 2	j = 3	j = 4	j = 5	j = 6	j = 7
i = 0	1 [m]	2 [h]	3 [h]	4 [h]	5 [m]	6 [h]	7 [h]	8 [h]
i = 1	9 [m]	10 [h]	11 [h]	12 [h]	13 [m]	14 [h]	15 [h]	16 [h]
i = 2	17 [m]	18 [h]	19 [h]	20 [h]	21 [m]	22 [h]	23 [h]	24 [h]
i = 3	25 [m]	26 [h]	27 [h]	28 [h]	29 [m]	30 [h]	31 [h]	32 [h]

但是如果我们做一个看似无伤大雅的改变——交换循环的次序，看看会发生什么：

int sumarraycols(int a[M][N])
{
    int i, j, sum = 0;

    for (j = 0; j < N; j++)
        for (i = 0; i < M; i++)
            sum += a[i][j];
    return sum;
}

在这种情况中，我们是一列一列而不是一行一行地扫描数组的。如果我们够幸运，整个数组都在高速缓存中，那么我们也会有相同的不命中率 1/4。不过，如果数组比高速缓存要大（更可能出现这种情况），那么每次对 a[i][j] 的访问都会不命中！

a[i][j]	j = 0	j = 1	j = 2	j = 3	j = 4	j = 5	j = 6	j = 7
i = 0	1 [m]	5 [m]	9 [m]	13 [m]	17 [m]	21 [m]	25 [m]	29 [m]
i = 1	2 [m]	6 [m]	10 [m]	14 [m]	18 [m]	22 [m]	26 [m]	30 [m]
i = 2	3 [m]	7 [m]	11 [m]	15 [m]	19 [m]	23 [m]	27 [m]	31 [m]
i = 3	4 [m]	8 [m]	12 [m]	16 [m]	20 [m]	24 [m]	28 [m]	32 [m]

较高的不命中率对运行时间可以有显著的影响。例如，在桌面机器上，sumarrayrows 运行速度比 sumarraycols 快 25 倍。总之，程序员应该注意他们程序中的局部性，试着编写利用局部性的程序。

练习题 6.17　在信号处理和科学计算的应用中，转置矩阵的行和列是一个很重要的问题。从局部性的角度来看，它也很有趣，因为它的引用模式既是以行为主（row-wise）的，也是以列为主（column-wise）的。例如，考虑下面的转置函数：

typedef int array[2][2];

void transpose1(array dst, array src)
{
    int i, j;

    for (i = 0; i < 2; i++) {
        for (j = 0; j < 2; j++) {
            dst[j][i] = src[i][j];
        }
    }
}

假设在一台具有如下属性的机器上运行这段代码：

• sizeof(int) == 4。
• src 数组从地址 0 开始，dst 数组从地址 16（十进制）开始。
• 只有一个 L1 数据高速缓存，它是直接映射的、直写和写分配的，块大小为 8 个字节。
• 这个高速缓存总的大小为 16 个数据字节，一开始是空的。
• 对 src 和 dst 数组的访问分别是读和写不命中的唯一来源。

A. 对每个 row 和 col，指明对 src[row][col] 和 dst[row][col] 的访问是命中（h）还是不命中（m）。例如，读 src[0][0] 会不命中，写 dst[0][0] 也不命中。

dst 数组

	列 0	列 1
0 行	m
1 行

src 数组

	列 0	列 1
0 行	m
1 行

B. 对于一个大小为 32 数据字节的高速缓存重复这个练习。

练习题 6.18　最近一个很成功的游戏 SimAquarium 的核心就是一个紧密循环（tight loop），它计算 256 个海藻（algae）的平均位置。在一台具有块大小为 16 字节（B = 16）、整个大小为 1024 字节的直接映射数据缓存的机器上测量它的高速缓存性能。定义如下：

struct algae_position {
    int x;
    int y;
};

struct algae_position grid[16][16];
int total_x = 0, total_y = 0;
int i, j;

还有如下假设：

• sizeof(int) == 4。
• grid 从内存地址 0 开始。
• 这个高速缓存开始时是空的。
• 唯一的内存访问是对数组 grid 的元素的访问。变量 i、j、total_x 和 total_y 存放在寄存器中。

确定下面代码的高速缓存性能：

for (i = 0; i < 16; i++) {
    for (j = 0; j < 16; j++) {
        total_x += grid[i][j].x;
    }
}

for (i = 0; i < 16; i++) {
    for (j = 0; j < 16; j++) {
        total_y += grid[i][j].y;
    }
}

A. 读总数是多少？

B. 缓存不命中的读总数是多少？

C. 不命中率是多少？

练习题 6.19　给定练习题 6.18 的假设，确定下列代码的高速缓存性能：

for (i = 0; i < 16; i++) {
    for (j = 0; j < 16; j++) {
        total_x += grid[j][i].x;
        total_y += grid[j][i].y;
    }
}

A. 读总数是多少？

B. 高速缓存不命中的读总数是多少？

C. 不命中率是多少？

D. 如果高速缓存有两倍大，那么不命中率会是多少呢？

练习题 6.20　给定练习题 6.18 的假设，确定下列代码的高速缓存性能：

for (i = 0; i < 16; i++) {
    for (j = 0; j < 16; j++) {
        total_x += grid[i][j].x;
        total_y += grid[i][j].y;
    }
}

A. 读总数是多少？

B. 高速缓存不命中的读总数是多少？

C. 不命中率是多少？

D. 如果高速缓存有两倍大，那么不命中率会是多少呢？