深入解析面向數據的哈希表性能

最近幾年中，面向數據的設計已經受到了很多的關注 —— 一種強調內存中數據布局的編程風格，包括如何訪問以及將會引發多少的 cache 缺失。由於在內存讀取操作中缺失所佔的數量級要大於命中的數量級，所以缺失的數量通常是優化的關鍵標準。這不僅僅關乎那些對性能有要求的 code-data 結構設計的軟體，由於缺乏對內存效益的重視而成為軟體運行緩慢、膨脹的一個很大因素。

高效緩存數據結構的中心原則是將事情變得平滑和線性。比如，在大部分情況下，存儲一個序列元素更傾向於使用普通數組而不是鏈表 —— 每一次通過指針來查找數據都會為 cache 缺失增加一份風險；而普通數組則可以預先獲取，並使得內存系統以最大的效率運行。

如果你知道一點內存層級如何運作的知識，下面的內容會是想當然的結果——但是有時候即便它們相當明顯，測試一下任不失為一個好主意。幾年前 Baptiste Wicht 測試過了std::vector vs std::list vs std::deque，（後者通常使用分塊數組來實現，比如：一個數組的數組）。結果大部分會和你預期的保持一致，但是會存在一些違反直覺的東西。作為實例：在序列鏈表的中間位置做插入或者移除操作被認為會比數組快，但如果該元素是一個 POD 類型，並且不大於 64 位元組或者在 64 位元組左右（在一個 cache 流水線內），通過對要操作的元素周圍的數組元素進行移位操作要比從頭遍歷鏈表來的快。這是由於在遍歷鏈表以及通過指針插入/刪除元素的時候可能會導致不少的 cache 缺失，相對而言，數組移位則很少會發生（對於更大的元素，非 POD 類型，或者你已經有了指向鏈表元素的指針，此時和預期的一樣，鏈表勝出）。

多虧了類似 Baptiste 這樣的數據，我們知道了內存布局如何影響序列容器。但是關聯容器，比如 hash 表會怎麼樣呢？已經有了些權威推薦：Chandler Carruth 推薦的帶局部探測的開放定址（此時，我們沒必要追蹤指針），以及Mike Acton 推薦的在內存中將 value 和 key 隔離（這種情況下，我們可以在每一個 cache 流水線中得到更多的 key）， 這可以在我們必須查找多個 key 時提高局部性能。這些想法很有意義，但再一次的說明：測試永遠是好習慣，但由於我找不到任何數據，所以只好自己收集了。

測試

我測試了四個不同的 quick-and-dirty 哈希表實現，另外還包括 std::unordered_map 。這五個哈希表都使用了同一個哈希函數 —— Bob Jenkins 的 SpookyHash（64 位哈希值）。（由於哈希函數在這裡不是重點，所以我沒有測試不同的哈希函數；我同樣也沒有檢測我的分析中的總內存消耗。）實現會通過簡短的代碼在測試結果表中標註出來。

• UM： std::unordered_map 。在 VS2012 和 libstdc++-v3 （libstdc++-v3: gcc 和 clang 都會用到這東西）中，UM 是以鏈表的形式實現，所有的元素都在鏈表中，bucket 數組中存儲了鏈表的迭代器。VS2012 中，則是一個雙鏈表，每一個 bucket 存儲了起始迭代器和結束迭代器；libstdc++ 中，是一個單鏈表，每一個 bucket 只存儲了一個起始迭代器。這兩種情況里，鏈表節點是獨立申請和釋放的。最大負載因子是 1 。

• Ch：分離的、鏈狀 buket 指向一個元素節點的單鏈表。為了避免分開申請每一個節點，元素節點存儲在普通數組池中。未使用的節點保存在一個空閑鏈表中。最大負載因子是 1。

• OL：開地址線性探測 —— 每一個 bucket 存儲一個 62 bit 的 hash 值，一個 2 bit 的狀態值（包括 empty，filled，removed 三個狀態），key 和 vale 。最大負載因子是 2/3。

• DO1：「data-oriented 1」 —— 和 OL 相似，但是哈希值、狀態值和 key、values 分離在兩個隔離的平滑數組中。
• DO2：「data-oriented 2」 —— 與 OL 類似，但是哈希/狀態，keys 和 values 被分離在 3 個相隔離的平滑數組中。

在我的所有實現中，包括 VS2012 的 UM 實現，默認使用尺寸為 2 的 n 次方。如果超出了最大負載因子，則擴展兩倍。在 libstdc++ 中，UM 默認尺寸是一個素數。如果超出了最大負載因子，則擴展為下一個素數大小。但是我不認為這些細節對性能很重要。素數是一種對低 bit 位上沒有足夠熵的低劣 hash 函數的挽救手段，但是我們正在用的是一個很好的 hash 函數。

OL，DO1 和 DO2 的實現將共同的被稱為 OA（open addressing）——稍後我們將發現它們在性能特性上非常相似。在每一個實現中，單元數從 100 K 到 1 M，有效負載（比如：總的 key + value 大小）從 8 到 4 k 位元組我為幾個不同的操作記了時間。 keys 和 values 永遠是 POD 類型，keys 永遠是 8 個位元組（除了 8 位元組的有效負載，此時 key 和 value 都是 4 位元組）因為我的目的是為了測試內存影響而不是哈希函數性能，所以我將 key 放在連續的尺寸空間中。每一個測試都會重複 5 遍，然後記錄最小的耗時。

測試的操作在這裡：

• Fill：將一個隨機的 key 序列插入到表中（key 在序列中是唯一的）。

• Presized fill：和 Fill 相似，但是在插入之間我們先為所有的 key 保留足夠的內存空間，以防止在 fill 過程中 rehash 或者重申請。

• Lookup：執行 100 k 次隨機 key 查找，所有的 key 都在 table 中。

• Failed lookup: 執行 100 k 次隨機 key 查找，所有的 key 都不在 table 中。

• Remove：從 table 中移除隨機選擇的半數元素。

• Destruct：銷毀 table 並釋放內存。

你可以在這裡下載我的測試代碼。這些代碼只能在 64 機器上編譯（包括Windows和Linux）。在 main() 函數頂部附近有一些開關，你可把它們打開或者關掉——如果全開，可能會需要一兩個小時才能結束運行。我收集的結果也放在了那個打包文件里的 Excel 表中。（注意： Windows 和 Linux 在不同的 CPU 上跑的，所以時間不具備可比較性）代碼也跑了一些單元測試，用來驗證所有的 hash 表實現都能運行正確。

我還順帶嘗試了附加的兩個實現：Ch 中第一個節點存放在 bucket 中而不是 pool 里，二次探測的開放定址。 這兩個都不足以好到可以放在最終的數據里，但是它們的代碼仍放在了打包文件裡面。

結果

這裡有成噸的數據!! 這一節我將詳細的討論一下結果，但是如果你對此不感興趣，可以直接跳到下一節的總結。

Windows

這是所有的測試的圖表結果，使用 Visual Studio 2012 編譯，運行於 Windows 8.1 和 Core i7-4710HQ 機器上。

從左至右是不同的有效負載大小，從上往下是不同的操作（注意：不是所有的Y軸都是相同的比例！）我將為每一個操作總結一下主要趨向。

Fill：

在我的 hash 表中，Ch 稍比任何的 OA 變種要好。隨著哈希表大小和有效負載的加大，差距也隨之變大。我猜測這是由於 Ch 只需要從一個空閑鏈表中拉取一個元素，然後把它放在 bucket 前面，而 OA 不得不搜索一部分 bucket 來找到一個空位置。所有的 OA 變種的性能表現基本都很相似，當然 DO1 稍微有點優勢。

在小負載的情況，UM 幾乎是所有 hash 表中表現最差的 —— 因為 UM 為每一次的插入申請（內存）付出了沉重的代價。但是在 128 位元組的時候，這些 hash 表基本相當，大負載的時候 UM 還贏了點。因為，我所有的實現都需要重新調整元素池的大小，並需要移動大量的元素到新池裡面，這一點我幾乎無能為力；而 UM 一旦為元素申請了內存後便不需要移動了。注意大負載中圖表上誇張的跳步！這更確認了重新調整大小帶來的問題。相反，UM 只是線性上升 —— 只需要重新調整 bucket 數組大小。由於沒有太多隆起的地方，所以相對有效率。

Presized fill：

大致和 Fill 相似，但是圖示結果更加的線性光滑，沒有太大的跳步（因為不需要 rehash ），所有的實現差距在這一測試中要縮小了些。大負載時 UM 依然稍快於 Ch，問題還是在於重新調整大小上。Ch 仍是穩步少快於 OA 變種，但是 DO1 比其它的 OA 稍有優勢。

Lookup：

所有的實現都相當的集中。除了最小負載時，DO1 和 OL 稍快，其餘情況下 UM 和 DO2 都跑在了前面。（LCTT 譯註： 你確定？）真的，我無法描述 UM 在這一步做的多麼好。儘管需要遍歷鏈表，但是 UM 還是堅守了面向數據的本性。

順帶一提，查找時間和 hash 表的大小有著很弱的關聯，這真的很有意思。 哈希表查找時間期望上是一個常量時間，所以在的漸進視圖中，性能不應該依賴於表的大小。但是那是在忽視了 cache 影響的情況下！作為具體的例子，當我們在具有 10 k 條目的表中做 100 k 次查找時，速度會便變快，因為在第一次 10 k - 20 k 次查找後，大部分的表會處在 L3 中。

Failed lookup：

相對於成功查找，這裡就有點更分散一些。DO1 和 DO2 跑在了前面，但 UM 並沒有落下，OL 則是捉襟見肘啊。我猜測，這可能是因為 OL 整體上具有更長的搜索路徑，尤其是在失敗查詢時；內存中，hash 值在 key 和 value 之飄來盪去的找不著出路，我也很受傷啊。DO1 和 DO2 具有相同的搜索長度，但是它們將所有的 hash 值打包在內存中，這使得問題有所緩解。

Remove：

DO2 很顯然是贏家，但 DO1 也未落下。Ch 則落後，UM 則是差的不是一丁半點（主要是因為每次移除都要釋放內存）；差距隨著負載的增加而拉大。移除操作是唯一不需要接觸數據的操作，只需要 hash 值和 key 的幫助，這也是為什麼 DO1 和 DO2 在移除操作中的表現大相徑庭，而其它測試中卻保持一致。（如果你的值不是 POD 類型的，並需要析構，這種差異應該是會消失的。）

Destruct：

Ch 除了最小負載，其它的情況都是最快的（最小負載時，約等於 OA 變種）。所有的 OA 變種基本都是相等的。注意，在我的 hash 表中所做的所有析構操作都是釋放少量的內存 buffer 。但是 在Windows中，釋放內存的消耗和大小成比例關係。（而且，這是一個很顯著的開支 —— 申請 ～1 GB 的內存需要 ～100 ms 的時間去釋放！）

UM 在析構時是最慢的一個（小負載時，慢的程度可以用數量級來衡量），大負載時依舊是稍慢些。對於 UM 來講，釋放每一個元素而不是釋放一組數組真的是一個硬傷。

Linux

我還在裝有 Linux Mint 17.1 的 Core i5-4570S 機器上使用 gcc 4.8 和 clang 3.5 來運行了測試。gcc 和 clang 的結果很相像，因此我只展示了 gcc 的；完整的結果集合包含在了代碼下載打包文件中，鏈接在上面。

大部分結果和 Windows 很相似，因此我只高亮了一些有趣的不同點。

Lookup：

這裡 DO1 跑在前頭，而在 Windows 中 DO2 更快些。（LCTT 譯註： 這裡原文寫錯了吧？）同樣，UM 和 Ch 落後於其它所有的實現——過多的指針追蹤，然而 OA 只需要在內存中線性的移動即可。至於 Windows 和 Linux 結果為何不同，則不是很清楚。UM 同樣比 Ch 慢了不少，特別是大負載時，這很奇怪；我期望的是它們可以基本相同。

Failed lookup：

UM 再一次落後於其它實現，甚至比 OL 還要慢。我再一次無法理解為何 UM 比 Ch 慢這麼多，Linux 和 Windows 的結果為何有著如此大的差距。

Destruct：

在我的實現中，小負載的時候，析構的消耗太少了，以至於無法測量；在大負載中，線性增加的比例和創建的虛擬內存頁數量相關，而不是申請到的數量？同樣，要比 Windows 中的析構快上幾個數量級。但是並不是所有的都和 hash 表有關；我們在這裡可以看出不同系統和運行時內存系統的表現。貌似，Linux 釋放大內存塊是要比 Windows 快上不少（或者 Linux 很好的隱藏了開支，或許將釋放工作推遲到了進程退出，又或者將工作推給了其它線程或者進程）。

UM 由於要釋放每一個元素，所以在所有的負載中都比其它慢上幾個數量級。事實上，我將圖片做了剪裁，因為 UM 太慢了，以至於破壞了 Y 軸的比例。

總結

好，當我們凝視各種情況下的數據和矛盾的結果時，我們可以得出什麼結果呢？我想直接了當的告訴你這些 hash 表變種中有一個打敗了其它所有的 hash 表，但是這顯然不那麼簡單。不過我們仍然可以學到一些東西。

首先，在大多數情況下我們「很容易」做的比 std::unordered_map 還要好。我為這些測試所寫的所有實現（它們並不複雜；我只花了一兩個小時就寫完了）要麼是符合 unordered_map 要麼是在其基礎上做的提高，除了大負載（超過128位元組）中的插入性能， unordered_map 為每一個節點獨立申請存儲佔了優勢。（儘管我沒有測試，我同樣期望 unordered_map 能在非 POD 類型的負載上取得勝利。）具有指導意義的是，如果你非常關心性能，不要假設你的標準庫中的數據結構是高度優化的。它們可能只是在 C++ 標準的一致性上做了優化，但不是性能。:P

其次，如果不管在小負載還是超負載中，若都只用 DO1 （開放定址，線性探測，hashes/states 和 key/vaules分別處在隔離的普通數組中），那可能不會有啥好表現。這不是最快的插入，但也不壞（還比 unordered_map 快），並且在查找，移除，析構中也很快。你所知道的 —— 「面向數據設計」完成了！

注意，我的為這些哈希表做的測試代碼遠未能用於生產環境——它們只支持 POD 類型，沒有拷貝構造函數以及類似的東西，也未檢測重複的 key，等等。我將可能儘快的構建一些實際的 hash 表，用於我的實用庫中。為了覆蓋基礎部分，我想我將有兩個變種：一個基於 DO1，用於小的，移動時不需要太大開支的負載；另一個用於鏈接並且避免重新申請和移動元素（就像 unordered_map )，用於大負載或者移動起來需要大開支的負載情況。這應該會給我帶來最好的兩個世界。

與此同時，我希望你們會有所啟迪。最後記住，如果 Chandler Carruth 和 Mike Acton 在數據結構上給你提出些建議，你一定要聽。

作者簡介：

我是一名圖形程序員，目前在西雅圖做自由職業者。之前我在 NVIDIA 的 DevTech 軟體團隊中工作，並在美少女特工隊工作室中為 PS3 和 PS4 的 Infamous 系列遊戲開發渲染技術。

自 2002 年起，我對圖形非常感興趣，並且已經完成了一系列的工作，包括：霧、大氣霧霾、體積照明、水、視覺效果、粒子系統、皮膚和頭髮陰影、後處理、鏡面模型、線性空間渲染、和 GPU 性能測量和優化。

你可以在我的博客了解更多和我有關的事，處理圖形，我還對理論物理和程序設計感興趣。

你可以在 nathaniel.reed@gmail.com 或者在 Twitter（@Reedbeta)/Google+ 上關注我。我也會經常在 StackExchange 上回答計算機圖形的問題。

via: Data-Oriented Hash Table

作者：Nathan Reed 譯者：sanfusu 校對：wxy

本文由 LCTT 原創編譯，Linux中國榮譽推出

推薦閱讀：