出来事の日付：2026年10月28日

固定された文字列キーの集合を扱う新しいC++ライブラリが、Apple M4搭載ハードウェアでのベンチマークで毎秒10億回を超える検索を記録したと報告した。プログラムがコンパイル時に検索用の構造を構築できる場合、どれほどの性能を引き出せるかを示す結果だ。

計算機科学の教授ダニエル・ルミールとフランシスコ・ガイマン・ティーセンによるこの取り組みは、HTTPメソッド、ヘッダー名、URLのプロトコル、プログラミング言語のキーワードを識別するといった一般的な処理を対象にしている。こうした用途では、受け付ける文字列がソフトウェアの実行前から分かっており、変わることもないのに、汎用ハッシュマップが使われることが多い。

汎用ハッシュテーブルは、衝突、動的な記憶領域、任意のキーに対応しなければならない。これに対し、提案された手法は、与えられたキー集合専用の完全ハッシュ関数を作る。認識対象の各文字列を一意のスロットに対応させることで、検索時の探索や、衝突した要素をつなぐ連結リストを不要にする。この考え方自体は古く、GNUの生成ツールgperfは1989年にさかのぼる。ただし今回の実装は、C++23のコンパイル時評価を使って関数を探索し、単一のヘッダーファイルとして提供される。

ハッシュは、文字列の長さと、選択した文字を添字とする関連付けテーブル内の小さな値を組み合わせる。テーブルの大きさを2の累乗にすることで、最後に値を範囲内へ収める処理にはビットマスクを使える。コンパイラは、constexpr計算の制限内に収まるよう設計された、探索量に上限のある貪欲法で、衝突を起こさない関連付けの値を探す。そのため、実行時の処理は、候補のキーを照合する前の数回のロード、加算、マスク処理にまで縮小できる。

文字列比較も用途に合わせて最適化されている。短いキーについては、16バイトのベクトルを読み込み、入力の長さを超えるバイトをマスクしたうえで、ゼロ埋めして保存したキーと比較する。幅の広いロードがメモリページの境界をまたぐ可能性がある場合は、境界チェックによって遅い処理経路を選ぶ。データに依存する複数の分岐を、挙動が安定すると見込まれる1つの境界分岐に置き換える設計だ。

ルミールは、AppleClang 15を使ったApple M3 Maxで、標準的なHTTPヘッダー名20個の検索に1回当たり1.3ナノ秒かかったと報告した。同じ試験では、gperfは7.7ナノ秒、Abseilのflat_hash_mapは10.9ナノ秒、std::unordered_mapは16.6ナノ秒だった。複数の固定キー集合を通じ、新しい実装は1回当たり1.2～2ナノ秒の範囲に収まったという。Apple M4では、URLプロトコルのベンチマークが毎秒10億回の処理を超えた。

これらの数値は作者自身が実施したマイクロベンチマークの結果であり、あらゆるアプリケーションでの性能を保証するものではない。性能はプロセッサ、コンパイラ、キー集合、呼び出しの状況、周辺の処理によって変わる。また、この方法が適用できるのは事前に決まっていて変更されないキーであり、実行時に要素を追加する必要があるマップではない。

それでも、扱う語彙が小さく安定しているパーサーやサーバーにとって、この結果は、汎用コンテナが回避可能な処理を課している場合があることを示している。ベンチマークのコードとグラフ作成スクリプトはライブラリとともに公開されており、開発者は自分のワークロードで主張を検証できる。