C语言编程之局部性原理

一、什么是局部性

一个编写良好的计算机程序常常具有良好的局部性（locality）。即，他们倾向于引用临近与其最近引用过的数据项的数据项，或者最近引用过的数据项本身。这种倾向性，被称为局部性原理。

局部性通常有两种不同的形式：

• 时间局部性

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

• 空间局部性

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

二、局部性原理的应用

一般来说，有良好局部性的程序比局部性差的程序运行得更快。

现代计算机系统的各个层次，从硬件到操作系统、再到应用程序，它的设计都利用了局部性。

• 硬件层

局部性原理允许计算机设计者通过引入称为高速缓存存储器，来保存最近被引用的指令和数据项，从而提高对主存的访问速度。

• 操作系统层

局部性原理允许系统使用主存来缓存磁盘文件系统中最近被使用的磁盘块。

• 应用程序

局部性原理在应用程序的设计中也扮演着重要角色。例如，Web浏览器将最近被引用的文档放在本地磁盘上。

三、对程序数据引用的局部性

通过举例来说明程序的局部性：

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

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

在这段程序代码中，变量 sum 在每次循环迭代中被引用一次，对于 sum 来说，有好的时间局部性。另外，sum 为标量，没有空间局部性。

向量 v 的元素是被顺序读取的，按照它们存储在内存中的顺序一个接一个。对于变量 v ，函数具有很好的空间局部性，但是时间局部性很差。因为每个向量元素只被访问一次。

对于循环体来说，其中的每个变量，要么有好的空间局部性，要么有好的时间局部性。由此断定函数 sumvec 有良好的局部性。

顺序访问一个向量每个元素的函数，具有步长为 1 的引用模式。每隔 k 个元素访问一个连续向量，就称为步长为 k 的引用模式。一般来说，随着步长的增加，空间局部性下降。

多维数组访问举例，二维数组求和，双重嵌套按照行优先顺序：

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

这个函数按照数组被存储的行优先顺序来访问这个数组，是一个以步长为 1 的引用模式，具有良好的空间局部性。

如果是以列优先顺序进行访问这个数组，for 循环修改为：

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

这个循环是按照列优先顺序扫描数组，而C语言的数组在内存中是按照 行顺序 来存放的。结果得到步长为 N 的引用模式，导致这个循环的空间局部性很差。

四、取指令的局部性

程序的指令是存放在内存中的，CPU 必须取出这些指令，因此也可以评价一个程序关于取指令的局部性。

for 循环体里的指令是按照连续的内存顺序执行的，因此循环具有良好的空间局部性。

循环体会被执行多次，因此，它也有很好的时间局部性。

五、小结

量化评价程序中局部性的一些简单原则为：

• 重复引用相同变量的程序有良好的时间局部性

• 对于具有步长为 k 的引用模式的程序，步长越小，空间局部性越好。具有步长为 1 的引用模式的程序，具有很好的空间局部性。在内存中以大步长跳来跳去的程序，空间局部性会很差。

• 对于取指令来说，循环有好的时间和空间局部性。循环体越小，循环迭代次数越多，局部性越好。