如何更好地理解現代緩存對算法性能的影響？

Question

我讀了以下紙張：http://www-db.in.tum.de/~leis/papers/ART.pdf，並在其中，他們在抽象的說：

主內存容量已經長大到一個地步，大多數數據庫 適合到RAM中。對於主內存數據庫系統而言，索引結構 的性能是一個關鍵瓶頸。傳統的內存數據 結構像平衡二叉搜索樹在 現代硬件上效率不高，因爲它們沒有最佳利用CPU上的高速緩存。 也經常用於主內存索引的哈希表很快，但 僅支持點查詢。

我該如何更好地理解CPU上高速緩存的這種利用以及它如何影響特定數據結構/算法的性能？

剛開始的地方會很棒，因爲這種分析對我來說真的不透明，我不知道該從哪裏開始理解。

Answer 1

這將是一個非常基本的答案，因爲否則它將會非常廣泛。我也不是這方面的專家（拿起零散工作來幫助理解如何更好地優化我的熱點）。但它可能有助於您開始調查此主題。當計算機體系結構 課程只教有關的寄存器，內存和磁盤，同時在兩者之間的CPU緩存掩飾

_{的話題讓我想起我的大學時代我。 CPU緩存是當今性能最主要的因素之一。}

的計算機的存儲器被分成不等的絕對最大但最慢的（磁盤）的層次結構，以絕對最小但最快的（寄存器）。

下面的磁盤是DRAM，它仍然很慢。而上面的寄存器就是CPU高速緩存，非常快（尤其是最小的L1高速緩存）。

訪問一個節點

現在讓我們假設你要求一些數據結構以某種形式訪問內存，說像一棵樹或鏈接列表鏈接的結構，我們只是訪問一個節點。

_{請注意，爲了簡單起見，我正在顛倒存儲器訪問視圖。通常情況下，它首先將一條指令加載到一個寄存器中，並且該過程向後和向前轉移，而不僅僅是轉發。}

虛擬到物理（DRAM）

在這種情況下，除非該記錄被映射到物理存儲器，操作系統必須從虛擬存儲器的頁映射到DRAM的物理地址（這很嚇人，特別是在頁面錯誤涉及磁盤訪問的最壞情況下）。這通常是在相當大的塊中完成的（機器通過一小撮抓取內存），就像對齊的4千字節塊。所以我們最終爲這個節點抓取了一個大的舊的4千字節內存塊。

DRAM到CPU緩存

現在，這4 KB頁面物理映射，我們還是希望做一些與節點（大部分的操作都在寄存器級進行操作），所以計算機移動它通過CPU緩存層次結構（這很慢）。通常，所有級別的CPU高速緩存都具有相同的高速緩存行大小，例如英特爾的64字節高速緩存行。

要將內存從DRAM移動到這些CPU高速緩存中，我們必須從DRAM中抓取一大塊緩存行大小對齊的內存並將其移入CPU高速緩存。我們可能還必須逐漸清除CPU緩存層次結構中不同級別的某些數據，例如最近最少使用的內存。所以現在我們爲這個節點抓取一個64字節的對齊內存。

也許在這一點上，緩存行內存可能看起來像這樣。假設相關的節點數據是42，而???中的內容是圍繞它的不相關內存，這不是我們鏈接數據結構的一部分。

CPU緩存來註冊

現在我們繼續從CPU高速緩存內存到寄存器（這種情況非常迅速）。而在這裏，我們仍然以少數人的形式抓住記憶，但卻是一個非常小的記憶。例如，我們可能會抓取一個64位對齊的內存塊並將其移入通用寄存器。所以我們在這裏抓住「42」的內存並將其移入一個寄存器。

最後我們對寄存器進行一些操作並存儲結果，而結果通常會以它們的方式回退內存層次結構。

訪問一個其他節點

當我們在聯結構進入下一個節點，我們最終不得不潛在做一遍，只爲了看一個小小的節點的數據。緩存行的內容可能如下所示（22是感興趣的節點數據）。

我們可以看到潛在的多少無用功的硬件和操作系統的應用，從較慢的內存僅僅是爲了獲取它的前一個小蠅頭位移動的數據大，對齊的短語，以更快的內存驅逐。

這就是爲什麼所有單獨分配的小對象，如鏈接節點或不能連續表示用戶定義類型的語言，都不是非常緩存或頁面友好的原因。當我們遍歷它們並訪問它們的數據時，它們傾向於調用大量頁面錯誤並緩存未命中。也就是說，除非他們從內存分配器獲得幫助，內存分配器以更連續的方式分配這些節點（在這種情況下，數據或兩個或多個節點可能彼此相鄰並一起訪問）。

接觸與空間局部性

最高速緩存友好的數據結構往往是基於連續的陣列（它不必是一個巨大的陣列，但也許陣列連接在一起，例如，如爲展開列表的情況）。當我們遍歷數組，訪問的第一個元素，我們可能要做以上尚未描述的動作，我們也許能夠得到這個曾經的記憶被移動到一個高速緩存行：

現在我們可以遍歷數組並訪問所有元素，而它是機器上第二快的內存形式（L1高速緩存），只需在初始強制性高速緩存未命中/頁錯誤後將數據從L1高速緩存移動到寄存器即可。如果我們從17開始，我們有最初的強制性高速緩存未命中，但是可以訪問此高速緩存行中的所有後續元素，而不必重複上述運動。這是非常快的，電腦可以通過這些數據開火。

所以這是什麼，通過這部分的意思是：

傳統的內存中的數據結構，如平衡的二進制搜索 樹不在現代的硬件高效的，因爲他們沒有 優化利用上，CPU緩存。

注意，有可能使連接結構如樹和鏈表實質上更多的緩存友好比他們自然會使用自定義的內存分配器，但他們缺乏在基本的數據結構這一固有緩存友好水平。

另一方面，散列表往往是基於數組的連續表結構。他們可能使用鏈接和鏈接的存儲桶結構，但通過自定義分配器（由於哈希存儲桶內更簡單的順序存取模式，遠小於樹），也可以更容易地實現緩存高效。

因此，無論如何，這是一個有關該主題的簡要概述，有點過於簡化，但希望足以幫助開始。如果你想深入瞭解這個主題，關鍵字將是緩存/內存效率/優化和參考的局部性。