我們?cè)谫I電腦時(shí)都會(huì)關(guān)注內(nèi)存、處理器、硬盤等部件的性能，都想內(nèi)存盡可能大，硬盤最好是固態(tài)的。
創(chuàng)新互聯(lián)公司2013年成立，先為蘿北等服務(wù)建站，蘿北等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為蘿北企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問題。
不知道你有沒有遇到過自己寫了大半天的文檔，因?yàn)椴恍⌒耐蝗魂P(guān)機(jī)了，自己辛苦忙活了幾個(gè)小時(shí)的成果又得重寫的情況。可是你是否想過為什么關(guān)機(jī)了就會(huì)丟失這些信息呢？為什么硬盤上的文件沒有丟？
會(huì)丟的那部分信息肯定是和電有關(guān)系的，不然也不會(huì)一斷電就丟信息。內(nèi)存就是這樣的部件，更專業(yè)一點(diǎn)的稱呼是隨機(jī)訪問存儲(chǔ)器。
隨機(jī)訪問存儲(chǔ)器（RAM）分靜態(tài)和動(dòng)態(tài)的兩種，靜態(tài) RAM 是將信息存儲(chǔ)在一個(gè)雙穩(wěn)態(tài)的存儲(chǔ)單元里。什么叫雙穩(wěn)態(tài)呢？就是只有兩種穩(wěn)定的狀態(tài)，雖然也有其它狀態(tài)，但即使細(xì)微的擾動(dòng)，也會(huì)讓它立馬進(jìn)入一個(gè)穩(wěn)定的狀態(tài)。
動(dòng)態(tài) RAM 使用的是電容來存儲(chǔ)信息，學(xué)過物理的都知道電容這個(gè)概念，它很容易就會(huì)漏電，使得動(dòng)態(tài) RAM 單元在 10~100 ms 時(shí)間內(nèi)就會(huì)丟失電荷（信息），但是不要忘記，計(jì)算機(jī)的運(yùn)行時(shí)間是以納秒計(jì)算的，1 GHz 的處理器的時(shí)鐘周期就是 1 ns，更何況現(xiàn)在的處理器都不止 1 GHz，所以 ms 相對(duì)于納秒來說是很長的，計(jì)算機(jī)不用擔(dān)心會(huì)丟失信息。
動(dòng)態(tài) RAM 芯片就封裝在內(nèi)存模塊中，比內(nèi)存更大的存儲(chǔ)部件是磁盤，發(fā)現(xiàn)自己在舊文你真的了解硬盤嗎？對(duì)磁盤總結(jié)的已經(jīng)不錯(cuò)了，就直接過渡到局部性上面去了吧。
局部性通常有兩種不同的形式：時(shí)間局部性和空間局部性。在一個(gè)具有良好時(shí)間局部性的程序中，被引用過一次的內(nèi)存位置很可能在不遠(yuǎn)的將來會(huì)再被多次引用；同樣在一個(gè)具有良好空間局部性的程序中，如果一個(gè)內(nèi)存被引用了一次，那么程序很可能在不遠(yuǎn)的將來引用附近的一個(gè)內(nèi)存位置。
不要小看局部性，局部性好的程序會(huì)比局部性差的程序運(yùn)行的更快，要往高級(jí)程序員走，這是肯定需要了解的。我們選擇把一些常用的文件從網(wǎng)盤下下來，利用的就是時(shí)間局部性。
下面這段代碼，再簡單不過，我們僅觀察一下其中的v向量，向量v的元素是一個(gè)接一個(gè)被讀取的，即按照存儲(chǔ)在內(nèi)存中的順序被讀取的，所以它有很好的空間局部性；但是每個(gè)元素都只被訪問一次，就使得時(shí)間局部性很差了。實(shí)際上對(duì)于循環(huán)體中的每個(gè)變量，這個(gè)函數(shù)要么具有好的空間局部性，要么具有好的時(shí)間局部性。
重慶分公司
重慶分公司
int sumvec(int v[N]){
int i, sum = 0;
for(i = 0; i < N; i++){
sum += v[i];
}
return sum;
}
像上面的代碼，每隔 1 個(gè)元素進(jìn)行訪問，稱之為步長為 1 的引用模式。一般而言，隨著步長的增加，空間局部性下降。
當(dāng)然，不僅數(shù)據(jù)引用有局部性，取指令也有局部性。比如for循環(huán)，循環(huán)體中的指令是按順序執(zhí)行的，并且會(huì)被執(zhí)行多次，所以它有良好的空間局部性和時(shí)間局部性。
不同存儲(chǔ)技術(shù)的訪問時(shí)間差異很大，而我們想要的是又快又大的體驗(yàn)，然而這又是違背機(jī)械原理的。為了讓程序運(yùn)行的更快，計(jì)算機(jī)設(shè)計(jì)者在不同層級(jí)之間加了緩存，比如在 CPU 與內(nèi)存之間加了高速緩存，而內(nèi)存又作為磁盤的緩存，本地磁盤又是 Web 服務(wù)器的緩存。多次訪問一個(gè)網(wǎng)頁，會(huì)發(fā)現(xiàn)有一些網(wǎng)絡(luò)請(qǐng)求的狀態(tài)碼是 300，這就是從本地緩存讀取的。
如下圖所示，高速緩存通常被組織為下面的形式，計(jì)算機(jī)需要從具體的地址去拿指令或者數(shù)據(jù)，而這個(gè)地址也被切分為不同的部分，可以直接映射到緩存上去。看下面詳細(xì)的介紹應(yīng)該更容易理解。
直接映射高速緩存每個(gè)組只有一行。高速緩存確定一個(gè)請(qǐng)求是否命中，然后抽取出被請(qǐng)求的字的過程分為：組選擇、行匹配、字抽取三步。
比如當(dāng) CPU 執(zhí)行一條讀內(nèi)存字w的指令，首先從w地址中間抽取出s個(gè)組索引位，映射到對(duì)應(yīng)的組，然后通過t位標(biāo)記確定是否有字w的一個(gè)副本存儲(chǔ)在該組中；最后使用b位的塊偏移確定所需要的字塊是從哪里開始的。
上面這個(gè)圖，還有下面這個(gè)表，對(duì)應(yīng)著看，由于能力有限，感覺怎么都講不好，多盯著一會(huì)兒，應(yīng)該就會(huì)獲得一種豁然開朗之感。
直接映射高速緩存造成沖突不命中的原因在于每個(gè)組只有一行，組相聯(lián)高速緩存放松了這一限制，每個(gè)組都保存多于一行的高速緩存行，所以在組選擇完成之后，需要遍歷對(duì)應(yīng)組中的行進(jìn)行行匹配。
當(dāng)然，我們可以把每個(gè)組中的緩存行數(shù)繼續(xù)擴(kuò)大，即全相聯(lián)高速緩存，所有的緩存行都在一個(gè)組，它總共只有一個(gè)組。因此對(duì)地址的劃分就不需要組索引了，如下圖所示。
float dotprod(float x[8], float y[8]){
float sum = 0.0;
int i;
for(i = 0; i < 8; i++){
sum += x[i] * y[i];
}
return sum;
}
這段函數(shù)很簡介，就是計(jì)算兩個(gè)向量點(diǎn)積的函數(shù)，而且對(duì)于x和y來說，這個(gè)函數(shù)具有很好的空間局部性，如果使用直接映射高速緩存，那它的緩存命中率并不高。
從表中就能看到，每次對(duì)x和y的引用都會(huì)導(dǎo)致沖突不命中，因?yàn)槲覀冊(cè)?code>x和y的塊之間抖動(dòng)，即高速緩存反復(fù)的加載替換相同的高速緩存塊組。
我們只需要做一個(gè)小小的改動(dòng)，就能讓命中率大大提高，即讓程序運(yùn)行的更快。這個(gè)改動(dòng)就是把float x[8]改為floatx[12]，改動(dòng)后的索引映射就變成下面那樣了，非常的友好。
再來看一個(gè)多維數(shù)組，函數(shù)的功能是對(duì)所有元素求和，兩種不同的寫法。
// 第一種
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;
}
// 第二種
int sumarrayrows(int a[M][N]){
int i, j, sum = 0;
for(j = 0; j < M; j++){
for(i = 0; i < N; i++){
sum += a[i][j];
}
}
return sum;
}
從編程語言角度來看，兩種寫法的效果是一樣的， 都是求數(shù)組所有元素的和，但是深入分析就會(huì)發(fā)現(xiàn)，第一種寫法會(huì)比第二種運(yùn)行的更快，因?yàn)榈诙N寫法一次緩存命中都不會(huì)發(fā)生，而第一種寫法會(huì)有 24 次緩存命中，所以第一比第二種運(yùn)行更快是必然的結(jié)果，第一種和第二種的緩存命中模式分別如下所示（粗體表示不命中）。
