z軸為速率，x軸為步長(zhǎng)，y軸為文件大?。ㄗ止?jié)），某些主流的測(cè)評(píng)軟件便是這個(gè)原理(將存儲(chǔ)器山的圖像進(jìn)行一下簡(jiǎn)單的變換，就能得到哪些軟件呈現(xiàn)的效果圖像)。上文提到過(guò)，任何一點(diǎn)小改動(dòng)，都有可能讓程序的性能發(fā)生很大的變動(dòng)，這是為什么？
當(dāng)時(shí)我們并未深究，由于我們慣性的認(rèn)為計(jì)算機(jī)的運(yùn)作方式和人類的運(yùn)作方式一致，也在過(guò)往的經(jīng)驗(yàn)中認(rèn)為計(jì)算機(jī)一定是在任何方面超越人類的存在，但是實(shí)際上，計(jì)算機(jī)除了在重復(fù)計(jì)算方面比人類的速度要快速以外，其他方面遠(yuǎn)遠(yuǎn)落后于人類的大腦，即便是我們最稀疏平常的視覺識(shí)別(看東西識(shí)別物體)，在計(jì)算機(jī)看來(lái)都是一門極其高深的領(lǐng)域，所以我們現(xiàn)在的時(shí)代的計(jì)算機(jī)還處于起步狀態(tài)，在這種時(shí)代里，程序員的作用是無(wú)可替代的，同樣程序員的一舉一動(dòng)關(guān)乎計(jì)算機(jī)的命運(yùn)。
可能在很多的方面，都已經(jīng)接觸了一臺(tái)計(jì)算機(jī)的主要組成構(gòu)造，和程序員最息息相關(guān)的便是CPU，主存以及硬盤了，可能到現(xiàn)在為止很多程序員仍然認(rèn)為編程序和這些存儲(chǔ)器有什么關(guān)系？然而一個(gè)程序員，特別是編寫C語(yǔ)言程序的程序員，最大的影響因素便來(lái)自于此，在計(jì)算機(jī)的存儲(chǔ)器結(jié)構(gòu)中，分為四種層次:
CPU寄存器 高速緩存器 主存 硬盤
但是有沒有想過(guò)，為什么計(jì)算機(jī)存儲(chǔ)器系統(tǒng)要分成這四層結(jié)構(gòu)呢？我們知道，上述四種存儲(chǔ)器的讀寫速度依次降低，我們?yōu)槭裁床贿x擇一種速度中庸的，價(jià)格也中庸的材料，制造所有層次的存儲(chǔ)器呢？
前方提到了局部性，局部性體現(xiàn)在了，當(dāng)步長(zhǎng)越大，空間局部性越低，大多數(shù)情況下會(huì)造成性能降低，比如最常見的多維數(shù)組循環(huán)(我鮮少使用多維數(shù)組的原因之一便在于此)，前面說(shuō)過(guò)多維數(shù)組實(shí)際上只是數(shù)個(gè)一維數(shù)組的包裝而已，C語(yǔ)言中并沒有真正的多維數(shù)組，而是將其解讀成內(nèi)存中的一維的連續(xù)內(nèi)存，但是當(dāng)我們遍歷它的時(shí)候，C語(yǔ)言為了不讓我們被底層實(shí)現(xiàn)所困擾，所以生成了多維數(shù)組遍歷的假象：
讓我們重溫一遍"多維數(shù)組"：
#include <stdio.h>
int main(void)
{
int dim_1_arr[4] = {1, 2, 3, 4};
int dim_2_arr[2][2] = { {1, 2}, {3, 4} };
int result_1 = 0;
int result_2 = 0;
for(int i = 0;i < 4;++i)
result_1 += dim_1_arr[i];
return 0;
}此例中，對(duì)一維數(shù)組進(jìn)行步長(zhǎng)為 1 遍歷求和，假設(shè)內(nèi)存中數(shù)組的起始位置是 0
0 => 4 => 8 => 12
for(int j = 0;j < 3;++j){
for(int i = 0;i < 3;++i){
result_2 += dim_2_arr[i][j];
}
}此例中，我們的步長(zhǎng)是多少呢？我們來(lái)看一下
0 => 8 => 4 => 12
可以很清晰的看出兩段不同代碼之間的跳躍，為什么？觀察到多維數(shù)組的遍歷中我們和平時(shí)的做法有些不同，是先對(duì)i進(jìn)行遍歷，再對(duì)j進(jìn)行遍歷，這就導(dǎo)致了程序必須在內(nèi)存塊中無(wú)規(guī)律的跳動(dòng)，這里的無(wú)規(guī)律是計(jì)算機(jī)認(rèn)為的無(wú)規(guī)律，雖然在我們看來(lái)的確是有跡可尋，優(yōu)秀的編譯器能夠?qū)λM(jìn)行優(yōu)化處理。就事論事，即這段程序的空間局部性比較差，對(duì)于一個(gè)在內(nèi)存中大幅度跳躍，無(wú)規(guī)律跳躍的程序都將影響程序的性能。這個(gè)判定對(duì)于一個(gè)連續(xù)的內(nèi)存塊來(lái)說(shuō)是很重要的，比如C語(yǔ)言中的結(jié)構(gòu)體。
實(shí)際上C語(yǔ)言也是能夠面向?qū)ο蟮模鞘謴?fù)雜，就像拿著棒子織衣服一樣。而C語(yǔ)言的機(jī)構(gòu)體能夠讓我們?cè)谝欢ǔ潭壬铣醪嚼斫鈱?duì)象這個(gè)概念，因?yàn)樗且粋€(gè)完整的個(gè)體，雖然對(duì)外界毫不設(shè)防。
對(duì)于結(jié)構(gòu)體
#define VECTOR 4
typedef struct{
double salary;
int index[4];
}test_data;
int main(void)
{
int result_1 = 0;
int result_2 = 0;
test_data dim_1_arr[VECTOR];
/* ...填充數(shù)據(jù) */
for(int i = 0;i < VECTOR;++i)
{
for(int j = 0;j < 4;++j)
result_1 += dim_1_arr[i].index[j];
}/* for loop 1 */
for(int j = 0;j < 4;++j)
{
for(int i = 0;i < VECTOR;++i)
result_2 += dim_1_arr[i].index[j];
}/* for loop 2 */
return 0;
} 還是和上方一樣，假設(shè) dim_1_arr 起始位置為 0
for loop 1：
8 => 12 => 16 => 20 ==> 32 => 36 => 40 => 44 ==> ...
for loop 2：
8 => 32 => 56 => 80 ==> 12 => 36 => 60 => 84 ==> ...
從上方不完整的比較來(lái)看，loop 1 相對(duì)于 loop 2 來(lái)說(shuō)有更好的空間局部性，很明顯在 loop 2 中，CPU讀取是在無(wú)規(guī)律的內(nèi)存位置跳躍，而 loop 1 則是以單調(diào)遞增的趨勢(shì)向前(這里的向前指的是直觀上的向前)讀取內(nèi)存。
解釋：
內(nèi)存對(duì)齊便是對(duì)于一個(gè)結(jié)構(gòu)體而言，其所占內(nèi)存大小總是最大成員的整數(shù)倍，其中最大成員指的是最基本成員，即：
typedef struct{
test_data test_1;
int test_2;
}test_data_2;
/*...*/
printf("The size of test_data_2 = %d\n",sizeof(test_data_2));
/*...*/
` 輸出： The size of test_data_2 = 32 `
typedef struct{
int index[4];
int store_1;
int store_2;
}test_data_3;
typedef struct{
test_data_3 test_3;
int test_4;
}test_data_4;
/*...*/
printf("The size of test_data_4 = %d\n",sizeof(test_data_4));
/*...*/
` 輸出： The size of test_data_2 = 28`
仔細(xì)對(duì)比`test_data_3`與`test_data`的差異，可以發(fā)現(xiàn)不同處，在前者的內(nèi)部包含了一個(gè)`double`類型的成員，在我的機(jī)器上它的長(zhǎng)度為 `8` ，后者的內(nèi)部包含了兩個(gè)`int`類型的成員，每個(gè)長(zhǎng)度為 `4`，但是他們的長(zhǎng)度在直觀上是一樣的！但是真正在使用的時(shí)候我們才能察覺到其中的差異，這就是我所說(shuō)的**最基本成員**的意義所在。雖然我們?cè)谑褂媒Y(jié)構(gòu)體的時(shí)候，能夠?qū)⑵洚?dāng)作一個(gè)整體，但是實(shí)際上他們與內(nèi)建(build-in)的類型還是有一些差異的。就此回過(guò)頭去再看看上方的 loop 解釋，應(yīng)該能夠理解到，那些數(shù)字是通過(guò)偏移量來(lái)進(jìn)行計(jì)算得到的。
在前方提到了，一般情況下，局部性好的程序能夠讓程序比局部性差的程序更有效率，而對(duì)于局部變量而言，一個(gè)好的編譯器總是盡可能的將之優(yōu)化，使其能充分使用CPU寄存器,那么寄存器的下方,也就是速度最接近寄存器的,便是所謂的高速緩存器了，對(duì)于高速緩存器而言，其最大的功效便是緩沖，緩沖有兩層意思：
對(duì)于現(xiàn)在的計(jì)算機(jī)而言，CPU基本都是三層緩存：一級(jí)緩存(L1),二級(jí)緩存(L2),三級(jí)緩存(L3)，可以通過(guò) CPU-Z(Windows) / Mac OS系統(tǒng)報(bào)告 來(lái)查看自己的CPU緩存，在軟件中我們能夠看到，在一級(jí)緩存中會(huì)分為兩個(gè)部分 ：一級(jí)數(shù)據(jù)，一級(jí)指令，這代表著只讀寫數(shù)據(jù)，只讀寫指令，這樣分開的意義在于處理器能夠同時(shí)處理一個(gè)數(shù)據(jù)和一個(gè)指令，上述所說(shuō)的都是對(duì)于一個(gè)CPU核而言的，也就是說(shuō)當(dāng)CPU是多核的時(shí)候，那就有多個(gè)這種“功能集合(L1+L2)”。二級(jí)緩存則與一級(jí)緩存同在一個(gè)核中，每個(gè)核都擁有自己的二級(jí)緩存，最后所有核共享唯一一個(gè)(L3)
2 x 32 KBytes之類的參數(shù)，32代表的就是某級(jí)的緩存大小，而前方的2則是核數(shù)，即有幾個(gè)核便有乘多少，和之前所說(shuō)的一致，具體可參見下方的緩存器圖示高速緩存器的各個(gè)層依然遵守逐步降速的規(guī)律，即讀取周期 L1 < L2 < L3，而影響較大的便是上文提到的的命中率，我們知道越上層的高速緩存器總是將下層的存儲(chǔ)器映射在自己的存儲(chǔ)器中，而按照邏輯推斷，上層的實(shí)際空間比下層的要小，因?yàn)樯蠈拥目臻g更加寶貴速度更快，這就導(dǎo)致我們無(wú)法將下層的空間一一對(duì)應(yīng)的映射到上層里，那么我們就想到一個(gè)辦法，并不是將下層存儲(chǔ)器的內(nèi)容完全映射到上層，而是上層有選擇性的將下層的部分內(nèi)容抽取到上層，這便是不命中之后的操作。
對(duì)于CPU從存儲(chǔ)器中讀取數(shù)據(jù)這個(gè)操作，如果我們使用了高速緩存以及內(nèi)存這兩個(gè)概念，那么就會(huì)有一個(gè)延伸概念，命中。而對(duì)于這個(gè)概念只有兩種情況，命中或者不命中。而對(duì)于一個(gè)初始化的高速緩存器，它一定是空的，也許在物理意義上它并不是空，但是實(shí)際上在程序看來(lái)它的確是空的，為了區(qū)分這個(gè)，高速緩存器專門使用了一個(gè)位(bit)來(lái)表示此組是否有效(即是否為空)，既然它是空的那么，我們第一次無(wú)論如何都無(wú)法命中數(shù)據(jù)，這時(shí)候該層的高速緩存器就會(huì)向下一層，在該層中尋找所要的數(shù)據(jù)，每次要向下一層申請(qǐng)尋找的行為一般稱為懲罰，而當(dāng)我們從存儲(chǔ)器中將所需的數(shù)據(jù)加載到高速緩存器中的時(shí)候，我們便開始了運(yùn)算，而一切關(guān)于高速緩存器效率的改進(jìn)都集中在命中率的提升。
假設(shè)有一個(gè)數(shù)組需要操作，由于數(shù)組是一個(gè)連續(xù)的內(nèi)存空間，對(duì)其進(jìn)行步長(zhǎng)為1的操作擁有很好的空間局部性，那么可以當(dāng)成一個(gè)很好的例子，在高速緩存器看來(lái)讀取一個(gè)有n(n>N)個(gè)元素的數(shù)組vector并不是一次性讀完，而是分次讀取，如果讀取了k次那么至少有k次不命中，這是不可避免的，而對(duì)于讀取的數(shù)據(jù)也不一定是我們需要的，用書上的例子來(lái)說(shuō)：vector:|[0]|[1]|[2]|[3]|[]|[]|[]|[]|[]|[]|[]|
假設(shè)操作數(shù)組的每一個(gè)元素，我們一次讀取三個(gè)內(nèi)存的值，類型為int，因?yàn)樵矶家粯印Ｄ敲丛诔跏蓟瘯r(shí)候，高速緩存器為空，在第一次操作的時(shí)候，讀取了四個(gè)(如上所示)，此時(shí)一定經(jīng)過(guò)了一次 不命中 。
很好理解，因?yàn)榫彺嫫骺?，所以第一次操作必然不命中，所以我們需要向下?jí)存儲(chǔ)器讀取我們需要的數(shù)據(jù)，那么第二訪問高速緩存的時(shí)候，可以命中`vector[0]`，依次命中后續(xù)兩個(gè)，直到需要`vector[4]`，出現(xiàn)了不命中，那么我們就需要重復(fù)上一步，再次讀取三個(gè)數(shù)據(jù)，依次類推直到結(jié)束。<br>`vector:|[0]|[1]|[2]|[3]|[4]|[5]|[6]|[7]|[]|[]|[]|`
現(xiàn)在我們能夠從一定層面上解釋為什么局部性好的程序比局部性差的程序要有更好的效率了，原因就在對(duì)于高速緩存器的利用，**首先反復(fù)利用本地臨時(shí)變量能夠充分的調(diào)用高速緩存器的功能做到讀寫的最優(yōu)化，其次步長(zhǎng)為越小也越能盡最大的能力發(fā)揮高速緩存器讀取的數(shù)據(jù)**，在這點(diǎn)上再回過(guò)頭思考多維數(shù)組的遍歷并進(jìn)行操作，如果沒有考慮空間局部性(即先操作大塊，再操作小塊)，那么在高速緩存器中，它的不命中率令人發(fā)指，這也是操作不當(dāng)效率低的原因。另一方面，對(duì)于不同步長(zhǎng)而言，其影響的也是高速緩存器的命中率，還是上方的vector
步長(zhǎng) | 1 | 2 | 3 | 4 | 5 |
不命中/命中 |1/4|1/2|2/3|1/1|1/1|可以看出來(lái)，對(duì)于步長(zhǎng)而言，當(dāng)?shù)搅艘欢ǖ纳舷抟院螅看蔚恼?qǐng)求都會(huì)不命中，那么這時(shí)候本層的高速緩存器相當(dāng)于作廢，時(shí)間全都耗費(fèi)在下層數(shù)據(jù)傳送到上層的時(shí)間，因?yàn)槊看巫x取都是不命中，可以利用上方的例子自己試著推理一下。
以上所說(shuō)的每次讀取下一級(jí)別存儲(chǔ)器數(shù)據(jù)的時(shí)候，都是按照內(nèi)存對(duì)齊，來(lái)讀取的，如果你的內(nèi)存數(shù)據(jù)，例如讀取結(jié)構(gòu)體時(shí)，沒有放在內(nèi)存對(duì)齊的位置(此處所說(shuō)的內(nèi)存對(duì)齊位置是以每次該級(jí)別存儲(chǔ)器讀取的大小為對(duì)齊倍數(shù)，而不是結(jié)構(gòu)體在內(nèi)存中存儲(chǔ)時(shí)的內(nèi)存對(duì)齊位置)，那么會(huì)將該位置的前后補(bǔ)齊倍數(shù)的起始位置來(lái)讀取
下一級(jí)別存儲(chǔ)器 0 1 2 3 4 5 6 7 8 9 A B C D E F
結(jié)構(gòu)體數(shù)據(jù)存放位置在 4~F
每次該級(jí)別的存儲(chǔ)器讀取 12個(gè)數(shù)據(jù)
那么本次由于結(jié)構(gòu)體存放的沒有對(duì)齊到提取的內(nèi)存位置，所有提取的可能會(huì)是 0~B也就意味著，并不是每次緩存讀取都是如此的完美，恰好都從內(nèi)存中數(shù)據(jù)的首部開始讀取，而是整片根據(jù)內(nèi)存倍數(shù)進(jìn)行讀取。
緩存器示意圖
----------------------------------------------
| CPU某個(gè)核 | ......其他核
| ---------- ---------- ------------------ |
| | | | | | | |
| | L1 | | L1 | | L2高速緩存器 | |
| | 一級(jí)數(shù)據(jù)| | 一級(jí)指令| | 二級(jí)緩存器 | |
| ---------- ---------- ------------------ |
----------------------------------------------
------------------------------------------------------------------------------------
| |
| L3高速緩存器 |
| 三級(jí)緩存器 |
------------------------------------------------------------------------------------
掃碼關(guān)注鍍金池微信號(hào)
手機(jī)訂課，優(yōu)惠多多