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

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

對于此，我們可以暫且忽略CPU的設(shè)計，因為我們在層面上只能考慮如何迎合編譯器的優(yōu)化規(guī)則，而CPU則是語言以及編譯器的事情了。

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

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

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

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

對于當下的編譯器，以GCC(GCC不僅僅是一個編譯器，但這里將它當成編譯器的代名詞)為例，-O2是一個為大眾所接受的優(yōu)化等級，對于其他編譯器，一般程序員可以選擇使用由Google和Apple聯(lián)合開發(fā)的編譯器clang也是一個很好的選擇， 在-O2的優(yōu)化等級下，GCC一般情況下能夠自動執(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; 

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

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

 /*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ù)，get_len和mix_cal分別用來得到data_t長度，以及計算數(shù)據(jù)域的總和。

 /*main.c*/ 
 int main(void)
 {
  block* block_in_all[ARR_SIZE] = { NULL };
  int result_in_all[ARR_SIZE] = { 0 };
  /*
  * 假設(shè)生成了許多的`block`類型對象
  * 將許多的`block`放置在一個數(shù)組中，每個元素類型為`block*`
  * 每個block對象中都包含非空的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;
 }

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

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

 int len = get_len(process->storage);

.

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

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

循環(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)展開。

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

 data* local_data = process->storage;

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

以及對于外部存儲位置 result 我們在此處也是存在著浪費，同樣我們應該使用一個臨時變量來存儲總和，而不是每次得到結(jié)果便對它進行解引用操作。

 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)展開，自然是有的，對于一個n次循環(huán)展開的式子我們有一個簡便的上界確定公式即:

 reality = len - n + 1;

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

 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)展開將元素相加分為兩個部分，第一部分每次加兩個元素，由于如此做會剩余元素沒有加，故在第二部分將剩下的元素都加起來。

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

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

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

命令式：

 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;
 }

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

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

. 多路并行的技巧也是一個很重要的思路，可能在很多人眼中看來，兩條語句依次寫出和合并的效果一定是一樣。但是多路并行有一個缺點就是對寄存器的數(shù)量有所要求，當寄存器不夠時(稱為溢出)，性能不升反降。同樣是對于循環(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];
 }//也可以分成四路并行，每一路存一個。這種做法充分利用了CPU流水線的性能
 for(;i < len;++i)
  local_result_1 += local_data[i];

 *result = local_result_1 + local_result_2;

Tips:

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

其實這是因為你根本就沒有理解C語言工程這個意思，大部分人是這么測試的:

首先在一個文件夾里創(chuàng)建兩個文件 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();   //編譯通過，可以運行。
  return 0;
 }

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

好吧，實際上是前輩們以及教材的錯，因為從始至終，所有外界現(xiàn)象都告訴我們C程序是獨立的一個一個文件組成的，但是并沒有告訴我們要先將他們弄成一個工程！此處如果是使用Visual Studio學習C語言的可能會對工程這個概念理解的稍微好一些，雖然不推薦使用 VS 學習C語言。

你想要實現(xiàn)static函數(shù)僅在本文件可見的效果，請你先補習一下工程這個概念，對于任何可見或者不可見的概念而言都是建立在一個工程內(nèi)而言，而不是像上方的代碼，使用#include來表示，你都#include了，那還有什么可見不可見的當然都可見了。所以一個static函數(shù)可見于不可見是基于一個個工程里的所有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();   //報錯，因為test是static函數(shù)。
  return 0;
 }

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

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

注：存儲器山就是對于不同步長不同大小文件的讀取速率的三維坐標圖，形似一座山，z軸為速率，x軸為步長，y軸為文件大?。ㄗ止?jié)），某些主流的測評軟件便是這個原理(將存儲器山的圖像進行一下簡單的變換，就能得到哪些軟件呈現(xiàn)的效果圖像)。

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

當時我們并未深究，由于我們慣性的認為計算機的運作方式和人類的運作方式一致，也在過往的經(jīng)驗中認為計算機一定是在任何方面超越人類的存在，但是實際上，計算機除了在重復計算方面比人類的速度要快速以外，其他方面遠遠落后于人類的大腦，即便是我們最稀疏平常的視覺識別(看東西識別物體)，在計算機看來都是一門極其高深的領(lǐng)域，所以我們現(xiàn)在的時代的計算機還處于起步狀態(tài)，在這種時代里，程序員的作用是無可替代的，同樣程序員的一舉一動關(guān)乎計算機的命運。

可能在很多的方面，都已經(jīng)接觸了一臺計算機的主要組成構(gòu)造，和程序員最息息相關(guān)的便是CPU，主存以及硬盤了，可能到現(xiàn)在為止很多程序員仍然認為編程序和這些存儲器有什么關(guān)系？然而一個程序員，特別是編寫C語言程序的程序員，最大的影響因素便來自于此，在計算機的存儲器結(jié)構(gòu)中，分為四種層次:
CPU寄存器、高速緩存器、主存、硬盤。

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

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

前方提到了局部性，局部性體現(xiàn)在了，當步長越大，空間局部性越低，大多數(shù)情況下會造成性能降低，比如最常見的多維數(shù)組循環(huán)(我鮮少使用多維數(shù)組的原因之一便在于此)，前面說過多維數(shù)組實際上只是數(shù)個一維數(shù)組的包裝而已，C語言中并沒有真正的多維數(shù)組，而是將其解讀成內(nèi)存中的一維的連續(xù)內(nèi)存，但是當我們遍歷它的時候，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進行遍歷，這就導致了程序必須在內(nèi)存塊中無規(guī)律的跳動，這里的無規(guī)律是計算機認為的無規(guī)律，雖然在我們看來的確是有跡可尋，優(yōu)秀的編譯器能夠?qū)λM行優(yōu)化處理。就事論事，即這段程序的空間局部性比較差，對于一個在內(nèi)存中大幅度跳躍，無規(guī)律跳躍的程序都將影響程序的性能。這個判定對于一個連續(xù)的內(nèi)存塊來說是很重要的，比如C語言中的結(jié)構(gòu)體。

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

在此處回顧一下C語言的結(jié)構(gòu)體性質(zhì)與知識：
對于任意一個完整定義的結(jié)構(gòu)體，每一個對象所占有的內(nèi)存大小都符合內(nèi)存對齊的規(guī)則。
對于結(jié)構(gòu)體內(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ū)⑵洚斪饕粋€整體，但是實際上他們與內(nèi)建(build-in)的類型還是有一些差異的。
偏移量通俗地說，就是該成員起始地址距離起始位置的長度，在結(jié)構(gòu)體中，C語言是怎么為結(jié)構(gòu)體分配設(shè)定大小的呢？除了內(nèi)存對齊外，還需要考慮定義結(jié)構(gòu)體時，其中成員的聲明順序，換句話說，誰首先聲明，誰的位置就靠前。而某個成員的偏移量代表著其起始位置減去其所屬對象的起始位置，(此處需要注意的是，兩個毫不相干的指針相減所得到的結(jié)果是無意義的，只有當兩個指針同在一個作用域內(nèi)時，減法才是有意義的，為了避免潛在的錯誤，我們要謹慎使用指針減法操作)。
就此回過頭去再看看上方的 loop 解釋，應該能夠理解到，那些數(shù)字是通過偏移量來進行計算得到的。

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

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

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

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

高速緩存器的各個層依然遵守逐步降速的規(guī)律，即讀取周期 L1 < L2 < L3，而影響較大的便是上文提到的的命中率，我們知道越上層的高速緩存器總是將下層的存儲器映射在自己的存儲器中，而按照邏輯推斷，上層的實際空間比下層的要小，因為上層的空間更加寶貴速度更快，這就導致我們無法將下層的空間一一對應的映射到上層里，那么我們就想到一個辦法，并不是將下層存儲器的內(nèi)容完全映射到上層，而是上層有選擇性的將下層的部分內(nèi)容抽取到上層，這便是不命中之后的操作。

對于CPU從存儲器中讀取數(shù)據(jù)這個操作，如果我們使用了高速緩存以及內(nèi)存這兩個概念，那么就會有一個延伸概念，命中。而對于這個概念只有兩種情況，命中或者不命中。而對于一個初始化的高速緩存器，它一定是空的，也許在物理意義上它并不是空，但是實際上在程序看來它的確是空的，為了區(qū)分這個，高速緩存器專門使用了一個位(bit)來表示此組是否有效(即是否為空)，既然它是空的那么，我們第一次無論如何都無法命中數(shù)據(jù)，這時候該層的高速緩存器就會向下一層，在該層中尋找所要的數(shù)據(jù)，每次要向下一層申請尋找的行為一般稱為懲罰，而當我們從存儲器中將所需的數(shù)據(jù)加載到高速緩存器中的時候，我們便開始了運算，而一切關(guān)于高速緩存器效率的改進都集中在命中率的提升。

假設(shè)有一個數(shù)組需要操作，由于數(shù)組是一個連續(xù)的內(nèi)存空間，對其進行步長為1的操作擁有很好的空間局部性，那么可以當成一個很好的例子，在高速緩存器看來讀取一個有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)了不命中，那么我們就需要重復上一步，再次讀取三個數(shù)據(jù)，依次類推直到結(jié)束。`vector:|[0]|[1]|[2]|[3]|[4]|[5]|[6]|[7]|[]|[]|[]|`

現(xiàn)在我們能夠從一定層面上解釋為什么局部性好的程序比局部性差的程序要有更好的效率了，原因就在對于高速緩存器的利用，**首先反復利用本地臨時變量能夠充分的調(diào)用高速緩存器的功能做到讀寫的最優(yōu)化，其次步長為越小也越能盡最大的能力發(fā)揮高速緩存器讀取的數(shù)據(jù)**，在這點上再回過頭思考多維數(shù)組的遍歷并進行操作，如果沒有考慮空間局部性(即先操作大塊，再操作小塊)，那么在高速緩存器中，它的不命中率令人發(fā)指，這也是操作不當效率低的原因。
另一方面，對于不同步長而言，其影響的也是高速緩存器的命中率，還是上方的vector

    步長       | 1 | 2 | 3 | 4 | 5 |
    不命中/命中 |1/4|1/2|2/3|1/1|1/1|
可以看出來，對于步長而言，當?shù)搅艘欢ǖ纳舷抟院?，每次的請求都會不命中，那么這時候本層的高速緩存器相當于作廢，時間全都耗費在下層數(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ù)進行讀取。