一、什么是局部性

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

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

時間局部性

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

空間局部性

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

二、局部性原理的應(yīng)用

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

現(xiàn)代計算機系統(tǒng)的各個層次，從硬件到操作系統(tǒng)、再到應(yīng)用程序，它的設(shè)計都利用了局部性。

硬件層

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

操作系統(tǒng)層

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

應(yīng)用程序

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

三、對程序數(shù)據(jù)引用的局部性

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

?

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

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

	?

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

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

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

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

	多維數(shù)組訪問舉例，二維數(shù)組求和，雙重嵌套按照行優(yōu)先順序：

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

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

	?

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

	如果是以列優(yōu)先順序進行訪問這個數(shù)組，for 循環(huán)修改為：

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

	?

	這個循環(huán)是按照列優(yōu)先順序掃描數(shù)組，而C語言的數(shù)組在內(nèi)存中是按照?行順序?來存放的。結(jié)果得到步長為 N 的引用模式，導致這個循環(huán)的空間局部性很差。

	四、取指令的局部性

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

	for 循環(huán)體里的指令是按照連續(xù)的內(nèi)存順序執(zhí)行的，因此循環(huán)具有良好的空間局部性。

	循環(huán)體會被執(zhí)行多次，因此，它也有很好的時間局部性。

	五、小結(jié)

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

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

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

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

	審核編輯：湯梓紅