閱讀經(jīng)典——《深入理解計(jì)算機(jī)系統(tǒng)》08
本文將介紹存儲(chǔ)器層次結(jié)構(gòu)以及局部性對(duì)程序性能的影響。
- 什么是存儲(chǔ)器層次結(jié)構(gòu)？
- 局部性
什么是存儲(chǔ)器層次結(jié)構(gòu)
這個(gè)詞大家也許并不陌生，計(jì)算機(jī)中的存儲(chǔ)器從寄存器、緩存到內(nèi)存、硬盤，形成了一個(gè)層次結(jié)構(gòu)。為什么不用單一的一種存儲(chǔ)設(shè)備，比如只用硬盤呢？因?yàn)槊恳环N存儲(chǔ)設(shè)備都有它的優(yōu)缺點(diǎn)，硬盤雖然存儲(chǔ)空間大，但傳輸速率太慢，完全跟不上CPU的節(jié)奏，直接與CPU交換數(shù)據(jù)的話會(huì)嚴(yán)重拉低CPU的執(zhí)行效率。而內(nèi)存雖然容量小一些，但速度比硬盤快的多，因此介于CPU和硬盤之間。隨著CPU主頻越來越高，CPU與內(nèi)存的交換效率也變得越來越低，因此現(xiàn)代計(jì)算機(jī)系統(tǒng)在CPU和內(nèi)存之間插入多級(jí)緩存，以縮小CPU與內(nèi)存之間的頻率差距。
下圖為完整的存儲(chǔ)器層次結(jié)構(gòu)，從最頂層的寄存器，到最底層的遠(yuǎn)程存儲(chǔ)器（包括分布式文件系統(tǒng)、Web服務(wù)器），越往下容量越大、傳輸速率越慢、單位容量?jī)r(jià)格越低。
在存儲(chǔ)器層次結(jié)構(gòu)中，每一層都作為其下一層的緩存。比如說，當(dāng)我們想要從L1 cache中讀取數(shù)據(jù)的時(shí)候，先檢查寄存器中有沒有我們需要的數(shù)據(jù)，如果有，直接從寄存器中讀取，如果沒有，再從L1 cache中讀取。再比如說，當(dāng)我們想要從硬盤中讀取數(shù)據(jù)的時(shí)候，先檢查內(nèi)存中有沒有我們需要的數(shù)據(jù)，如果有，直接從內(nèi)存中讀取，如果沒有，再從硬盤中讀取。
存儲(chǔ)器層次結(jié)構(gòu)的優(yōu)點(diǎn)在于，作為一個(gè)整體，它的容量相當(dāng)于最底層的存儲(chǔ)設(shè)備的容量，而它的速度卻相當(dāng)于最頂層存儲(chǔ)設(shè)備的速度。也就是說，它可以在速度和容量這兩個(gè)看似矛盾的方面同時(shí)達(dá)到極限。
為什么？為什么如此神奇？
這是因?yàn)槌绦蚓哂?strong>局部性。
局部性
理解局部性對(duì)程序開發(fā)人員有極大的幫助。一般來講，有良好局部性的程序比局部性差的程序運(yùn)行得更快。
局部性有兩種：時(shí)間局部性和空間局部性。讓我們舉幾個(gè)例子來說明吧。
下面的數(shù)組元素求和函數(shù)就具有良好的時(shí)間局部性和空間局部性。
int sumvec(int v[N])
{
int i, sum = 0;
for (i = 0; i < n; i++)
{
sum += v[i];
}
return sum;
}
在該程序中，變量sum在每次循環(huán)迭代中被引用一次。如果同一個(gè)存儲(chǔ)單元在短時(shí)間內(nèi)多次被引用，我們就說該存儲(chǔ)單元具有時(shí)間局部性。向量v中的元素在循環(huán)中按照存儲(chǔ)順序依次被讀取，這些被訪問的存儲(chǔ)單元在空間上離的很近，我們就說它們有良好的空間局部性。
有局部性良好的程序，就有局部性不好的程序。下面的二維數(shù)組按列求和就是一個(gè)典型的例子。
int sumarraycols(int a[M][N])
{
int i, j, sum = 0;
for (j = 0; j < N; j++)
for (i = 0; i < M; i++)
sum += a[i][j];
return sum;
}
由于二維數(shù)組在內(nèi)存中的存放順序是按行排放的，因此該程序相當(dāng)于以N個(gè)元素的間隔訪問數(shù)據(jù)，這些存儲(chǔ)位置在空間上的距離變大，空間局部性不好。正確的做法應(yīng)該是外層循環(huán)行遍歷，內(nèi)層循環(huán)列遍歷。
上面舉的兩個(gè)例子都是數(shù)據(jù)的局部性，除此之外，還有取指令的局部性。因?yàn)橹噶畲娣旁诖鎯?chǔ)器中，CPU讀取這些指令也需要考慮局部性。for循環(huán)就具有良好的局部性，由于循環(huán)體內(nèi)的指令在存儲(chǔ)器中是連續(xù)放置的，因此具有良好的空間局部性；又由于循環(huán)會(huì)執(zhí)行多次，因此也具有良好的時(shí)間局部性。
關(guān)注作者或文集《深入理解計(jì)算機(jī)系統(tǒng)》，第一時(shí)間獲取最新發(fā)布文章。
