一、什么是局部性

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

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

時(shí)間局部性

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

空間局部性

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

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

一般來(lái)說(shuō)，有良好局部性的程序比局部性差的程序運(yùn)行得更快。

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

硬件層

局部性原理允許計(jì)算機(jī)設(shè)計(jì)者通過(guò)引入稱為高速緩存存儲(chǔ)器，來(lái)保存最近被引用的指令和數(shù)據(jù)項(xiàng)，從而提高對(duì)主存的訪問(wèn)速度。

操作系統(tǒng)層

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

應(yīng)用程序

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

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

通過(guò)舉例來(lái)說(shuō)明程序的局部性：

?

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

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

	?

	在這段程序代碼中，變量 sum 在每次循環(huán)迭代中被引用一次，對(duì)于 sum 來(lái)說(shuō)，有好的時(shí)間局部性。另外，sum 為標(biāo)量，沒(méi)有空間局部性。

	向量 v 的元素是被順序讀取的，按照它們存儲(chǔ)在內(nèi)存中的順序一個(gè)接一個(gè)。對(duì)于變量 v ，函數(shù)具有很好的空間局部性，但是時(shí)間局部性很差。因?yàn)槊總€(gè)向量元素只被訪問(wèn)一次。

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

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

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

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

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

	?

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

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

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

	?

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

	四、取指令的局部性

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

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

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

	五、小結(jié)

	量化評(píng)價(jià)程序中局部性的一些簡(jiǎn)單原則為：

	重復(fù)引用相同變量的程序有良好的時(shí)間局部性

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

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

	審核編輯：湯梓紅