时间局部性和空间局部性

局部性

一个编写良好的计算机程序常常具有良好的局部性。也就是，它们倾向于引用邻近于它最近引用过的数据项，或者最近引用的数据项本身。这种倾向被称为局部性原理。

局部性原理对于高速缓存存储器的应用有重要意义，一个良好的局部性程序更能发挥高速缓存的作用

• 时间局部性

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

• 空间局部性

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

• 取指令的局部性

程序指令可以看作一个不可修改的数据，所以它的局部性也适用于时间局部性和空间局部性。一个好的局部性需要指令可以重复多次被执行。

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

这是一个求和程序，变量sum在每次的循环迭代中都会被引用一次，因此对于sum来说有良好时间局部性。另一方面，因为sum是标量，对于sum来说没有空间局部性。

对于向量V来说，每次访问都是按照地址空间一个接一个读取的具有良好的空间局部性，但是时间局部性很差，因为每个元素都只被访问一次。

for(i=0; i < N ; i+=2) 一般而言，随着步长的增长，空间局部性会降低。但是因为循环展开和多路并行的存在，空间局部性的降低并不一定会降低程序的性能，相反有可能会明显提升程序性能。

// 程序1
int sumvec(int v[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;
}

// 程序2
int sumvec(int v[M][N])
{
  int i,j,sum=0;
  for(i =0 ; i <N ;i++)
    for(j=0; j < M ;j ++)
      sum += a[i][j]
  return sum;
}

由于对于数组来说，是按照行优先的方式存储在内存中。所以对于程序1来说，它是按照行优先的顺序遍历的，所以它的空间局部性比较好，而对于程序2来说，是按照列优先顺序遍历的，所以它的空间局部性比较差。

小结

• 重复引用相同变量的程序有良好的时间局部性。
• 对于具有步长为K的引用模式的程序，步长越小，空间局部性越好。在内存中以大步长跳来跳去的程序空间局部性会很差。
• 对于取指令来说，循环有很好的时间和空间局部性。循环体越小，循环迭代次数越多，局部性越好。

参考内容

《深入理解计算机系统》