閱讀經(jīng)典——《深入理解計算機系統(tǒng)》08
本文將介紹存儲器層次結(jié)構(gòu)以及局部性對程序性能的影響备埃。
- 什么是存儲器層次結(jié)構(gòu)财忽？
- 局部性
什么是存儲器層次結(jié)構(gòu)
這個詞大家也許并不陌生，計算機中的存儲器從寄存器鼠冕、緩存到內(nèi)存灾前、硬盤，形成了一個層次結(jié)構(gòu)寞射。為什么不用單一的一種存儲設(shè)備渔工，比如只用硬盤呢？因為每一種存儲設(shè)備都有它的優(yōu)缺點桥温，硬盤雖然存儲空間大引矩，但傳輸速率太慢，完全跟不上CPU的節(jié)奏侵浸，直接與CPU交換數(shù)據(jù)的話會嚴重拉低CPU的執(zhí)行效率旺韭。而內(nèi)存雖然容量小一些，但速度比硬盤快的多掏觉，因此介于CPU和硬盤之間区端。隨著CPU主頻越來越高，CPU與內(nèi)存的交換效率也變得越來越低澳腹，因此現(xiàn)代計算機系統(tǒng)在CPU和內(nèi)存之間插入多級緩存织盼，以縮小CPU與內(nèi)存之間的頻率差距。
下圖為完整的存儲器層次結(jié)構(gòu)酱塔，從最頂層的寄存器沥邻，到最底層的遠程存儲器（包括分布式文件系統(tǒng)、Web服務(wù)器）羊娃，越往下容量越大唐全、傳輸速率越慢、單位容量價格越低蕊玷。
在存儲器層次結(jié)構(gòu)中邮利，每一層都作為其下一層的緩存。比如說垃帅，當我們想要從L1 cache中讀取數(shù)據(jù)的時候延届，先檢查寄存器中有沒有我們需要的數(shù)據(jù)，如果有贸诚，直接從寄存器中讀取鳍咱，如果沒有，再從L1 cache中讀取疙赠。再比如說先誉，當我們想要從硬盤中讀取數(shù)據(jù)的時候，先檢查內(nèi)存中有沒有我們需要的數(shù)據(jù)，如果有，直接從內(nèi)存中讀取，如果沒有髓窜，再從硬盤中讀取。
存儲器層次結(jié)構(gòu)的優(yōu)點在于欺殿，作為一個整體寄纵，它的容量相當于最底層的存儲設(shè)備的容量，而它的速度卻相當于最頂層存儲設(shè)備的速度脖苏。也就是說程拭，它可以在速度和容量這兩個看似矛盾的方面同時達到極限。
為什么棍潘？為什么如此神奇恃鞋？
這是因為程序具有局部性。
局部性
理解局部性對程序開發(fā)人員有極大的幫助亦歉。一般來講恤浪，有良好局部性的程序比局部性差的程序運行得更快。
局部性有兩種：時間局部性和空間局部性肴楷。讓我們舉幾個例子來說明吧水由。
下面的數(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)迭代中被引用一次砂客。如果同一個存儲單元在短時間內(nèi)多次被引用，我們就說該存儲單元具有時間局部性呵恢。向量v中的元素在循環(huán)中按照存儲順序依次被讀取鞭盟，這些被訪問的存儲單元在空間上離的很近，我們就說它們有良好的空間局部性瑰剃。
有局部性良好的程序，就有局部性不好的程序筝野。下面的二維數(shù)組按列求和就是一個典型的例子晌姚。
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)存中的存放順序是按行排放的，因此該程序相當于以N個元素的間隔訪問數(shù)據(jù)歇竟，這些存儲位置在空間上的距離變大挥唠，空間局部性不好。正確的做法應(yīng)該是外層循環(huán)行遍歷焕议，內(nèi)層循環(huán)列遍歷宝磨。
上面舉的兩個例子都是數(shù)據(jù)的局部性，除此之外，還有取指令的局部性唤锉。因為指令存放在存儲器中世囊，CPU讀取這些指令也需要考慮局部性。for循環(huán)就具有良好的局部性窿祥，由于循環(huán)體內(nèi)的指令在存儲器中是連續(xù)放置的株憾，因此具有良好的空間局部性；又由于循環(huán)會執(zhí)行多次晒衩，因此也具有良好的時間局部性嗤瞎。
關(guān)注作者或文集《深入理解計算機系統(tǒng)》，第一時間獲取最新發(fā)布文章听系。
