我正在為表尋找高性能的 C 結構。該表將以 void* 作為鍵，以 uint32 作為值。
表本身很小，創建后不會改變。我想到的第一個想法是使用類似ska::flat_hash_map<void*, int32_t>or 的東西std::unordered_map<void*, int32_t>。然而，這將是矯枉過正，不會為我提供我想要的性能（這些表也適用于大量專案）。
所以我考慮使用std::vector<std::pair<void*, int32_t>>，在創建時對其進行排序并對其進行線性探測。下一個想法將使用 SIMD 指令，但使用當前結構是可能的。
我將很快評估的另一種解決方案是這樣的：
struct Group
{
void* items[5]; // search using SIMD
int32_t items[5];
}; // fits in cache line
struct Table
{
Group* groups;
size_t capacity;
};
有沒有更好的選擇？我只需要 1 個操作：通過鍵查找值，而不是修改它們，不需要任何操作。謝謝！
編輯：我想我應該提到的另一件事是訪問模式：假設我有一個這些哈希表的陣列，每次我都會從陣列中的一個隨機表中查找。
uj5u.com熱心網友回復：
在這種情況下，線性探測可能是常見主流架構上最快的解決方案，特別是因為元素數量非常少且有界（即 <10）。對專案進行排序不應該用這么少的專案加速探測（它只對二進制搜索有用，在這種情況下它要昂貴得多）。
如果您想使用 SIMD 指令，那么為了性能，您需要使用陣列結構而不是結構陣列。這意味著您應該使用std::pair<std::vector<void*>, std::vector<int32_t>>而不是std::vector<std::pair<void*, int32_t>>（由于64 位體系結構的對齊約束，它使用一些填充開銷來交替記憶體中的void*型別和int32_t值void*）。擁有兩個std::vector也不是很好，因為您要支付兩次開銷。正如@JorgeBellon 在評論中提到的，您可以簡單地使用 astd::array而不是std::vector假設專案數是已知或有界的。
SIMD 指令的一種可能優化是通過將 64 位架構上的關鍵指標分成 32 位低/高部分來壓縮它們。實際上，兩個指標具有相同的低位部分（最低有效位）而具有不同的高位部分是非常不可能的。這個技巧可以幫助您一次檢查 2 倍以上的指標。
請注意，在這種情況下，在實踐中使用 SIMD 指令可能不是那么好。如果項數小于 SIMD 向量中的項數，則尤其如此。例如，使用 AVX2（在 86-64 處理器上），您可以一次處理 4 個 64 位值（或 8 個 32 位值），但如果您的值少于 8 個，則需要屏蔽不需要的值檢查（如果記憶體緩沖區不包含一些填充，甚至不加載它們）。這引入了額外的開銷。這對于 AVX-512 和 SVE（僅在一小部分處理器上可用）來說不是什么大問題，因為它們提供了高級屏蔽操作。此外，一些處理器降低了它們的頻率當它們執行 SIMD 指令時（尤其是使用 AVX-512，盡管整數指令的降頻不是那么強）。與標量版本（可以更好地流水線化）相比，SIMD 指令還引入了一些額外的延遲，現代處理器往往能夠比 SIMD 并行執行更多的標量指令。由于所有這些原因，嘗試撰寫一個標量無分支實作當然是一個好主意（如果專案數量在編譯時已知，則可能展開以獲得更好的性能）。
uj5u.com熱心網友回復：
您可能想要研究完美的散列——不太難，并且可以提供簡單的恒定時間查找。但是，從技術上講，創建表可能需要無限的時間，而且當常規哈希表幸運時，它不如常規哈希表快。
我認為一個不錯的選擇是優化您的簡單線性探測想法。
您的查找程序如下所示：
Slot *s = &table[hash(key)];
Slot *e = s s->max_extent;
for (;s<e; s) {
if (s->key == key) {
return s->value;
}
}
return NOT_FOUND;
table[h].max_extent如果您正在尋找具有哈希碼的元素，則是您可能需要查看的最大元素數h。您將在生成表時預先計算它，因此您的查找不必迭代，直到它獲得空值。這大大減少了您必須為未命中而進行的探測量。
當然，您希望max_extent盡可能小。選擇一個散列結果大小（至少 2n）使其在大多數情況下 <= 1，并嘗試幾種不同的散列函式，然后再根據您喜歡的任何指標選擇產生最佳結果的散列函式。您的散列可以像 一樣簡單key % P，其中嘗試不同的散列意味著嘗試不同的 P 值。填寫您的哈希表hash(key)以產生最佳結果。
請注意，我們在探測時不會從表的末尾繞到表的開頭。只需分配您需要避免它的許多額外插槽。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/388169.html
上一篇：根據另一個陣列和條件過濾一組物件