來源：資料結構、算法與應用 C++語言描述（原書第2版）
簡單計算機模型
我們來看一個簡單的計算機模型，它的存儲由一個一級緩存 L1（level 1）、一個二級緩存 L2 和主存構成。算術和邏輯操作由算術和邏輯單元（ALU）對存儲在寄存器（R）中的資料進行處理來完成。下圖是這個計算機模型的一部分。
通常，主存的大小是幾十或幾百 MB；二級緩存的大小不足 1MB；一級緩存的大小是幾十 KB；寄存器的數量在 8 和 32 之間。程式開始運作時，所有資料都在主存。
要執行一個算術運算，例如加法，首先把相加的資料從主存移到寄存器，然後把寄存器的資料相加，最後把結果寫入主存。
我們把寄存器的資料相加所需要的時間作為一個周期。把一級緩存的資料送到一個寄存器所需要的時間是兩個周期。如果需要的資料沒有在一級緩存，而是在二級緩存，即一級緩存未命中，那麼把需要的資料從二級緩存送到一級緩存和寄存器需要 10 個周期。當需要的資料沒有在二級緩存，即二級緩存未命中時，把需要的資料從主存複制到二級緩存、一級緩存和寄存器需要 100 個周期。我們把寫操作，甚至向主存的寫操作，算作一個周期，因為不需要等到寫操作完成之後再進行下一個操作。
緩存未命中對運作時間的影響
在我們的簡化計算機模型中，語句 a=b+c 編譯後的機器指令是
load a;load b;add; store c;
其中，load 操作把資料送到寄存器，store 操作把相加後的結果送到主存。add 和 store 操作共需要兩個周期。兩個 load 操作可能需要 4 個周期至 200 個周期不等，這取決于資料是否在緩存中，即緩存是否命中。是以，語句 a=b+c 所需要的總時間從 6 個周期到 202 個周期不等。在實際操作中，時間差别沒有這麼極端，因為可以把連續的緩存未命中所花費的時間交叉處理。
假定有兩個類型相同的算術運算。第一個算術運算是 2000 次加法，它需要 4000 次 load 操作、2000 次 add 操作和 2000 次 store 操作。第二個算術運算是 1000 次加法。第一個算術運算的資料通路有 25% 的 load 操作出現一級緩存未命中，另有 25% 的 load 操作出現二級緩存未命中。在我們這個簡化的計算機模型中，第一個算術運算所需要的時間是 2000*2（有 50% 的 load 操作是緩存命中）+1000*10（有 25% 的 load 操作出現一級緩存未命中）+1000*100（有 25% 的 load 操作出現二級緩存未命中）+2000*1（用于 adds）+2000*1（用于 stores）=118000 個周期。如果第二個算術運算有 100% 的二級緩存未命中，它的用時 =2000*100（有 100% 的二級緩存未命中）+1000*1（adds）+1000*1（stores）=202000 個周期。第二個運算的量是第一個的一半，但實際用時卻比第一個多 76%。
為了減少緩存未命中的數量，進而減少程式的運作時間，計算機采用了一些政策，比如，把最近需要處理的資料預載到緩存中，當出現一個緩存未命中時，把需要的資料和相鄰位元組中的資料裝入緩存中。當連續的計算機操作使用的是相鄰位元組的資料時，這個政策很有效。
雖然我們的讨論集中在如何用緩存來減少通路資料的時間問題上，但是我們也用緩存來減少通路指令的時間。
矩陣乘法
也許有人不相信，在一台商用計算機上，一個操作多的程式可能比一個操作少的程式實際用時要少。本節就是要讓這些人相信，确有此事。
我們從一個實際的程式入手，程式 2-22 如下
// 程式 2-22
template<class T>
void squareMatrixMultiply(T** a, T** b, T** c, int n)
{ // 将 n × n 矩陣 a 和 b 相乘得到矩陣 c
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
T sum = 0;
for (int k = 0; k < n; k++)
sum += a[i][k] * b[k][j];
c[i][j] = sum;
}
}
它是把兩個用二維數組描述的方陣相乘。計算如下所示：
c [ i ] [ j ] = ∑ k = 1 n a [ i ] [ k ] ∗ b [ k ] [ j ] , 1 ⩽ i ⩽ n , 1 ⩽ j ⩽ n c[i][j]=\sum^n_{k=1}a[i][k]*b[k][j],\quad 1\leqslant i\leqslant n,1\leqslant j\leqslant n c[i][j]=k=1∑na[i][k]∗b[k][j],1⩽i⩽n,1⩽j⩽n
（你不了解矩陣乘法沒關系，這不影響你對我們要說明的問題的了解。）程式 2-22 是一段标準代碼，你在很多教科書上都可以找到。程式 4-4 是另一段代碼，它和程式 2-22 一樣，産生一個二維數組 c。我們來觀察程式 4-4。它有兩層嵌套的 for 循環，這是程式 2-22 所沒有的，這使它對數組 c 的索引處理得更多一些。其餘的操作都一樣。
// 程式 4-4
void fastSquareMatrixMultiply(int** a, int** b, int** c, int n)
{
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
c[i][j] = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
c[i][j] += a[i][k] * b[k][j];
}
你會發現，把程式 4-4 的三層嵌套 for 循環重新排列一下順序，結果是不變的。我們把程式 4-4 的嵌套循環順序稱為 ijk。當我們把第二層和第三層的 for 循環交換次序，我們得到的嵌套循環順序是 ikj。一共有 3!=6 種嵌套循環順序。由 6 種嵌套循環順序分别生成的函數都以同樣的數量執行每一種類型的操作。是以你也許認為這些函數所需的運作時間也是相同的。但是錯了。改變了循環的次序，也就改變了資料通路模式，進而改變了緩沖區未命中的數量，最終影響了運作時間。
在 ijk 順序中，數組 a 和 c 的元素是按行通路的，數組 b 的元素是按列通路的。因為同行的元素在存儲中是相鄰的，而同列的元素在存儲中是分開的，是以當數組很大，以至三個數組不能同時存儲在二級緩存 L2 中的時候，通路數組 b 可能導緻很多二級緩存未命中的事件。在 ikj 的順序中，數組 a、b 和 c 的元素是按行通路的，是以二級緩存未命中的事件就比較少，是以所需時間也比較少。
上圖給出了程式 2-22 和程式 4-4 分别使用 ijk 順序和 ikj 順序時的運作時間（以秒為機關）。下圖顯示的是标準運作時間，即一個函數的運作時間除以在 ikj 順序下執行的時間。
多麼神啊！ikj 順序要比 ijk 順序和程式 2-22 運作快。實際上，當 n=500 時，ikj 順序所需要的時間僅是 ijk 順序的 1/3，是程式 2-22 的 1/2；當 n=1000 時，比率近似是 7/16 和 1/4；當 n=2000 時，比率近似是 1/13 和 1/16。記住，按操作步數計算，ikj 順序比程式 2-22 和 ijk 順序所執行的操作要多。隻有 ikj 順序的運作時間是按照漸進分析的比率 Θ ( n 3 ) \Theta(n^3) Θ(n3)增長的。ijk 順序和程式 2-22 的運作時間是受緩沖未命中事件所控制的，而不受執行步數所控制。
存儲等級制對代碼性能的影響随着程式語言、編譯器、編譯器選項和計算機配置的變化而變化。例如，2.4GHz Intel Pentium IV PC 的二級緩存比 1.7GHz PC 的二級緩存大一倍，上述圖中所給出的矩陣乘法的時間是用後者實驗得來的，如果用前者實驗，那麼當 n=500 時，比率大約是 9/16 和 2/5；當 n=1000 時，比率大約是 1/2 和 1/3；當 n=2000 時，比率大約是 1/4 和 1/5。