C語言編程之局部性

什么是局部性

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

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

• 時(shí)間局部性

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

• 空間局部性

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

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

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

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

• 硬件層

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

• 操作系統(tǒng)層

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

• 應(yīng)用程序

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

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

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

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

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

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

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

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

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

int sumarrayrows(int a[M][N])
{
    int i, j, sum = 0;
    
    for(i = 0; i < M; i++)
    {
        for(j = 0; j < N; j++)
        {
            sum += a[i][j];
        }
    }
    return sum;
}

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

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

for(j = 0; j < N; j++)
{
  for(i = 0; i < M; i++)
  {
      sum += a[i][j];
  }
}

這個(gè)循環(huán)是按照列優(yōu)先順序掃描數(shù)組，而C語言的數(shù)組在內(nèi)存中是按照 行順序 來存放的。結(jié)果得到步長為 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à)程序中局部性的一些簡單原則為：

• 重復(fù)引用相同變量的程序有良好的時(shí)間局部性
• 對(duì)于具有步長為 k 的引用模式的程序，步長越小，空間局部性越好。具有步長為 1 的引用模式的程序，具有很好的空間局部性。在內(nèi)存中以大步長跳來跳去的程序，空間局部性會(huì)很差。
• 對(duì)于取指令來說，循環(huán)有好的時(shí)間和空間局部性。循環(huán)體越小，循環(huán)迭代次數(shù)越多，局部性越好。