C++ 中每秒十億次查詢的查詢表

許多軟體花費時間將字串對映到值。網路伺服器必須辨識 HTTP 方法 (GET, POST, …)。它必須辨識標頭名稱。URL 解析器必須辨識協定 (http, https, ftp, …)。編譯器必須辨識關鍵字。

在 C++ 中，預設做法是將字串放在 std::unordered_map 中。

std::unordered_map<std::string_view, Method> methods = {
    {"GET", Method::GET}, {"POST", Method::POST}, {"PUT", Method::PUT},
    {"DELETE", Method::DELETE}, {"PATCH", Method::PATCH}};

這樣就能工作。但請注意：關鍵字在編寫程式碼時就已知，且永不變動。儘管如此，我們在執行時仍像它們可能隨時改變一樣付費：雜湊整個字串、選取桶、跟隨指標、比較，甚至可能遍歷連結串列。

完美雜湊

雜湊函式將關鍵字對映到槽位。若兩個關鍵字落在同一槽位，就會產生碰撞，必須處理。碰撞是使雜湊表複雜且慢的原因。

若你事先知道所有關鍵字，可以構造專為你的關鍵字設計的雜湊函式，永不產生碰撞。這稱為完美雜湊函式。這個概念已久：GNU gperf 工具自 1989 年起已在做這件事。你提供一份關鍵字清單，它會產生 C 程式碼。

我們採用與 gperf 相同的設計。關鍵字的槽位計算如下。

slot = (length + asso[key[i]] + asso[key[j]] + ...) % table_size

我們將關鍵字長度加上幾個從關聯表 (asso) 取出的較小值，該表以選定位置的字元為索引。通常一或兩個位置足夠。表大小是 2 的冪，因此取模相當於一次位元與運算。

以四種 HTTP 方法 GET、PUT、POST 和 DELETE 為例。我們只使用首字元。設 asso['G'] = 0、asso['P'] = 1 和 asso['D'] = 0。然後 GET 進入槽 3 + 0 = 3，PUT 進入槽 3 + 1 = 4，POST 進入槽 4 + 1 = 5，DELETE 進入槽 6 + 0 = 6。無碰撞。

要查詢 PUT，我們計算槽位 (4)，並將 PUT 與槽 4 中儲存的唯一關鍵字比較。一次雜湊，一次比較。若查詢 PATCH（不在集合中），你落在槽 5 + 1 = 6，與 DELETE 比較，完成：未找到。沒有探測，也沒有連結串列需要遍歷。

我們如何尋找關聯值？先按每個字元觸碰的關鍵字數量排序。接著逐一取出，嘗試 0、1、2、…，直到找到不會產生碰撞的值。設定後不再修改。這是一個有界工作的貪婪演算法。界限重要，因為我們在編譯時完成所有工作，而 C++ 編譯器限制 constexpr 函式可做的工作量。

在 C++ 中實作

使用 our library，你可以寫普通的 C++23。不需要外部工具執行。

#include <ConstexprCore/perfect_hash.h>
using namespace ConstexprCore;
enum class Method { GET, POST, PUT, DELETE, PATCH };
constexpr auto methods = make_perfect_map<
    kv<"GET",    Method::GET>,
    kv<"POST",   Method::POST>,
    kv<"PUT",    Method::PUT>,
    kv<"DELETE", Method::DELETE>,
    kv<"PATCH",  Method::PATCH>
>();

對映是編譯時常數。編譯器在編譯程式碼時搜尋完美雜湊函式。執行時，計算雜湊可僅需四條指令：載入關鍵字的一個位元組、載入關聯表的一個位元組、加上長度、套用遮罩。

快速比較字串

計算雜湊成本低廉。但仍需確認查詢的字串與槽中儲存的關鍵字相符。字串比較可能昂貴：教科書方法是逐位元組迴圈，且每個位元組都有分支。這很容易導致數十條指令和多個分支，且當字串變化時，分支難以預測。

相反地，我們把關鍵字視為向量。無論是 ARM 或 x64 處理器，都有 16 位元組的暫存器。因此我們無條件載入 16 位元組，即使關鍵字只有三位元組。我們接著使用 shuffle 指令（tbl 在 ARM NEON 上）將關鍵字結束後的位元組設為 0。儲存的關鍵字在編譯時已經以零填充。一次向量比較即可處理整個關鍵字。從大約四十條指令與八個分支，減至五條指令且無分支。

不過，請問在只有三位元組時讀取 16 位元組是否安全？只要不跨入另一個記憶體頁面，且頁面至少 4KB，讀取超出緩衝區尾端是允許的。因此我們檢查該位址是否距離其頁面結尾不足 16 位元組。若是，我們採用較慢的路徑；否則就執行寬載入。我們把多個不可預測的分支換成一個幾乎總是以相同方式被採取的單一分支。

它有多快？

我在 Apple M3 Max 上使用 AppleClang 15 執行基準測試。我們以隨機順序查詢鍵，並報告每次查詢所需時間。先來看 20 個標準 HTTP 標頭名稱。

我們需要大約 1.3 ns 每次查詢，或約 5 個週期。經典的 gperf 需要 7.7 ns。Abseil 的 flat_hash_map（一個優秀的雜湊表）需要 10.9 ns。std::unordered_map 需要 16.6 ns。我們比標準函式庫快十三倍。

這並非一次幸運的鍵集合。以下列出多個鍵集合的結果，從 6 個 URL 協議到 S&P 100 的 100 個股票程式碼。

我們每次查詢的時間介於 1.2 ns 與 2 ns 之間。我們比 gperf 快 3~6 倍，比 std::unordered_map 快 7~13 倍。注意 gperf 在處理 JavaScript 保留字時表現不佳：那時我們快 17 倍。

為什麼 std::unordered_map 那麼慢？C++ 標準實際上要求使用鏈式雜湊表。一次查詢會透過函式呼叫對整個字串進行雜湊，接著追蹤指向堆疊分配節點的指標，並遍歷連結串列。我的查詢僅執行少量載入，且不呼叫函式。使用此程式碼，處理器每週期可退化超過 8.6 條指令，這已是該晶片上最佳表現，且幾乎永遠不會錯誤預測分支。

在 Apple M4 上，使用 URL 協議時，我們每秒超過十億次查詢。

結論

如果你的鍵在編譯時已知，則不應在執行階段為衝突處理付費。完美雜湊函式可將比較次數降至一次。經過適當處理，查詢成本約為五個週期。此函式庫為單一標頭檔，您可以直接加入專案：github.com/ConstexprCore/perfect_hash。

這是與 Francisco Geiman Thiesen（Microsoft）共同完成的工作。我們於 P99 CONF 2026 進行了發表。您可以 觀看此演講於 YouTube。

以下為 基準數值與繪圖指令碼，已公開可取得。