一、什么是局部性

一個編寫良好的計算機程序常常具有良好的局部性（locality）。即，他們傾向于引用臨近與其最近引用過的數據項的數據項，或者最近引用過的數據項本身。這種傾向性，被稱為局部性原理。

局部性通常有兩種不同的形式：

時間局部性

具有良好時間局部性的程序中，被引用過一次的內存位置很可能在不遠的將來再被多次引用。

空間局部性

具有良好空間局部性的程序中，如果一個內存位置被引用了一次，那么程序很可能在不遠的將來引用附近的一個內存位置。

二、局部性原理的應用

一般來說，有良好局部性的程序比局部性差的程序運行得更快。

現代計算機系統的各個層次，從硬件到操作系統、再到應用程序，它的設計都利用了局部性。

硬件層

局部性原理允許計算機設計者通過引入稱為高速緩存存儲器，來保存最近被引用的指令和數據項，從而提高對主存的訪問速度。

操作系統層

局部性原理允許系統使用主存來緩存磁盤文件系統中最近被使用的磁盤塊。

應用程序

局部性原理在應用程序的設計中也扮演著重要角色。例如，Web瀏覽器將最近被引用的文檔放在本地磁盤上。

三、對程序數據引用的局部性

通過舉例來說明程序的局部性：

?

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

????for(i?=?0;?i?

	?

	在這段程序代碼中，變量 sum 在每次循環迭代中被引用一次，對于 sum 來說，有好的時間局部性。另外，sum 為標量，沒有空間局部性。

	向量 v 的元素是被順序讀取的，按照它們存儲在內存中的順序一個接一個。對于變量 v ，函數具有很好的空間局部性，但是時間局部性很差。因為每個向量元素只被訪問一次。

	對于循環體來說，其中的每個變量，要么有好的空間局部性，要么有好的時間局部性。由此斷定函數 sumvec 有良好的局部性。

	順序訪問一個向量每個元素的函數，具有步長為 1 的引用模式。每隔 k 個元素訪問一個連續向量，就稱為步長為 k 的引用模式。一般來說，隨著步長的增加，空間局部性下降。

	多維數組訪問舉例，二維數組求和，雙重嵌套按照行優先順序：

	?
int sumarrayrows(int a[M][N])
{
????int i,?j,?sum?=?0;

????for(i?=?0;?i?

	?

	這個函數按照數組被存儲的行優先順序來訪問這個數組，是一個以步長為 1 的引用模式，具有良好的空間局部性。

	如果是以列優先順序進行訪問這個數組，for 循環修改為：

	?
for(j?=?0;?j?

	?

	這個循環是按照列優先順序掃描數組，而C語言的數組在內存中是按照?行順序?來存放的。結果得到步長為 N 的引用模式，導致這個循環的空間局部性很差。

	四、取指令的局部性

	程序的指令是存放在內存中的，CPU 必須取出這些指令，因此也可以評價一個程序關于取指令的局部性。

	for 循環體里的指令是按照連續的內存順序執行的，因此循環具有良好的空間局部性。

	循環體會被執行多次，因此，它也有很好的時間局部性。

	五、小結

	量化評價程序中局部性的一些簡單原則為：

	重復引用相同變量的程序有良好的時間局部性

	對于具有步長為 k 的引用模式的程序，步長越小，空間局部性越好。具有步長為 1 的引用模式的程序，具有很好的空間局部性。在內存中以大步長跳來跳去的程序，空間局部性會很差。

	對于取指令來說，循環有好的時間和空間局部性。循環體越小，循環迭代次數越多，局部性越好。

	審核編輯：湯梓紅