局部性原理

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的循環體中，放在同一個記憶體位置的程式指令在短時間内會被多次讀取，其附近的指令也會被多次讀取，是以具有很好的局部性。

先留個問題，程式指令如何存放在記憶體中？