大概所有學(xué)習(xí)C語言的初學(xué)者，都被前輩說過，C語言是世界上接近最速的編程語言，當(dāng)然這并不是吹牛，也并不是貶低其他語言，誠然非C語言能寫出高速度的代碼，但是C語言更容易寫出高速的程序(高速不代表高效)，然而再好的工具，在外行人手中也只能是黯淡沒落。

對(duì)于現(xiàn)代編譯器，現(xiàn)代CPU而言，我們要盡量迎合CPU的設(shè)計(jì)(比如架構(gòu)和處理指令的方式等)，雖然編譯器是為程序員服務(wù)，并且在盡它最大的能力來優(yōu)化程序員寫出的代碼，但是畢竟它還沒有脫離電子的范疇，如果我們的代碼不能讓編譯器理解，編譯器無法幫我們優(yōu)化代碼，那么我們就無法寫出一個(gè)高速的程序。

對(duì)于此，我們可以暫且忽略CPU的設(shè)計(jì)，因?yàn)槲覀冊(cè)趯用嫔现荒芸紤]如何迎合編譯器的優(yōu)化規(guī)則，而CPU則是語言以及編譯器的事情了。

提高程序的速度，就C語言而言可以有這幾種方法:

首先還是要設(shè)計(jì)合理的大綱，正所謂一個(gè)程序最大的性能提升就是它第一次運(yùn)行的時(shí)候
要避免連續(xù)的函數(shù)調(diào)用。

• 消除不必要的存儲(chǔ)器使用(并非推薦使用register)
• 使用循環(huán)展開技巧，一般編譯器的優(yōu)化選項(xiàng)能自動(dòng)幫你修改代碼成循環(huán)展開
• 對(duì)于一個(gè)操作的核心耗時(shí)部分，通過重新組合技術(shù)來提高速度
• 多采用幾種風(fēng)格的寫法，而不是直觀的認(rèn)為，因?yàn)橛?jì)算機(jī)的想法和你是不一樣的

注：隨著編譯器的版本更新，即使不開啟優(yōu)化選項(xiàng)，自帶的編譯器優(yōu)化依舊能夠?yàn)槲覀兙帉懙拇a提供一部分優(yōu)化，這便是不使用老版本編譯器的原因，雖然作為一個(gè)程序員不應(yīng)該太依賴于編譯器，但是我認(rèn)為，時(shí)代在進(jìn)步，信息量正在無限的膨脹，但是人類的大腦以及精力在一個(gè)大時(shí)代內(nèi)是有限的，換句話說對(duì)于普通人而言我們的記憶是有限的，我們不應(yīng)該把精力放在前人已經(jīng)做完的事情上，而是要站在巨人的肩膀上向更遠(yuǎn)處眺望，如此我們應(yīng)該充分利用工具來幫助我們實(shí)現(xiàn)一些既有的功能，而程序員應(yīng)該更 專注于發(fā)現(xiàn)新的思路，以及想法，在圖靈測(cè)試尚未有人打破之前，程序員依賴編譯器并不是一件錯(cuò)誤的事情。

對(duì)于當(dāng)下的編譯器，以GCC(GCC不僅僅是一個(gè)編譯器，但這里將它當(dāng)成編譯器的代名詞)為例，-O2是一個(gè)為大眾所接受的優(yōu)化等級(jí)，對(duì)于其他編譯器，一般程序員可以選擇使用由Google和Apple聯(lián)合開發(fā)的編譯器clang也是一個(gè)很好的選擇， 在-O2的優(yōu)化等級(jí)下，GCC一般情況下能夠自動(dòng)執(zhí)行循環(huán)展開優(yōu)化，

開始.

 /*struct.h*/ 
 #include <stdio.h>
 typedef struct me{
   int  value;
   struct me* next;
 }data_t;

 typedef struct{
   int index;
   data_t* storage;
 }block; 

為了測(cè)試方便我們首先定義了兩個(gè)結(jié)構(gòu)體，分別是:

block代表一個(gè)塊，每個(gè)塊都有一個(gè)序號(hào)(int)，一個(gè)數(shù)據(jù)域data_t
data_t代表一個(gè)數(shù)據(jù)域，原型是一個(gè)鏈表，每個(gè)data_t對(duì)象中包含一個(gè)數(shù)據(jù)和一個(gè)指針。

 /*main.c*/
 #include "struct.h"
 #define ARR_SIZE 10
 static inline int get_len(const data_t* data)
 {
  int len = 0;

  if(!data)
   fprintf(stderr,"The data in %p is NULL\n",data);
  else
   while(!data->next)
   {
    ++len;
    data = data->next;
   }
  return len;
 }

 static inline void mix_cal(const block* process, int result[])
 {
  for(int i = 0;i < get_len(process->storage);++i)
  {
   *result += (process->storage)[i];
  }
 }

此時(shí)我們得到了兩個(gè)測(cè)試函數(shù)，get_len和mix_cal分別用來得到data_t長(zhǎng)度，以及計(jì)算數(shù)據(jù)域的總和。

 /*main.c*/ 
 int main(void)
 {
  block* block_in_all[ARR_SIZE] = { NULL };
  int result_in_all[ARR_SIZE] = { 0 };
  /*
  * 假設(shè)生成了許多的`block`類型對(duì)象
  * 將許多的`block`放置在一個(gè)數(shù)組中，每個(gè)元素類型為`block*`
  * 每個(gè)block對(duì)象中都包含非空的data_t類型的數(shù)據(jù)域
  */
  for(int i = 0;i < ARR_SIZE;++i)
  {
   mix_cal(block_in_all[i], result_in_all+i);
  }
  for(int i = 0;i < ARR_SIZE;++i)
  {
   printf("The %dth block have the total %d data\n",
      block_in_all[i]->index, result_in_all[i]);
  }

  return 0;
 }

耐心讀完上述的代碼，它是用來求和的，求一個(gè)域中的所有元素的和。仔細(xì)分析一下，很容易就能看見一些缺點(diǎn)，最大的莫過于在mix_cal函數(shù)中對(duì)于get_len函數(shù)的調(diào)用，在此處看來十分明顯，但是我們?cè)诰帉懗绦虻臅r(shí)候是否能夠注意到這個(gè)問題呢？
對(duì)于一些不必要的函數(shù)調(diào)用我們要做的便是將他們提取出來，使用臨時(shí)變量是一個(gè)很好的辦法，因?yàn)樵诰幾g器的幫助下臨時(shí)變量在允許的情況下能夠充分的利用CPU的寄存器。之所以是允許的情況下，是因?yàn)榧拇嫫鞯臄?shù)量并不多，而編譯器在寄存器的使用上需要考慮許多的復(fù)雜因素，故并不是每次使用臨時(shí)變量都能加入寄存器。但這并不妨礙我們提升程序的性能。

在此處，我們應(yīng)該將for循環(huán)中的判斷語句里的get_len函數(shù)提取出來，在外部使用一個(gè)臨時(shí)變量接收結(jié)果，而不是在循環(huán)中一直調(diào)用該函數(shù)。

 int len = get_len(process->storage);

.

依舊是上方的代碼，我們來講述一下，循環(huán)展開。

對(duì)于mix_cal函數(shù)，我們或者說編譯器可以如何提升它的速度呢？我們說過一點(diǎn)的小改變都可能對(duì)一個(gè)程序的最終代碼產(chǎn)生極大的影響，對(duì)此最常用的便是嘗試，前人之路早已鋪好，不需要重復(fù)造輪子了。

循環(huán)展開:

 int reality = len - 1, i;
 for(i = 0;i < reality;i+=2)
 {
  *result = *result + (process->storage)[i] 
      + (process->storage)[i+1];
 }
 for(;i < len;++i)
 {
  *result += (process->storage)[i];
 }

這就是循環(huán)展開中的2次循環(huán)展開，同樣還有n次循環(huán)展開。

同樣，在剛才提到過寄存器的使用以及減少不必要的開銷，在此程序中對(duì)于(process->storage)[i]這樣的存儲(chǔ)器位置解引用太過浪費(fèi)，我們總是將其優(yōu)化成本低臨時(shí)變量的使用

 data* local_data = process->storage;

這將為程序帶來十分可觀的節(jié)約，雖然這些工作在編譯器的優(yōu)化中都能包括，但是一旦我們的代碼難以被編譯器所理解(雖然編譯器的升級(jí)最大的目的就是提升優(yōu)化效果)，那么我們很可能得到一個(gè)性能不夠可觀的程序。所以當(dāng)我們并不是特別緊湊的時(shí)候，可以將這些工作當(dāng)成我們的本分來做，而不是交給編譯器來做。

以及對(duì)于外部存儲(chǔ)位置 result 我們?cè)诖颂幰彩谴嬖谥速M(fèi)，同樣我們應(yīng)該使用一個(gè)臨時(shí)變量來存儲(chǔ)總和，而不是每次得到結(jié)果便對(duì)它進(jìn)行解引用操作。

 int local_result = 0;
 /*...*/
 local_result = local_result + local_data[i] + local_data[i+1];
 /*...*/
 *result = local_result;

在上方我們可以看見循環(huán)展開被稱作2次循環(huán)展開，那么自然可以推斷有n次循環(huán)展開，自然是有的，對(duì)于一個(gè)n次循環(huán)展開的式子我們有一個(gè)簡(jiǎn)便的上界確定公式即:

 reality = len - n + 1;

至于展開幾次最好，依然是視環(huán)境而定。 故最終的版本應(yīng)該為：

 static inline void mix_cal(const block* process, int result[])
 {
  int local_result = 0;
  int len = get_len(process->storage);
  int reality = len - 1, i;
  data* local_data = process->storage;

  for(i = 0;i < reality;i+=2)
   local_result += local_data[i] + local_data[i+1];
  for(;i < len;++i)
   local_result += local_data[i];

  *result = local_result;
 }

解釋：循環(huán)展開將元素相加分為兩個(gè)部分，第一部分每次加兩個(gè)元素，由于如此做會(huì)剩余元素沒有加，故在第二部分將剩下的元素都加起來。

. 還有一種叫做重新組合的技巧，即為讓一個(gè)表達(dá)式中的運(yùn)算數(shù)自由組合，組合出最快速的一種，但是這種方法未曾試驗(yàn)過。故不提及。

. 對(duì)于條件分支預(yù)測(cè)錯(cuò)誤造成的時(shí)間損耗，稱之為懲罰，最通俗的說法，就是當(dāng)你編寫的代碼中含有條件分支的時(shí)候，處理器會(huì)選擇去預(yù)判某一個(gè)分支是此次正確的支路，這樣可以避免修改任何實(shí)際的寄存器和存儲(chǔ)器，一直到確定了實(shí)際結(jié)果，要是不對(duì)，那就慘了，這段時(shí)間做的事情都白費(fèi)了。但是也不必過分的關(guān)心這種條件分支的預(yù)測(cè)，這也是我放在最后說的意義所在。

這里有兩種較為客觀的方法，一種被稱為命令式，一種被稱為功能式

命令式：

 for(int i = 0;i < n;++i)
 {
  if(a[i] > b[i]){
   int temp = a[i];
   a[i] = b[i];
   b[i] = temp;
  }
 }

功能式：

 int min, max;
 for(int i = 0;i < n;++i)
 { 
  min = a[i] < b[i] ? a[i] : b[i];
  max = a[i] < b[i] ? b[i] : a[i];
  a[i] = min;
  b[i] = max;
 }

很清晰的一個(gè)例子，明顯看出來，前者對(duì)于不同情況所作的程序步數(shù)明顯不同，而后者無論什么情況都是相同的程序步。

兩個(gè)形式的好處前者對(duì)于可預(yù)測(cè)數(shù)據(jù)來說，是一個(gè)很好的模型，后者則是中庸之道，什么是可預(yù)測(cè)不可預(yù)測(cè)，比如一個(gè)數(shù)是負(fù)數(shù)還是正數(shù)這就是不可預(yù)測(cè)的，用前面那個(gè)代碼會(huì)有很大的懲罰。

. 多路并行的技巧也是一個(gè)很重要的思路，可能在很多人眼中看來，兩條語句依次寫出和合并的效果一定是一樣。但是多路并行有一個(gè)缺點(diǎn)就是對(duì)寄存器的數(shù)量有所要求，當(dāng)寄存器不夠時(shí)(稱為溢出)，性能不升反降。同樣是對(duì)于循環(huán)展開，此次使用四次循環(huán)展開加二路并行：

 for(i = 0;i < reality;i+=4){
  local_result_1 += local_data[i] + local_data[i+1];
  local_result_2 += local_data[i+2] + local_data[i+3];
 }//也可以分成四路并行，每一路存一個(gè)。這種做法充分利用了CPU流水線的性能
 for(;i < len;++i)
  local_result_1 += local_data[i];

 *result = local_result_1 + local_result_2;

Tips:

上文中寫到的函數(shù)大都帶有static inline關(guān)鍵字，這是何意？首先我們要確定一件事情，對(duì)于非工程的單文件而言，static函數(shù)并沒有什么意義(意義指的是對(duì)于可見性而言，并非說它一無是處)，許多人對(duì)于static函數(shù)感到茫然的原因在于:我明明將一個(gè)函數(shù)聲明定義成static類型了，但是我還是可以在別的文件中訪問到??！

其實(shí)這是因?yàn)槟愀揪蜎]有理解C語言工程這個(gè)意思，大部分人是這么測(cè)試的:

首先在一個(gè)文件夾里創(chuàng)建兩個(gè)文件 test_static.c和static.h:

 /*static.h*/
 #ifndef STATIC_H
 #define STATIC_H
 static void test(void);

 static void test(void);
 {
  printf("Hello World!\n");
 }
 #endif
...

 /*test_static.c*/
 #include <stdio.h>
 #include "static.h"

 void test(void);
 int main(void)
 {
  test();   //編譯通過，可以運(yùn)行。
  return 0;
 }

然后編譯運(yùn)行，發(fā)現(xiàn)可以通過?。?！標(biāo)準(zhǔn)怎么說在其他文件中不可見？而把static.h去掉#include之后發(fā)現(xiàn)報(bào)錯(cuò)test undefined，瞬間初學(xué)者就凌亂了。

好吧，實(shí)際上是前輩們以及教材的錯(cuò)，因?yàn)閺氖贾两K，所有外界現(xiàn)象都告訴我們C程序是獨(dú)立的一個(gè)一個(gè)文件組成的，但是并沒有告訴我們要先將他們弄成一個(gè)工程！此處如果是使用Visual Studio學(xué)習(xí)C語言的可能會(huì)對(duì)工程這個(gè)概念理解的稍微好一些，雖然不推薦使用 VS 學(xué)習(xí)C語言。

你想要實(shí)現(xiàn)static函數(shù)僅在本文件可見的效果，請(qǐng)你先補(bǔ)習(xí)一下工程這個(gè)概念，對(duì)于任何可見或者不可見的概念而言都是建立在一個(gè)工程內(nèi)而言，而不是像上方的代碼，使用#include來表示，你都#include了，那還有什么可見不可見的當(dāng)然都可見了。所以一個(gè)static函數(shù)可見于不可見是基于一個(gè)個(gè)工程里的所有C語言源文件而言的。所以你將?？匆娗拜厒冞@么回答你的提問:

 /*static.h*/
 #ifndef STATIC_H
 #define STATIC_H
 static void test(void);

 static void test(void);
 {
  printf("Hello World!\n");
 }
 #endif
...

 /*test_static.c*/
 #include <stdio.h>

 void test(void);
 int main(void)
 {
  test();   //報(bào)錯(cuò)，因?yàn)閠est是static函數(shù)。
  return 0;
 }

發(fā)現(xiàn)了嗎？在上方代碼中，少了一行#include "static.h"但是這個(gè)代碼依舊可行，因?yàn)檫@兩個(gè)文件是建立在同一個(gè)工程里的，而不是在一個(gè)文件夾中隨意新建兩個(gè)源文件這么簡(jiǎn)單，你可以使用各個(gè)IDE的工程功能來進(jìn)行測(cè)試。

回到正題，在這里稍微提一下static對(duì)函數(shù)的某些作用，它可以讓函數(shù)放在一個(gè)靜態(tài)的空間中，而不是棧里，這是的它的調(diào)用更加快速，經(jīng)常與inline關(guān)鍵字一起使用，為的就是讓函數(shù)更加快。但是有利有弊，可以自己權(quán)衡一下。

注：存儲(chǔ)器山就是對(duì)于不同步長(zhǎng)不同大小文件的讀取速率的三維坐標(biāo)圖，形似一座山，z軸為速率，x軸為步長(zhǎng)，y軸為文件大小（字節(jié)），某些主流的測(cè)評(píng)軟件便是這個(gè)原理(將存儲(chǔ)器山的圖像進(jìn)行一下簡(jiǎn)單的變換，就能得到哪些軟件呈現(xiàn)的效果圖像)。

上文提到過，任何一點(diǎn)小改動(dòng)，都有可能讓程序的性能發(fā)生很大的變動(dòng)，這是為什么？

當(dāng)時(shí)我們并未深究，由于我們慣性的認(rèn)為計(jì)算機(jī)的運(yùn)作方式和人類的運(yùn)作方式一致，也在過往的經(jīng)驗(yàn)中認(rèn)為計(jì)算機(jī)一定是在任何方面超越人類的存在，但是實(shí)際上，計(jì)算機(jī)除了在重復(fù)計(jì)算方面比人類的速度要快速以外，其他方面遠(yuǎn)遠(yuǎn)落后于人類的大腦，即便是我們最稀疏平常的視覺識(shí)別(看東西識(shí)別物體)，在計(jì)算機(jī)看來都是一門極其高深的領(lǐng)域，所以我們現(xiàn)在的時(shí)代的計(jì)算機(jī)還處于起步狀態(tài)，在這種時(shí)代里，程序員的作用是無可替代的，同樣程序員的一舉一動(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語言程序的程序員，最大的影響因素便來自于此，在計(jì)算機(jī)的存儲(chǔ)器結(jié)構(gòu)中，分為四種層次:
CPU寄存器、高速緩存器、主存、硬盤。

但是有沒有想過，為什么計(jì)算機(jī)存儲(chǔ)器系統(tǒng)要分成這四層結(jié)構(gòu)呢？我們知道，上述四種存儲(chǔ)器的讀寫速度依次降低，我們?yōu)槭裁床贿x擇一種速度中庸的，價(jià)格也中庸的材料，制造所有層次的存儲(chǔ)器呢？

有人給出的解釋是，一個(gè)編寫良好的程序總是傾向于訪問層次更高的存儲(chǔ)器，而對(duì)于現(xiàn)在的技術(shù)，價(jià)格高昂而無法大量制造的高速存儲(chǔ)器來說，我們可以選擇按層次分配構(gòu)造，讓我們以最低的成本的存儲(chǔ)器達(dá)到使用最高的速度存儲(chǔ)器的效果。
就像是在自己的計(jì)算機(jī)上，當(dāng)我們打開一個(gè)很笨重的應(yīng)用程序后，會(huì)發(fā)現(xiàn)，下一次再打開的時(shí)候可能會(huì)更快，就像以前歷史遺留的一個(gè)問題 Visual Studio 2008 在 Windows XP 上，第一次打開總是十分卡頓，但是當(dāng)關(guān)閉程序之后第二次打開卻是很流暢。在參考書中，提到過兩個(gè)評(píng)價(jià)程序速度的關(guān)鍵點(diǎn)：時(shí)間局部性和空間局部性 。
時(shí)間局部性：在訪問過某塊存儲(chǔ)器之后的不久的將來，很可能會(huì)再次訪問它
空間局部性：在訪問過某塊存儲(chǔ)器之后的不就的將來，很可能訪問其鄰近的存儲(chǔ)器位置。
良好的局部性改進(jìn)一般能很好的提升程序的性能。
所謂局部性就是當(dāng)我們使用過某些資源后，這些資源總是以一種形式存儲(chǔ)在更高級(jí)更方便的存儲(chǔ)器當(dāng)中，讓最近一次的存取請(qǐng)求能夠更加有效率的進(jìn)行。
打個(gè)不太貼切的比喻，假設(shè)計(jì)算機(jī)是一個(gè)家，CPU是一個(gè)人，想象一下這個(gè)家中的所有物品都是井然有序的，這個(gè)人想要工作必然會(huì)需要工作物品，所以他需要從某些地方拿來，用完以后再放回去，這些地方就是存儲(chǔ)器，但是過了一段時(shí)間發(fā)現(xiàn)這么做太浪費(fèi)時(shí)間，有時(shí)候某些東西太遠(yuǎn)了，所以，人想把它把它放在離自己更進(jìn)的地方，這樣自己的效率就高很多，如果這個(gè)東西一段時(shí)間內(nèi)不再用，則把它放回原處，留出位置給更需要的工作物品，于是形成了越常使用的物品離人越近的現(xiàn)象。這便是計(jì)算機(jī)存儲(chǔ)器的分層結(jié)構(gòu)的意義。
而對(duì)于一個(gè)有良好局部性的程序而言，我們總能在離自己最近的地方找到我們所需要的數(shù)據(jù)，回到計(jì)算機(jī)：我們知道計(jì)算機(jī)的存儲(chǔ)器是分層結(jié)構(gòu)的，即每一層對(duì)應(yīng)著不同的讀寫速度等級(jí)(CPU寄存器 > 高速緩存 > 主存 > 硬盤)，而我們的程序總是按照從左至右的順序依次查找，每次找到一個(gè)所需要數(shù)據(jù)，不出意外，總是將其移動(dòng)到上一層次的存儲(chǔ)器中存儲(chǔ)，以便下次更高速的訪問，我們稱這種行為叫做 命中 。越好的程序，越能將當(dāng)時(shí)所需的數(shù)據(jù)放在越靠近左邊的地方。這便是局部性的意義所在。
當(dāng)然，存儲(chǔ)器如此分層也是出于無奈，在處理器的速度和存儲(chǔ)器的速度實(shí)在差距的情況下只有如此做才能讓處理器更加充分的利用，而不至于等待存儲(chǔ)器讀寫而空閑，也許某一天，當(dāng)內(nèi)存的位價(jià)和普通硬盤不相上下或者差距不多的時(shí)候，也許內(nèi)存就是硬盤了。而當(dāng)今也有人使用某些特殊的軟件在實(shí)現(xiàn)這個(gè)功能，憑著自己計(jì)算機(jī)上大容量的內(nèi)存，分割出來當(dāng)作硬盤使用，存取速度讓硬盤望塵莫及。
局部性：

前方提到了局部性，局部性體現(xiàn)在了，當(dāng)步長(zhǎng)越大，空間局部性越低，大多數(shù)情況下會(huì)造成性能降低，比如最常見的多維數(shù)組循環(huán)(我鮮少使用多維數(shù)組的原因之一便在于此)，前面說過多維數(shù)組實(shí)際上只是數(shù)個(gè)一維數(shù)組的包裝而已，C語言中并沒有真正的多維數(shù)組，而是將其解讀成內(nèi)存中的一維的連續(xù)內(nèi)存，但是當(dāng)我們遍歷它的時(shí)候，C語言為了不讓我們被底層實(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)是多少呢？我們來看一下

0 => 8 => 4 => 12

可以很清晰的看出兩段不同代碼之間的跳躍，為什么？觀察到多維數(shù)組的遍歷中我們和平時(shí)的做法有些不同，是先對(duì)i進(jìn)行遍歷，再對(duì)j進(jìn)行遍歷，這就導(dǎo)致了程序必須在內(nèi)存塊中無規(guī)律的跳動(dòng)，這里的無規(guī)律是計(jì)算機(jī)認(rèn)為的無規(guī)律，雖然在我們看來的確是有跡可尋，優(yōu)秀的編譯器能夠?qū)λM(jìn)行優(yōu)化處理。就事論事，即這段程序的空間局部性比較差，對(duì)于一個(gè)在內(nèi)存中大幅度跳躍，無規(guī)律跳躍的程序都將影響程序的性能。這個(gè)判定對(duì)于一個(gè)連續(xù)的內(nèi)存塊來說是很重要的，比如C語言中的結(jié)構(gòu)體。

實(shí)際上C語言也是能夠面向?qū)ο蟮?，但是十分?fù)雜，就像拿著棒子織衣服一樣。而C語言的機(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 ==> ...

從上方不完整的比較來看，loop 1 相對(duì)于 loop 2 來說有更好的空間局部性，很明顯在 loop 2 中，CPU讀取是在無規(guī)律的內(nèi)存位置跳躍，而 loop 1 則是以單調(diào)遞增的趨勢(shì)向前(這里的向前指的是直觀上的向前)讀取內(nèi)存。

在此處回顧一下C語言的結(jié)構(gòu)體性質(zhì)與知識(shí)：
對(duì)于任意一個(gè)完整定義的結(jié)構(gòu)體，每一個(gè)對(duì)象所占有的內(nèi)存大小都符合內(nèi)存對(duì)齊的規(guī)則。
對(duì)于結(jié)構(gòu)體內(nèi)的各個(gè)成員而言，其相對(duì)于對(duì)象存儲(chǔ)地址起始的距離，稱為偏移量。
解釋：

內(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í)候我們才能察覺到其中的差異，這就是我所說的**最基本成員**的意義所在。雖然我們?cè)谑褂媒Y(jié)構(gòu)體的時(shí)候，能夠?qū)⑵洚?dāng)作一個(gè)整體，但是實(shí)際上他們與內(nèi)建(build-in)的類型還是有一些差異的。
偏移量通俗地說，就是該成員起始地址距離起始位置的長(zhǎng)度，在結(jié)構(gòu)體中，C語言是怎么為結(jié)構(gòu)體分配設(shè)定大小的呢？除了內(nèi)存對(duì)齊外，還需要考慮定義結(jié)構(gòu)體時(shí)，其中成員的聲明順序，換句話說，誰首先聲明，誰的位置就靠前。而某個(gè)成員的偏移量代表著其起始位置減去其所屬對(duì)象的起始位置，(此處需要注意的是，兩個(gè)毫不相干的指針相減所得到的結(jié)果是無意義的，只有當(dāng)兩個(gè)指針同在一個(gè)作用域內(nèi)時(shí)，減法才是有意義的，為了避免潛在的錯(cuò)誤，我們要謹(jǐn)慎使用指針減法操作)。
就此回過頭去再看看上方的 loop 解釋，應(yīng)該能夠理解到，那些數(shù)字是通過偏移量來進(jìn)行計(jì)算得到的。

之所以沒有詳細(xì)的介紹時(shí)間局部性是因?yàn)?，?duì)于時(shí)間局部性而言，其最大的影響因素便是操作區(qū)域的大小，比如我們操作的數(shù)組或者文件的大小，越小時(shí)間局部性越好，試想一下對(duì)于一個(gè)小的文件和大的文件，我們更容易操作到同一塊地方多次的，必定是小的文件。而操作文件的大小有時(shí)候并不能很好得成為我們的操作因素，故只能多關(guān)注空間局部性。
高速緩存器：

在前方提到了，一般情況下，局部性好的程序能夠讓程序比局部性差的程序更有效率，而對(duì)于局部變量而言，一個(gè)好的編譯器總是盡可能的將之優(yōu)化，使其能充分使用CPU寄存器,那么寄存器的下方,也就是速度最接近寄存器的,便是所謂的高速緩存器了，對(duì)于高速緩存器而言，其最大的功效便是緩沖，緩沖有兩層意思：

緩存數(shù)據(jù)，使下一次需要的數(shù)據(jù)盡可能的“靠近”CPU，此處的靠近并不是物理意義上的距離靠近。
緩沖一下CPU于存儲(chǔ)器巨大的速度差距，防止CPU空閑浪費(fèi)。
對(duì)于現(xiàn)在的計(jì)算機(jī)而言，CPU基本都是三層緩存：一級(jí)緩存(L1),二級(jí)緩存(L2),三級(jí)緩存(L3)，可以通過 CPU-Z(Windows) / Mac OS系統(tǒng)報(bào)告 來查看自己的CPU緩存，在軟件中我們能夠看到，在一級(jí)緩存中會(huì)分為兩個(gè)部分 ：一級(jí)數(shù)據(jù)，一級(jí)指令，這代表著只讀寫數(shù)據(jù)，只讀寫指令，這樣分開的意義在于處理器能夠同時(shí)處理一個(gè)數(shù)據(jù)和一個(gè)指令，上述所說的都是對(duì)于一個(gè)CPU核而言的，也就是說當(dāng)CPU是多核的時(shí)候，那就有多個(gè)這種“功能集合(L1+L2)”。二級(jí)緩存則與一級(jí)緩存同在一個(gè)核中，每個(gè)核都擁有自己的二級(jí)緩存，最后所有核共享唯一一個(gè)(L3)

總的來說，對(duì)于高速緩存器來說，一般分為三層，第一層比較特殊由獨(dú)立的兩個(gè)部分組成，第二層第三層則是各自獨(dú)立一體并未區(qū)分功能(既存數(shù)據(jù)又存指令)，而第一層和第二層則是每個(gè)核單獨(dú)享有不同的緩存器，第三層則是各個(gè)核共享一個(gè)層，所以我們經(jīng)?？匆娫趥€(gè)人計(jì)算機(jī)上，L3的大小經(jīng)常是以MB為單位的，而第一層則多以KB甚至是Byte為單位。
在實(shí)際中，喜歡研究計(jì)算機(jī)的人經(jīng)常會(huì)在一些專業(yè)軟件中看見自己的CPU配置，在緩存一欄的一級(jí)和二級(jí)中總能看見2 x 32 KBytes之類的參數(shù)，32代表的就是某級(jí)的緩存大小，而前方的2則是核數(shù)，即有幾個(gè)核便有乘多少，和之前所說的一致。

高速緩存器的各個(gè)層依然遵守逐步降速的規(guī)律，即讀取周期 L1 < L2 < L3，而影響較大的便是上文提到的的命中率，我們知道越上層的高速緩存器總是將下層的存儲(chǔ)器映射在自己的存儲(chǔ)器中，而按照邏輯推斷，上層的實(shí)際空間比下層的要小，因?yàn)樯蠈拥目臻g更加寶貴速度更快，這就導(dǎo)致我們無法將下層的空間一一對(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í)際上在程序看來它的確是空的，為了區(qū)分這個(gè)，高速緩存器專門使用了一個(gè)位(bit)來表示此組是否有效(即是否為空)，既然它是空的那么，我們第一次無論如何都無法命中數(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è)很好的例子，在高速緩存器看來讀取一個(gè)有n(n>N)個(gè)元素的數(shù)組vector并不是一次性讀完，而是分次讀取，如果讀取了k次那么至少有k次不命中，這是不可避免的，而對(duì)于讀取的數(shù)據(jù)也不一定是我們需要的，用書上的例子來說：
vector:|[0]|[1]|[2]|[3]|[]|[]|[]|[]|[]|[]|[]|
假設(shè)操作數(shù)組的每一個(gè)元素，我們一次讀取三個(gè)內(nèi)存的值，類型為int，因?yàn)樵矶家粯印Ｄ敲丛诔跏蓟瘯r(shí)候，高速緩存器為空，在第一次操作的時(shí)候，讀取了四個(gè)(如上所示)，此時(shí)一定經(jīng)過了一次 不命中 。

很好理解，因?yàn)榫彺嫫骺眨缘谝淮尾僮鞅厝徊幻?，所以我們需要向下?jí)存儲(chǔ)器讀取我們需要的數(shù)據(jù)，那么第二訪問高速緩存的時(shí)候，可以命中`vector[0]`，依次命中后續(xù)兩個(gè)，直到需要`vector[4]`，出現(xiàn)了不命中，那么我們就需要重復(fù)上一步，再次讀取三個(gè)數(shù)據(jù)，依次類推直到結(jié)束。`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)上再回過頭思考多維數(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|
可以看出來，對(duì)于步長(zhǎng)而言，當(dāng)?shù)搅艘欢ǖ纳舷抟院?，每次的?qǐng)求都會(huì)不命中，那么這時(shí)候本層的高速緩存器相當(dāng)于作廢，時(shí)間全都耗費(fèi)在下層數(shù)據(jù)傳送到上層的時(shí)間，因?yàn)槊看巫x取都是不命中，可以利用上方的例子自己試著推理一下。

以上所說的每次讀取下一級(jí)別存儲(chǔ)器數(shù)據(jù)的時(shí)候，都是按照內(nèi)存對(duì)齊，來讀取的，如果你的內(nèi)存數(shù)據(jù)，例如讀取結(jié)構(gòu)體時(shí)，沒有放在內(nèi)存對(duì)齊的位置(此處所說的內(nèi)存對(duì)齊位置是以每次該級(jí)別存儲(chǔ)器讀取的大小為對(duì)齊倍數(shù)，而不是結(jié)構(gòu)體在內(nèi)存中存儲(chǔ)時(shí)的內(nèi)存對(duì)齊位置)，那么會(huì)將該位置的前后補(bǔ)齊倍數(shù)的起始位置來讀取

•     下一級(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)行讀取。

最新評(píng)論