ハッシュテーブルは、その巧妙さゆえに厄介だ。
std::unordered_set の平均 O(1) ルックアップという約束に、私たちはつい手を伸ばしてしまう。特に C++ で、とにかく速さを追求したいときには、それがデフォルトで賢い選択肢のように思える。だが、ほとんどの人が見落としているのは、ハイパフォーマンスコード、特にナノ秒を争うホットループの最前線では、その自動的な反射神経が、文字通り桁違いのコストをあなたに請求するということだ。
これは単なる机上の空論ではない。私は、近似最近傍探索のための Vamana グラフインデックスに取り組んでいたとき、これを身をもって体験した。そのタスクでは、訪問済みのノードを追跡する必要があった。ノード ID は？ 密な整数だ。そして、ノードが訪問済みかどうかをチェックする処理は？ それは、探索パス全体で最もホットなループの中で発生していた。これ以上クリティカルな場所はないだろう。
私の最初の選択肢は、当然ながら std::unordered_set だった。確かに正しかったし、仕事はこなした。だが、それは 遅かった。特にスケールが大きくなると、痛いほど遅かったのだ。
その遅さを把握するために、いくつかのテストを実行した。1000 個のランダムな uint32_t ID のベクトルを、3 つの異なる重複排除方法に投入した。すなわち、前述の std::unordered_set、古典的な sort + unique の組み合わせ、そして boost::dynamic_bitset<> だ。ID は密で、[0, 2n) の範囲からサンプリングされた。結果は？ 残酷だった。
| n | unordered_set ms | sort+unique ms | boost bitset ms |
|---|---|---|---|
| 128 | 5 | 3 | 1 |
| 32,768 | 1,649 | 1,455 | 177 |
| 500,000 | 50,302 | 26,759 | 3,423 |
最後の行を見てほしい。50万要素で、ビットセットはほぼ 15倍 速かった。なぜか？ ハッシュテーブルは、キーのハッシュ計算、バケットの成長処理、混雑しすぎたときの再ハッシュ、そしてメモリ全体でのポインタ追跡といった、あらゆる高コストなブックキーピングに追われていたからだ。ビットセットは？ 単一のインデックス付きメモリ操作だ。シンプルで、直接的で、データが収まる場合にははるかに効率的だ。
scale が大きくなると、sort + unique でさえハッシュテーブルを上回ることができた。なぜか？ それは単に連続したメモリを走査しているだけだからだ。そして CPU は？ CPU は連続したメモリを 愛している。
さて、ハッシュテーブルを完全に捨て去る前に、注意点がある。ID がスパース（疎）な場合、少なくともビットセットにとってはゲームチェンジャーとなる。1億という巨大な宇宙から n 個の ID をサンプリングした場合、ビットセットは 各ベクトルごとに、巨大でほとんど空の配列をクリアする必要があった。これは無視できないオーバーヘッドだ。
| n | unordered_set ms | boost bitset ms |
|---|---|---|
| 128 | 6.3 | 149.7 |
| 2,048 | 91.9 | 145.5 |
| 65,536 | 4,169.3 | 985.4 |
これを見ただろうか？ 小さくスパースな入力の場合、std::unordered_set は実際には より良い。ビットセットは、入力が upfront のクリアコストを償却するのに十分な大きさになって初めて輝き始める。いつものように、トレードオフだ。
では、いつ std::unordered_set を使うべきなのか？ ID がスパースな場合、または不定な場合、あるいは単に直接インデックス化に適さない整数である場合だ。しかし、ホットループ内で密な整数が踊っているときは？ メンバーシップチェックを再考する必要がある。代わりにインデックス付きのロードまたはストアにするのだ。それは安価で、速く、CPU を尊重する。
CPU は、そのシリコンの心臓部、ビッグオー記法など気にも留めない。キャッシュラインとメモリのアクセスパターンを気にする。これを間違えると、おしまいだ。
CPU はビッグオー記法など気にしない。メモリのアクセスパターンを気にする。
タイトなループで std::unordered_set を避けるというこの騒ぎは、新しいものではない。昔から、人々は同様の分析を行っていた。これは古典的なパフォーマンスの落とし穴だ。汎用的で、一見効率的な構造の魅力が、最新プロセッサの超最適化された低レベルの現実を覆い隠してしまう。誰が儲かるのか？ それは、非効率なコードを brute-force で処理できるより高速な CPU を販売するシリコンメーカーだ。そして、もしかしたら、ループを最適化する人々が競争上の優位性を得るかもしれない。
なぜこれが開発者にとって重要なのか？
効率が、特にシステムプログラミング、ゲーム開発、科学計算、組み込みシステムなどの多くの分野で依然として王様だからだ。これらの低レベルのパフォーマンス特性を無視することは、大幅な速度をテーブルの上に置き去りにすることを意味する。それは単にミリ秒を削ることではない。より大きなデータセット、より複雑なシミュレーション、そしてより応答性の高いアプリケーションを可能にすることだ。それは、ハードウェアを不必要に churn しないコードを書くことだ。そして、リソースがしばしば制約され、すべてのサイクルが重要となるオープンソースの世界では、これらのニュアンスを理解することが、プロジェクトが繁栄するか、パフォーマンスの負債の下で衰退するかの違いになる可能性がある。
std::unordered_set はパフォーマンスにとって常に正しい選択肢か？
絶対にそうだ。ハッシュ衝突がまれなシナリオ、データアクセスパターンが真にランダムな場合、またはスパースデータのためにビットセットをクリアするオーバーヘッドがハッシュテーブルの操作を上回る場合、std::unordered_set は依然として完全に妥当な、あるいは最良の選択肢となり得る。鍵はコンテキストだ。ほとんどの日常的なプログラミングタスクでは、その利便性と平均ケースのパフォーマンスで十分すぎるほどだ。しかし、パフォーマンスの壁にぶつかったとき、またはプロファイリングが何かをボトルネックだと教えてくれたとき、抽象的な O(1) の約束よりも深く掘り下げる必要がある。そのとき、ツール自体ではなく、習慣に疑問を投げかけるのだ。
