Facebook 開放 F14 哈希表的實現

公司臉書 宣布了 關於開源哈希表實現 F14針對高效內存消耗進行了優化。 F14 在 Facebook 基礎架構中用作大多數類型的哈希表的替代品，允許您在不犧牲性能的情況下減少內存消耗。 F14 明顯優於 google::sparse_hash_map 哈希表，後者一直被認為是內存效率最高的。 項目代碼用C++編寫並包含在庫中 蠢事.

F14 指的是具有基於 14 雙散列的衝突解決系統的算法 樣本序列 （哈希表的一個單元存儲一串14個槽，單元之間的間隔使用輔助哈希函數計算）。 為了加速單元格過濾操作，該實現使用 x2_86 系統的 SSE64 矢量指令和 Aarch64 系統的 NEON，這允許您並行化選擇帶有密鑰鏈的插槽和鏈內篩選密鑰的操作。 一次處理 14 個插槽的塊，這是使用處理器緩存的效率和衝突次數之間的最佳平衡。

F14的一個特點是可以選擇不同的數據存儲策略：

• F14NodeMap - 大中型鍵消耗最少的內存。 每次插入 malloc 函數時，通過調用提供元素的間接存儲；
• F14ValueMap - 為小鍵提供最小的內存消耗。 元素存儲在單元格本身中（內聯）。 對於中型和大型密鑰，這種方法會導致顯著的內存開銷；
• F14VectorMap 對於大表和復雜鍵更快，但對於簡單鍵和小表更慢。 元素被打包到一個連續的數組中，並由一個 32 位索引指針尋址；
• F14FastMap 是一種組合策略。 如果key小於24字節，則選擇F14ValueMap，如果大於14字節，則選擇FXNUMXVectorMap。

來源： opennet.ru