6.2.1 对程序数据引用的局部性

考虑图 6-17a 中的简单函数，它对一个向量的元素求和。这个程序有良好的局部性吗？要回答这个问题，我们来看看每个变量的引用模式。在这个例子中，变量 sum 在每次循环迭代中被引用一次，因此，对于 sum 来说，有好的时间局部性。另一方面，因为 sum 是标量，对于 sum 来说，没有空间局部性。

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

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

一个具有良好局部性的程序

地址	0	4	8	12	16	20	24	28
内容	v₀	v₁	v₂	v₃	v₄	v₅	v₆	v₇
访问顺序	1	2	3	4	5	6	7	8

向量 v 的引用模式（N = 8）

图 6-17 注意如何按照向量元素存储在内存中的顺序来访问它们

正如我们在图 6-17b 中看到的，向量 v 的元素是被顺序读取的，一个接一个，按照它们存储在内存中的顺序（为了方便，我们假设数组是从地址 0 开始的）。因此，对于变量 v，函数有很好的空间局部性，但是时间局部性很差，因为每个向量元素只被访问一次。因为对于循环体中的每个变量，这个函数要么有好的空间局部性，要么有好的时间局部性，所以我们可以断定 sumvec 函数有良好的局部性。

我们说像 sumvec 这样顺序访问一个向量每个元素的函数，具有步长为 1 的引用模式（stride-1 reference pattern）（相对于元素的大小）。有时我们称步长为 1 的引用模式为顺序引用模式（sequential reference pattern）。一个连续向量中，每隔 k 个元素进行访问，就称为步长为 k 的引用模式（stride-k reference pattern）。步长为 1 的引用模式是程序中空间局部性常见和重要的来源。一般而言，随着步长的增加，空间局部性下降。

对于引用多维数组的程序来说，步长也是一个很重要的问题。例如，考虑图 6-18a 中的函数 sumarrayrows，它对一个二维数组的元素求和。双重嵌套循环按照行优先顺序（row-major order）读数组的元素。也就是，内层循环读第一行的元素，然后读第二行，依此类推。函数 sumarrayrows 具有良好的空间局部性，因为它按照数组被存储的行优先顺序来访问这个数组（图 6-18b）。其结果是得到一个很好的步长为 1 的引用模式，具有良好的空间局部性。

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;
}

另一个具有良好局部性的程序

地址	0	4	8	12	16	20
内容	a₀₀	a₀₁	a₀₂	a₁₀	a₁₁	a₁₂
访问顺序	1	2	3	4	5	6

数组 a 的引用模式（M = 2，N = 3）

图 6-18 有良好的空间局部性，是因为数组是按照与它存储在内存中一样的行优先顺序来被访问的

一些看上去很小的对程序的改动能够对它的局部性有很大的影响。例如，图 6-19a 中的函数 sumarraycols 计算的结果和图 6-18a 中函数 sumarrayrows 的一样。唯一的区别是我们交换了 i 和 j 的循环。这样交换循环对它的局部性有何影响？函数 sumarraycols 的空间局部性很差，因为它按照列顺序来扫描数组，而不是按照行顺序。因为 C 数组在内存中是按照行顺序来存放的，结果就得到步长为 N 的引用模式，如图 6-19b 所示。

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;
}

一个空间局部性很差的程序

地址	0	4	8	12	16	20
内容	a₀₀	a₀₁	a₀₂	a₁₀	a₁₁	a₁₂
访问顺序	1	3	5	2	4	6

数组 a 的引用模式（M = 2，N = 3）

图 6-19 函数的空间局部性很差，这是因为它使用步长为 N 的引用模式来扫描