CPU的局部性原理非常大的影響到了程序的性能髓需，很多性能調(diào)優(yōu)的場景就跟這個相關(guān)。比如說：Cacheline房蝉，字節(jié)對齊僚匆，甚至這個原理影響了編程語言的設(shè)計。程序員需要掌握這個知識來理解編程語言與CPU的結(jié)構(gòu)搭幻。
介紹一些事實
- 用數(shù)組在任何情況下的效率都要比用鏈表高咧擂；
- 程序中應(yīng)該多用循環(huán)少用遞歸
- 二維數(shù)組必須先循環(huán)行，再循環(huán)列檀蹋；
- Cacheline就是根據(jù)這個原理設(shè)計的松申，理解了局部性原理可以理解為啥有“偽共享”以及怎么讓變量常駐一個Cacheline中。
原理簡單但是推論多
局部性原理分類
-
時間局部性：n時刻cpu訪問過的代碼與數(shù)據(jù)在n+1的時刻還會被訪問 -
空間局部性：m位置cpu訪問過的代碼與數(shù)據(jù)，則[m,m+n]位置的數(shù)據(jù)也會馬上被訪問到贸桶，簡單講就是一旦訪問了一個地址舅逸，那么鄰居都要準備好被訪問餐抢。
舉個例子：
int i;
int array[N] = {0}
for(i=0;i<N;j++){
array[i] =1;
}
先看看空間局部性
數(shù)組可以說是編程語言里面比較常用的結(jié)構(gòu)了（hash table就是用數(shù)組特性實現(xiàn)的匙头，你想想用得多不多）。根據(jù)空間局部性原理甸祭，當CPU訪問到i=0的元素時设联，i+n個字節(jié)其實已經(jīng)從內(nèi)存被加載到CPU緩存了（CPU訪問內(nèi)存的金字塔結(jié)構(gòu)這里默認大家都知道了善已，不知道看這里 - Numbers Everyone Should Know小節(jié)）。接下來訪問i=1,i=2,i=3....i=n都不需要再去訪問內(nèi)存了离例，因為都被
CPU cache了换团，這就是空間局部性原理的使用。接著上面的宫蛆，n就是CPU一次cache多大的范圍合適呢艘包？現(xiàn)在x64CPU就是64個字節(jié)，這個cache也有個專屬名字——
cacheline耀盗。至于為啥是64個字節(jié)想虎，應(yīng)該是個經(jīng)驗值，這個大小對緩存程序叛拷，數(shù)據(jù)的粒度剛剛好吧舌厨，不糾結(jié)。還有很多數(shù)據(jù)都是經(jīng)驗數(shù)據(jù)忿薇，比如OS的頁大小4k等等裙椭。-
接著看鏈表，鏈表這種數(shù)據(jù)結(jié)構(gòu)的優(yōu)點是靈活署浩，可以用O(1)做插入與刪除揉燃，也就是擴容性能不錯，可以應(yīng)對未知大小的數(shù)據(jù)需求筋栋，但是根據(jù)
空間局部性原理炊汤，隨機訪問性能就被拉低了，看看圖：
數(shù)組VS鏈表
套用分布式緩存的概念弊攘，鏈表這種數(shù)據(jù)結(jié)構(gòu)更容易導(dǎo)致CPU的緩存被擊穿抢腐。所以C++語言的作者都推薦大家在任何情況下都不要使用鏈表。(出處已經(jīng)忘記了……)肴颊。那么怎么利用數(shù)組做出可以靈活添加與刪除元素的結(jié)構(gòu)呢氓栈？答案是——ringbuffer。
然而鏈表并沒有消失婿着，因為數(shù)組的原罪動態(tài)擴容沒有解決授瘦，所以導(dǎo)致兩個后果：
3.1.Hashtable在任何語言實現(xiàn)下對于擴容的性能都非常不友好醋界，特別是在多核CPU多線程并發(fā)情況下尤其消耗性能，導(dǎo)致在很多讀寫相當提完，性能critcal的場景下hashtable不是一個理想的選擇形纺。因為會抖動，所以不是一種穩(wěn)定的數(shù)據(jù)結(jié)構(gòu)徒欣。例子：linux中很少用hashtable對未知大小的數(shù)據(jù)做檢索逐样，轉(zhuǎn)而使用紅黑樹；redis用跳表做zset的實現(xiàn)打肝。這都用了鏈表的特性脂新。
3.2. 啟示——在工程上有些瓶頸是不要試圖去突破的，比如鏈表與數(shù)組粗梭，你不要期望可以設(shè)計出一種完美的數(shù)據(jù)結(jié)構(gòu)來解決所有的問題争便，永遠都是去做權(quán)衡，而不是盲目自信去做無謂的浪費断医。有很多例子都是經(jīng)過數(shù)學證明的滞乙，不要試圖去突破，比如CAP鉴嗤，比如排序算法的效率斩启。 一個需要優(yōu)化的代碼例子（當然這里的n與m要足夠大，越大越明顯）：
int a[n][m];
for(int i=0; i<m;i++){
for(int j=0;j<n;j++){
a[j][i] =1;
}
}
這個例子的意思是先訪問列再訪問行醉锅，訪問的步長是n個元素兔簇，如果n等于16，就正好跨過了一個緩存行硬耍，正好j每++一次就導(dǎo)致一次CPU緩存被擊穿男韧，性能就巨差。正確的代碼：
int a[n][m];
for(int i=0; i<n;i++){
for(int j=0;j<m;j++){
a[i][j] =1;
}
}
所以默垄，在寫代碼時，要多想想CPU甚纲，多想想操作系統(tǒng)才能寫出性能優(yōu)秀的代碼口锭。
時間局部性
- 時間局部性簡單說就是訪問過的代碼、數(shù)據(jù)還會馬上被訪問到介杆。為什么有這個結(jié)論呢鹃操？你如果感興趣的話，可以看看你家的代碼庫中春哨，或者開源軟件的源代碼中荆隘，是不是循環(huán)語句最多？或者不較真的說赴背，循環(huán)代碼最重要椰拒。為什么呢晶渠？
1.1. 因為算法都是要被寫成循環(huán)或者遞歸形式的，不能用循環(huán)或者遞歸實現(xiàn)的算法不存在燃观；
1.2. 這叫做程序的可停止性褒脯，這是圖靈的主要功績，圖靈證明了任何計算都是可以用圖靈機在有限步里面完成的缆毁。 -
循環(huán)代碼就是時間局部性原理的基礎(chǔ)番川。因為一個循環(huán)如果被CPU cache住了，就不用去內(nèi)存加載了脊框，從而提高了程序的運行效率颁督。
3、啟示——性能好的程序往往會寫成循環(huán)的代碼而不是遞歸浇雹。遞歸函數(shù)調(diào)用是高級語言的特性沉御，但是它涉及到代碼從一個點反復(fù)的跳轉(zhuǎn)到不同的代碼段，會導(dǎo)致cpu cache bouncing箫爷，程序性能會波動嚷节；
循環(huán)vs遞歸 - 啟示2——人越容易看懂的代碼對機器也越不友好。在算法設(shè)計中虎锚，遞歸法是人能看懂的最好編碼的形式硫痰，但是實際運行的效率不高；相反如果寫成循環(huán)形式窜护，人雖然理解起來有困難效斑，但是機器十分友好，如：
void preOrder1(BinTree *root) //遞歸前序遍歷
{
if(root!=NULL)
{
cout<<root->data<<"";
preOrder1(root->lchild);
preOrder1(root->rchild);
}
}
void preOrder2(BinTree *root) //非遞歸前序遍歷
{
stack<BinTree*> s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
cout<<p->data<<"";
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
s.pop();
p=p->rchild;
}
}
}
所以還是那樣柱徙，自然界的這種蹺蹺板很多缓屠，一個東西有好的方面也肯定有其不足之處，這是很正常的护侮。
認識到事物的邊界才算是真正認識到了它敌完。
總結(jié)
計算機硬件與軟件的性能都會受到局部性原理的限制，而局部性原理又分為空間與時間局部性兩個維度羊初，正是這兩個約束（枷鎖）使得我們的計算機世界長成了現(xiàn)在這個樣子滨溉；而程序員懂得其中的基本概念，在寫代碼的時候能夠有點印象就已經(jīng)可以了长赞。
