如何計(jì)算矩陣乘法，這個(gè)大家都知道。通常情況下，我們都是用以下代碼實(shí)現(xiàn)的：

那為什么會(huì)如此呢？

那是因?yàn)镃PU讀數(shù)據(jù)時(shí)，并不是直接訪問內(nèi)存，而是先查看緩存中是否有數(shù)據(jù)，有的話直接從緩存讀取。而從緩存讀取數(shù)據(jù)比從內(nèi)存讀數(shù)據(jù)快很多。

當(dāng)數(shù)據(jù)不在緩存中時(shí)，CPU會(huì)將包含數(shù)據(jù)在內(nèi)的一個(gè)數(shù)據(jù)塊讀到緩存，如果程序具有良好空間局部性，那么第一次cache miss后，之后的幾次數(shù)據(jù)訪問就可以直接在緩存中完成。除了空間局部性（程序傾向于引用與當(dāng)前數(shù)據(jù)鄰近的數(shù)據(jù)）之外，還有時(shí)間局部性（程序傾向于引用最近被引用過的數(shù)據(jù)）。

回到矩陣乘法。（我們只考慮內(nèi)循環(huán)）

前者對(duì)矩陣A，有良好的空間局部性，假設(shè)一次能緩存四個(gè)元素，則每次迭代對(duì)于A只有0.25次miss，但是對(duì)于B，則不然，因此B是按列訪問的，每次訪問都會(huì)miss，因此每次迭代總的miss數(shù)是1.25。

后者對(duì)于矩陣C和矩陣B都有良好的局部性，每次迭代都只有0.25詞miss，因此總的miss數(shù)是0.5。后者每次迭代多了一次存儲(chǔ)（對(duì)C[i][j]寫入），但是即便如此，后者的運(yùn)行效率也比前者高。

總而言之，要想程序跑得快，就要在程序中多利用局部性，讓緩存hold住你的數(shù)據(jù)，減少訪存次數(shù)。要知道CPU可以在3個(gè)時(shí)鐘周期內(nèi)訪問到L1 cache，10個(gè)時(shí)鐘周期左右的時(shí)間訪問到L2 cache。訪問內(nèi)存卻要上百個(gè)時(shí)鐘周期，孰快孰慢，很清楚了吧？