《深入理解計(jì)算機(jī)系統(tǒng)》p418

6.2 局部性

一個(gè)編寫良好的計(jì)算機(jī)程序常常具有良好的局部性( locality )。也就是,它們傾向于引用鄰近于其他最近引用過的數(shù)據(jù)項(xiàng)的數(shù)據(jù)項(xiàng),或者最近引用過的數(shù)據(jù)項(xiàng)本身。這種傾向性,被稱為局部性原理( principle of locality ),是一個(gè)持久的概念,對(duì)硬件和軟件系統(tǒng)的設(shè)計(jì)和性能都有著極大的影響。

局部性通常有兩種不同的形式:時(shí)間局部性( temporal locality )和空間局部性( spatial locality )。在一個(gè)具有良好時(shí)間局部性的程序中,被引用過一次的內(nèi)存位置很可能在不遠(yuǎn)的將來再被多次引用。在一個(gè)具有良好空間局部性的程序中,如果一個(gè)內(nèi)存位置被引用了一次,那么程序很可能在不遠(yuǎn)的將來引用附近的一個(gè)內(nèi)存位置。

程序員應(yīng)該理解局部性原理,因?yàn)橐话愣?有良好局部性的程序比局部性差的程序運(yùn)行得更快?，F(xiàn)代計(jì)算機(jī)系統(tǒng)的各個(gè)層次,從硬件到操作系統(tǒng)、再到應(yīng)用程序,它們的設(shè)計(jì)都利用了局部性。在硬件層,局部性原理允許計(jì)算機(jī)設(shè)計(jì)者通過引人稱為高速緩存存儲(chǔ)器的小而快速的存儲(chǔ)器來保存最近被引用的指令和數(shù)據(jù)項(xiàng),從而提高對(duì)主存的訪問速度。在操作系統(tǒng)級(jí),局部性原理允許系統(tǒng)使用主存作為虛擬地址空間最近破引用塊的高速緩存。類似地,操作系統(tǒng)用主存來緩存磁盤文件系統(tǒng)中最近被使用的磁盤塊。局部性原理在應(yīng)用程序的設(shè)計(jì)中也扮演著重要的角色。例如, Web 瀏覽器將最近被引用的文檔放在本地磁盤上,利用的就是時(shí)間局部性。大容量的 Web 服務(wù)器將最近被請(qǐng)求的文檔放在前端磁盤高速緩存中,這緩存能滿足對(duì)這些文檔的請(qǐng)求,而不需要服務(wù)器的任何干預(yù)。

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

考慮圖6-17a中的簡(jiǎn)單函數(shù),它對(duì)—個(gè)向量的元素求和。這個(gè)程序有良好的局部性嗎?要回答這個(gè)問題,我們來看看每個(gè)變量的引用模式。在這個(gè)例子中,變量 sum 在每次循環(huán)迭代中被引用一次,因此,對(duì)于 sum 來說,有好的時(shí)間局部性。另一方面,因?yàn)?sum 是標(biāo)量,對(duì)于 sum 來說,沒有空間局部性。

正如我們?cè)趫D6-17b中看到的,向量 v 的元素是被順序讀取的,一個(gè)接一個(gè),按照它們存儲(chǔ)在內(nèi)存中的順序(為了方便,我們假設(shè)數(shù)組是從地址0開始的)。因此,對(duì)于變量 V ,函數(shù)有很好的空局部性,但是時(shí)間局部性很差,因?yàn)槊總€(gè)向量元素只被訪問一次。因?yàn)閷?duì)于循環(huán)體中的每個(gè)變量,這個(gè)函數(shù)要么有好的空間局部性,要么有好的時(shí)間局部性,所以我們可以斷定 sumvec 函數(shù)有良好的局部性。

我們說想sumvec這樣順序訪問一個(gè)向量每個(gè)元素的函數(shù)，具有步長(zhǎng)為1的引用模式( stride-1 reference pattern )(相對(duì)于元素的大小)。有時(shí)我們稱步長(zhǎng)為1的引用模式為順序引用模式( sequential reference pattern )。一個(gè)連續(xù)向量中,每隔 k 個(gè)元素進(jìn)行訪問,就稱為步長(zhǎng)為 k 的引用模式( stride-k reference pattern )。步長(zhǎng)為1的引用模式是程序中空間局部性常見和重要的來源。一般而言,隨著步長(zhǎng)的增加,空間局部性下降。

對(duì)于引用多維數(shù)組的程序來說,步長(zhǎng)也是一個(gè)很重要的問題。例如,考慮圖6-18a中的函數(shù) sumarrayrowS ,它對(duì)一個(gè)二維數(shù)組的元素求和。雙重嵌套循環(huán)按照行優(yōu)先順序( row - major order )讀數(shù)組的元素。也就是,內(nèi)層循環(huán)讀第一行的元素,然后讀第二行,依此類推。函數(shù) sumarrayrows 具有良好的空間局部性,因?yàn)樗凑諗?shù)組被存儲(chǔ)的行優(yōu)先順序來訪問這個(gè)數(shù)組(圖6-18b)。其結(jié)果是得到一個(gè)很好的步長(zhǎng)為1的引用模式,具有良好的空間局部性。

圖6-18有良好的空間局部性,是因?yàn)閿?shù)組是按照與它存儲(chǔ)在內(nèi)存中一樣的行優(yōu)先順序來被訪問的

一些看上去很小的對(duì)程序的改動(dòng)能夠?qū)λ木植啃杂泻艽蟮挠绊憽＠?圖6-19a中的函數(shù) sumarraycols 計(jì)算的結(jié)果和圖6-18a中函數(shù) sumarrayrows 的一樣。唯一的區(qū)別是我們交換了 i 和 j 的循環(huán)。這樣交換循環(huán)對(duì)它的局部性有何影響?函數(shù) sumarraycols 的空間局部性很差,因?yàn)樗凑樟许樞騺頀呙钄?shù)組,而不是按照行順序。因?yàn)?C 數(shù)組在內(nèi)存中是按照行順序來存放的,結(jié)果就得到步長(zhǎng)為 N 的引用模式,如圖6-19b所示。

圖6-19 函數(shù)的空間局部性很差,這是因?yàn)樗褂貌介L(zhǎng)為 N 的引用模式來掃描

6.2.2 取指令的局部性

因?yàn)槌绦蛑噶钍谴娣旁趦?nèi)存中的, CPU 必須取出(讀出)這些指令,所以我們也能夠評(píng)價(jià)一個(gè)程序關(guān)于取指令的局部性。例如,圖6-17中 for 循環(huán)體里的指令是按照連續(xù)的內(nèi)存順序執(zhí)行的,因此循環(huán)有良好的空間局部性。因?yàn)檠h(huán)體會(huì)被執(zhí)行多次,所以它也有很好的時(shí)間局部性。

代碼區(qū)別于程序數(shù)據(jù)的一個(gè)重要屬性是在運(yùn)行時(shí)它是不能被修改的。當(dāng)程序正在執(zhí)行時(shí), CPU 只從內(nèi)存中讀出它的指令。 CPU 很少會(huì)重寫或修改這些指令。

6.2.3 局部性小結(jié)

在這一節(jié)中,我們介紹了局部性的基本思想,還給出了量化評(píng)價(jià)程序中局部性的一些簡(jiǎn)單原則:

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

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

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

6.6.3 在程序中利用局部性

正如我們看到的,存儲(chǔ)系統(tǒng)被組織成一個(gè)存儲(chǔ)設(shè)備的層次結(jié)構(gòu),較小、較快的設(shè)備靠近頂部,較大、較的設(shè)備靠近底部。由于采用了這種層次結(jié)構(gòu),程序訪問存儲(chǔ)位置的實(shí)際速率不是一個(gè)數(shù)字能描述的。相反,它是一個(gè)變化很大的程序局部性的函數(shù)(我們稱之為存儲(chǔ)器山),變化可以有幾個(gè)數(shù)量級(jí)。有良好局部性的程序從快速的高速緩存存儲(chǔ)器中訪問它的大部分?jǐn)?shù)據(jù)。局部性差的程序從相對(duì)慢速的 DRAM 主存中訪問它的大部分?jǐn)?shù)據(jù)。

理解存儲(chǔ)器層次結(jié)構(gòu)本質(zhì)的程序員能夠利用這些知識(shí)編寫出更有效的程序,無論具體

的存儲(chǔ)系統(tǒng)結(jié)構(gòu)是怎樣的。特別地,我們推薦下列技術(shù);

1）將你的注意力集中在內(nèi)循環(huán)上,大部分計(jì)算和內(nèi)存訪問都發(fā)生在這里。

2）通過按照數(shù)據(jù)對(duì)象存儲(chǔ)在內(nèi)存中的順序、以步長(zhǎng)為1的來讀數(shù)據(jù),從而使得你程序中的空間局部性最大。

3）一旦從存儲(chǔ)器中讀人了一個(gè)數(shù)據(jù)對(duì)象,就盡可能多地使用它,從而使得程序中的時(shí)間局部性最大。

例子：

BC例程使用了兩個(gè)加載和一個(gè)存儲(chǔ)，它們比AB例程多需要一個(gè)內(nèi)存操作。另一方面，因?yàn)閮?nèi)循環(huán)以步長(zhǎng)為1的訪問模式按行掃描B和C，每次迭代每個(gè)數(shù)組上的不命中率只有0.25次不命中，所以每次迭代總共有0.5個(gè)不命中。