これは何？
C++ で辞書（key-value pair）がほしい場合。
とりあえず std::unordered_map か std::map を使うと思う。
状況によっては boost::container::flat_map を使うこともあると思う。
でも、要素数が少ない場合は線形探索のほうが速かったりするんじゃないの？ と思って測ってみた。
登場人物
std::map
中身は赤黒木。ポインタをたどって要素を探す。
std::unordered_map
中身は Hashテーブル。ハッシュ値でスロットを特定する。スロット内はよく知らない。
boost::container::flat_map
中身は整列済みの配列のようなもの。二分探索で要素を探す。
挿入は遅いけど、探索は速いという評判。
線形探索
中身は vector。先頭から普通に探す。
調査内容
キーのバイト数 K、コンテナに入れる要素数 E、試行回数 T を決める。
コンテナを 16個、キーを 16個作る。
作ったキーをキー、値を適当な 64bit整数 にしてコンテナに値を入れる。コンテナに入れる要素数は 16個とも E。
以下の操作を行う時間を測る
合計のための変数 sum を用意する
- T 回、以下の操作をする
- 使うキーとコンテナを乱数で決める
- 上記で決まったコンテナにキーを渡して値を得る。
- 得られた値を
sumに加算する
コンパイラは、 Apple clang version 12.0.5 (clang-1205.0.22.11) / x86_64-apple-darwin20.6.0。
コンパイルオプションに -O2 -std=c++17 を入れている。
ハードウェアは手元の MacBook Pro。
調査結果
以下グラフは、横軸がコンテナサイズ。縦軸が処理時間（秒）。
対数目盛注意。
試行回数は key のサイズで適当に変えている。例えば key が uint32 × 1 の場合は 4194304回、key が uint32 × 256 の場合、16384回施行している。
感想
グラフを見ると分かる通り、キーのサイズで様子が違う。キャッシュに乗るかどうかが勝負なのかな。
unordered_map で、要素数が増えると却って速くなる部分があって謎だけど調べていない。
あと
- キーのバイト数が少ないと線形が有利。
-
unordered_mapが速い。flat_mapは意外と振るわない。 - キーが 32bit ぐらいで
unordered_mapとの比較なら、10〜30 個ぐらいまでは線形有利。 - キーが 32bit ぐらいで
mapとの比較なら、30〜100 個ぐらいまでは線形有利。
辺り。
もちろん処理系とかキャッスサイズとか色々で変わるのでこの実験結果の汎用性はあまりないと思う。
この調査では map がいまいちな感じだけど、比較がハッシュ値の計算より安いケースでは map が圧勝したりするので、ケースバイケースということではある。
まとめ
存在しないキーで探索する割合とか、キャッシュの効き具合とか、時間に影響を与える条件がたくさんあるので、一般的で公平なベンチマークは存在しないと思う。
要素数が少ないとわかっているときは線形も悪くないなと思ったけど、std::linear_map みたいなのがないので実装するとしたら手作りになるからめんどくさい。どっかに作っておこうかな。それとももうどっかにあるのかなぁ。
あと、要素数が少ない場合は線形で、要素数が多くなると Hashテーブルになる、みたいな対応をするといつでも速くなるかもとも思った。うまくやる方法はあるのだろうか。
実験に使ったコードを github に置いた。