程式局部性原理感悟

對于程式局部性原理的感悟。

局部性原理

　　程式的局部性原理是指程式在執行時呈現出局部性規律，即在一段時間内，整個程式的執行僅限于程式中的某一部分。相應地，執行所通路的存儲空間也局限于某個記憶體區域。

　　局部性原理又表現為：時間局部性和空間局部性。

　　時間局部性是指如果程式中的某條指令一旦執行，則不久之後該指令可能再次被執行；如果某資料被通路，則不久之後該資料可能再次被通路。

　　空間局部性是指一旦程式通路了某個存儲單元，則不久之後。其附近的存儲單元也将被通路。

　　這一規律是是普遍事實的總結，更是許多計算機技術的前提假設，比如.NET中托管堆以及代齡的處理過程，便是基于這個認識。

　　之是以有這個規律，很多人認為原因是：程式的指令大部分時間是順序執行的，而且程式的集合，如數組等各種資料結構是連續存放的。對于這一點，我個人表示贊同。

　　程式的局部性原理是如此重要，以至于與程式設計的各個方面都存在密切的關系。

局部性與效率

　　熟悉代碼的局部性原理，并且按照這個思路去寫代碼，可以顯著的提高代碼的執行效率，先看下面的C#代碼：

static void Main(string[] args)
{
 int[,] a = new int[10000,10000];
 int sum = 0;
 // 按照先行後列的順序周遊二維數組，這是正常做法
 WriteTimes(() =>
 {
  for (int i = 0; i < 10000; i++)
  {
   for (int j = 0; j < 10000; j++)
   {
    sum += a[i, j];
   }
  }
 });
 // 按照先列後行的順序周遊二維數組，這是異常做法
 WriteTimes(() =>
 {
  for (int j = 0; j < 10000; j++)
  {
   for (int i = 0; i < 10000; i++)
   {
    sum += a[i, j];
   }
  }
 });
 
 Console.Read();
}
 
static void WriteTimes(Action func)
{
 DateTime dt0 = DateTime.Now;
 func();
 DateTime dt1 = DateTime.Now;
 Console.WriteLine((dt1 - dt0).Milliseconds);
}      

　　大家可以輸出一下，在我的機器上的輸出為(具體的數值可能不同，但是大小比例應該差不多)：

102
999      

　　這個例子本身并沒什麼實際的意義，但如果處理的資料量足夠大，并且可能需要頻繁的在外存、記憶體、緩存間排程，又注重效率的話，這個問題就有可能會被陡然放大了。不過，通常來說，效率總是在程式出現性能問題後才應該被關注的方面。

局部性與緩存

　　歸根結底，緩存(各種緩存技術，CPU緩存，資料庫緩存，伺服器緩存)探讨的也基本都是效率的問題，看另一個來源于網上某位仁兄的問題：

// 寫法一：循環内塞進好幾件事
for (int i = 0; i < 1000; i++)
{
 WriteIntArray();
 WriteStringArray();
}
// 寫法二：循環内隻幹一件事
for (int i = 0; i < 1000; i++)
{
 WriteIntArray();
}
for (int i = 0; i < 1000; i++)
{
 WriteStringArray();
}      

問：兩種寫法哪個好？

　　有的同學認為寫法一效率高，因為循環隻執行了一遍，而有的同學認為寫法二效率高，因為該寫法中每個循環内的局部變量大部分情況下是比寫法一少，這樣更容易利用CPU的寄存器以及各級緩存，這滿足局部性原理，是以效率較好。

　　我寫了簡單的程式驗證了一下，發現确實有時候寫法一執行時間較短，有時候寫法二執行之間較短，沒有明顯的固定規律，是以我認為這裡的效率一說不太明顯，當然了也許是這裡的循環次數比較少，循環多次的低效還沒有展現出來，感興趣的可以自己試一下大的循環。

　　即使是這樣的結果，我還是傾向于使用第二種寫法，這不是效率的原因，而是重構中，提倡一個循環隻幹一件事。

局部性與重構

　　重構的基本原理這裡就不多說了，感興趣的随便搜一下就可以了。重構的基本原則中就有諸如：一個循環隻幹好一件事，關聯性強的代碼放到一起，變量定義在使用的地方等等。這些原則與局部性原理闡述的規律竟然是如出一轍。

　　看一些我認可的寫法：

// 一個循環内隻幹好一件事
for (int i = 0; i < 1000; i++)
{
 WriteIntArray();
}
for (int i = 0; i < 1000; i++)
{
 WriteStringArray();
}
 
// 原始的代碼
List<int> salaryList = new List<int>();
List<int> levelList = new List<int>();
List<int> scoreList = new List<int>();
 
collectHighSalary(salaryList);
collectHighLevel(levelList);
collectHighScore(scoreList);
 
collectMiddleSalary(salaryList);
collectMiddleLevel(levelList);
 
collectLowSalary(salaryList);
collectLowlevel(levelList);
// 重構成：
// 有關系的代碼放到一起
// 變量需要時再定義
List<int> salaryList = new List<int>();
collectHighSalary(salaryList);
collectMiddleSalary(salaryList);
collectLowSalary(salaryList);
 
List<int> levelList = new List<int>();
collectHighLevel(levelList);
collectMiddleLevel(levelList);
collectLowlevel(levelList);
 
List<int> scoreList = new List<int>();
collectHighScore(scoreList);        

　　局部性原理不僅與語句和函數的組織方式息息相關，還與元件的組織方式互相呼應。

局部性與高内聚

　　從元素(函數，對象，元件，乃至服務)設計的角度，内聚性是描述一個元素的成員之間關聯性強弱尺度。如果一個元素具有很多緊密相關的成員，而且它們有機的結合在一起去完成有限的相關功能，那這個元素通常就是高度内聚的。高内聚的設計是一種良好的設計。

　　耦合性從另一個角度描述了元素之間的關聯性強弱。元素之間聯系越緊密，其耦合性就越強，元素的獨立性則越差，元素間耦合的高低取決于元素間接口的複雜性，調用的方式以及傳遞的資訊。低耦合的設計是一種良好的設計。

　　一個具有低内聚，高耦合的元素會執行許多互不相關的邏輯，或者完成太多的功能，這樣的元素難于了解、難于重用、難于維護，常常導緻系統脆弱，常常受到變化帶來的困擾。

　　毫無疑問，遵循良好的局部性原理通常能得到良好的高内聚低耦合元素，反之，代碼中元素的高内聚低耦合也使的局部性得以大大加強，此所謂相得益彰。

局部性與命名

　　說到命名，不得不提著名的匈牙利命名法。

　　在我讀了《軟體随想錄：程式員部落酋長Joel談軟體》一書之前，我認為的匈牙利命名法則就是在駝峰式命名的基礎上，在變量名前加上變量的類型，例如iLength表示int型的表示長度的變量。

　　但是在我閱讀了《軟體随想錄》一書相關的章節以後，才徹底的了解到其中的誤解。原來微軟那位大牛推薦的匈牙利命名法居然不是我想的那樣。

　　在該書中，作者将匈牙利命名法分為兩種，流行的并且被廢掉的叫“系統型匈牙利命名法則”，這種命名法将變量類型加到了變量名字前面，老實說确實沒什麼意義，特别是在現代編輯器中。

　　事實上，微軟那位仁兄推薦的是叫做“應用型匈牙利命名法則”的規則，那就是把變量的應用場景加到變量的名字前面。

　　比如在頁面開發中，直接從使用者輸入得到的Name字元串可以起名叫：usName，其中us代表unsafe，意思是這個字元串是使用者輸入的，沒用經過編碼處理，可能是不安全的。而經過編碼的Name字元串可以起名叫sName，其中s代表safe，意思是這個字元串經過了編碼處理，是安全的。

　　談到命名的規則，就是為了說明下面這個息息相關的問題：代碼錯誤檢查。

　　代碼錯誤檢查也是一個經典的話題，如何讓代碼的錯誤提前暴露出來，而不是釋出後由客戶去發現，這是個問題。

　　滿足局部性原理，使得我們的程式内聚性通常很好，但是毫無疑問，有些元素還是必須要貫穿很多的行的，比如在某些函數中，定義變量和末次使用變量的地方可能相差幾十行：

var usName = getName();
action1(usName);
// 此處省略20行...
sName = usName;
// 此處省略10行...
document.write(sName);      

　　我不得不承認，Joel老兄提出的“應用型匈牙利命名法則”還是相當有作用的。比如中間那行：

sName = usName;      

　　我們很容易就會從變量名發現這行代碼存在安全性威脅。

我們其實生活在世界的局部中

　　推而廣之，局部性原理不僅僅是适用于程式的理論，而是适用于我們生活的各個方面的重要規律，它的稱呼向來随着場合的不同而有所變化，比如有時叫“習慣”，有時叫“慣性”，有時又演化成“熟悉的人/事”等。總之，我個人認為，人總是傾向于在局部的、連續的時間空間内做相關的、熟悉的事情，程式其實是人類做事風格的反應。