C++における毎秒10億クエリのルックアップテーブル

C++における毎秒10億クエリのルックアップテーブル

多くのソフトウェアは、文字列を値にマッピングするのに時間を費やしています。Webサーバーは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}
};

これは機能します。しかし、あることに気づいてください。キーはコードを書くときにわかっています。それらは決して変わりません。それにもかかわらず、あたかもいつでも変更できるかのようにランタイムでコストを支払っています。文字列全体をハッシュし、バケットを選択し、ポインタをたどり、比較し、場合によってはリストをたどります。

パーフェクトハッシュ

ハッシュ関数はキーをスロットにマッピングします。2つのキーが同じスロットに着地すると、衝突が発生し、対処する必要があります。衝突こそがハッシュテーブルを複雑で遅くする原因です。

すべてのキーが事前にわかっている場合、衝突が発生しないように設計されたハッシュ関数、つまりパーフェクトハッシュ関数を構築できます。このアイデアは古くからあります。GNUのgperfツールは1989年からこれを実行しています。キーワードのリストを与えると、Cコードを生成します。

私たちはgperfと同じ設計に従います。キーのスロットは次のように計算されます。

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

キーの長さに、いくつかの選択された位置の文字でインデックス付けされた関連テーブル（asso）から取得したいくつかの小さな値を加算します。通常、1つまたは2つの位置で十分です。テーブルサイズは2のべき乗なので、モジュロ演算は単一のビット演算ANDになります。

4つの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）を計算し、スロット4に格納されているキーとPUTを比較します。1回のハッシュ、1回の比較です。セットにないPATCHをルックアップすると、スロット5 + 1 = 6に着地し、DELETEと比較して完了です。見つかりません。プロービングはなく、たどるリストもありません。

関連値はどうやって見つけるのでしょうか？衝突を引き起こさない値が見つかるまで、文字をそれらが触れるキーの数でソートします。次に、それらを1つずつ取り、0、1、2、…を試します。一度設定した値は決して変更しません。これは境界付きの作業を行う貪欲なアルゴリズムです。境界が重要である理由は、これらすべてをコンパイル時に行うため、C++コンパイラはconstexpr関数が行える作業量に制限があるからです。

C++での実装

私たちのライブラリを使用すると、通常の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>
>();

このマップはコンパイル時定数です。コンパイラはコードをコンパイルするときにパーフェクトハッシュ関数を検索します。ランタイムでは、ハッシュの計算はわずか4命令で済みます。キーのバイトを1つロードし、関連テーブルからバイトを1つロードし、長さを加算し、マスクを適用します。

文字列の高速比較

ハッシュの計算は安価です。しかし、ルックアップしている文字列がスロットに格納されているキーと一致することを確認する必要があります。文字列の比較は高価になる可能性があります。教科書的なアプローチは、各バイトに分岐を伴うバイトのループです。数十命令といくつかの分岐に至ることは容易であり、文字列が変化すると分岐の予測は困難になります。

代わりに、キーをベクトルとして扱います。ARMでもx64でも、プロセッサは16バイトレジスタを持っています。そのため、キーが3バイトしかなくても、無条件で16バイトをロードします。次に、キーの末尾以降のバイトをゼロにするためにシャッフル命令（ARM NEONではtbl）を使用します。格納されているキーはコンパイル時にゼロパディングされます。単一のベクトル比較でキー全体を処理できます。約40命令と8つの分岐から、5命令と分岐なしになります。

しかし待ってください。3バイトしかないのに16バイトを読み取るのは安全でしょうか？バッファの末尾を越えて読み取ることは、別のメモリページに侵入しない限り問題ありません。ページは少なくとも4キロバイトです。そのため、アドレスがページの末尾から16バイト以内にあるかどうかを確認します。そうであれば、より遅いパスを取ります。そうでなければ、ワイドロードを実行します。私たちは、予測不可能な複数の分岐を、ほぼ常に同じように分岐する単一の分岐と交換しました。

どのくらい速いのか？

Apple M3 Max（AppleClang 15）でベンチマークを実行しました。ランダムな順序でキーをルックアップし、ルックアップあたりの時間を報告します。まず、20の標準HTTPヘッダー名を検討します。

［画像: HTTP header names, nanoseconds per lookup］

ルックアップあたり約1.3ナノ秒、つまり約5サイクル必要です。従来のgperfは7.7ナノ秒必要です。Abseilのflat_hash_map（優れたハッシュテーブル）は10.9ナノ秒必要です。そしてstd::unordered_mapは16.6ナノ秒必要です。標準ライブラリの13倍高速です。

これは単一のラッキーなキーセットではありません。ここでは、6つのURLプロトコルからS&P 100の100のティッカーまでの複数のキーセットでの結果を示します。

［画像: Seven key sets, nanoseconds per lookup］

ルックアップあたり1.2ナノ秒から2ナノ秒の間に収まります。gperfより3〜6倍、std::unordered_mapより7〜13倍高速です。gperfがJavaScriptの予約語で苦労していることに注目してください。そこでは17倍高速です。

なぜstd::unordered_mapはそれほど遅いのでしょうか？C++標準は、本質的に連鎖ハッシュテーブルを要求しています。ルックアップは、関数を呼び出して文字列全体をハッシュし、ヒープ割り当てノードへのポインタをたどり、リストを歩きます。私たちのルックアップは数回のロードを実行し、関数呼び出しはありません。プロセッサはこのチップで可能な限り良好な状態である8.6命令/サイクル以上をリタイアでき、分岐の誤予測はほとんどありません。

［画像: Cost of one lookup］

Apple M4では、URLプロトコルで1秒あたり10億以上のルックアップを超えます。

結論

キーがコンパイル時にわかっている場合、ランタイムでの衝突処理のコストを支払うべきではありません。パーフェクトハッシュ関数を使用すると、比較は1回にまで削減されます。注意を払えば、ルックアップのコストは約5サイクルです。このライブラリは、プロジェクトにドロップインできる単一のヘッダーです。github.com/ConstexprCore/perfect_hash

これはFrancisco Geiman Thiesen（Microsoft）との共同作業です。P99 CONF 2026で発表しました。YouTubeで講演を見ることができます。

ベンチマーク結果とプロットスクリプトが利用可能です。