基于CPU訪存局部性原理下的矩陣乘法實作

　　細看一番就會發現這兩種實作語義是等價的，但是後者的實際運作效率卻比前者高。

　　那為什麼會如此呢？

　　那是因為CPU讀資料時，并不是直接通路記憶體，而是先檢視緩存中是否有資料，有的話直接從緩存讀取。而從緩存讀取資料比從記憶體讀資料快很多。

　　當資料不在緩存中時，CPU會将包含資料在内的一個資料塊讀到緩存，如果程式具有良好空間局部性，那麼第一次cache miss後，之後的幾次資料通路就可以直接在緩存中完成。除了空間局部性（程式傾向于引用與目前資料鄰近的資料）之外，還有時間局部性（程式傾向于引用最近被引用過的資料）。

回到矩陣乘法。（我們隻考慮内循環）

　　前者對矩陣A，有良好的空間局部性，假設一次能緩存四個元素，則每次疊代對于A隻有0.25次miss，但是對于B，則不然，是以B是按列通路的，每次通路都會miss，是以每次疊代總的miss數是1.25。後者對于矩陣C和矩陣B都有良好的局部性，每次疊代都隻有0.25詞miss，是以總的miss數是0.5。後者每次疊代多了一次存儲（對C[i][j]寫入），但是即便如此，後者的運作效率也比前者高。 

　　總而言之，要想程式跑得快，就要在程式中多利用局部性，讓緩存hold住你的資料，減少訪存次數。要知道CPU可以在3個時鐘周期内通路到L1 cache，10個時鐘周期左右的時間通路到L2 cache。通路記憶體卻要上百個時鐘周期，孰快孰慢，很清楚了吧？

​