緩存陣列的局部性和分期複雜性

陣列通常比鏈接列表更快。這主要是由於數組的緩存局部性。我有兩個疑問：緩存陣列的局部性和分期複雜性

實際上，它比您在問題中提出的簡單模型複雜一點。

首先，您可能有多個緩存層（L1，L2，L3），每個緩存層具有不同的特性。尤其是，每個高速緩存的替換策略可以使用不同的算法作爲效率和複雜度（即成本）之間的折衷。

然後，所有現代操作系統實現虛擬內存機制。僅緩存數據和指令（這是L1..L3的用途）是不夠的，還需要緩存虛擬地址和物理地址（在TLB中，事務後備緩衝區）之間的關聯。

要理解地點的影響，您需要考慮所有這些機制。

問題1

的最小單元的存儲器之間交換和高速緩存是高速緩存行。通常，它是64個字節（但取決於CPU型號）。讓我們假設緩存是空的。

如果你迭代一個數組，你將支付每64個字節的緩存缺失。智能CPU（和智能程序）可以分析內存訪問模式並決定預取緩存中連續的內存塊以提高吞吐量。

如果您在列表上迭代，訪問模式將是隨機的，您可能會爲每個項目支付緩存未命中。

問題2

整個數組沒有查找到並在第一次訪問緩存帶來的。只有第一個緩存行是。

但是，還有另一個要考慮的因素：TLB。頁面大小取決於系統。典型值是4 KB。第一次訪問數組時，會發生地址轉換（並將其結果存儲在TLB中）。如果數組小於4 KB（頁面大小），則不需要執行其他地址轉換。如果它更大，則每頁翻譯一次就完成了。

將此與列表進行比較。多個項目適合在同一頁面（4 KB）的概率遠低於陣列。它們可以放入同一個緩存行（64字節）的概率非常低。

我認爲計算複雜性很困難，因爲可能還有其他因素需要考慮。但是，在這種複雜性中，你必須考慮高速緩存行大小（對於高速緩存未命中）和頁面大小（對於TLB未命中）。

問題3

緩存未命中是當定高速緩存行不在緩存中。它可能發生在L1，L2或L3級別。級別越高，代價越高。

當虛擬地址不在TLB中時，發生TLB未命中。在這種情況下，使用頁表格（昂貴）轉換爲物理地址，並將結果存儲在TLB中。

所以，是的，對於鏈表，您可能會支付更高數量的緩存和TLB未命中數組。

相關鏈接：

2015-08-10 14:44:20

回答