局部性原理

1.1 什么是程序局部性？

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

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

1.2 数据引用局部性

请看下面程序：

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

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

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

在看下面的例子：

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

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

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

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

1.3 取指令局部性

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

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