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