理解程序的局部性原理

1.1 什么是程序局部性?

良好的计算机程序通常有良好的局部性,局部性主要有:

  • 时间局部性 :指的是同一个内存位置,从时间维度来看,它能够在较短时间内被多次引用。
  • 空间局部性 :指的是同一个内存位置,从空间维度来看,它附近的内存位置能够被引用 。

1.2 数据引用局部性

请看下面程序:

#例1
int sumvec(int  v[N])
{
    int i,sum=0;
    for(i=0;i

对于例1的程序,是否有良好的局部性?要回答这个问题就要看看程序中变量的引用模式。

变量sum被能在较短时间内多次引用,所以具有很好的时间局部性,但是没有引用到sum附近的内存位置,所以没有空间局部性可言。对于数据v,数据是顺序存储的,程序中也是按顺序取元素(步长为1的引用模式,步长越大,空间局部性越差 ),元素附近的位置能够被引用,所以具有良好的空间局部性,但是对于同一个内存位置,只能被引用一次,所以时间局部性很差。对于函数中每个变量 ,要么有时间局部性,要么有空间局部性,所以说这个函数具有良好的局部性 。

在看下面的例子:

#例2 
int sumvec(int  v[M][N])
{
    int i,j,sum=0;
    for(i=0;i

二维数是按照行优先顺序存储的,而例2程序中,也是按照行优先读取元素 ,所以有很好的空间局部性,但是每个元素的内存位置只被引用一次,所以时间局部性很差,再看例3。

#例3
int sumvec(int  v[M][N])
{
    int i,j,sum=0;
    for(i=0;i

例3按照列优先读取元素(程序具有步长为N的引用模式,读取下一个元素时候需要跳到步长N的位置),空间局部较差,所以例3的程序空间局部性和时间局部性都比较差。

1.3 取指令局部性

指令存放在内存中,CPU需要将取出指令,在例2,例3的循环体中,放在同一个内存位置的程序指令在短时间内会被多次读取,其附近的指令也会被多次读取,所以具有很好的局部性。

先留个问题,程序指令如何存放在内存中?