シンクリッジ

STL と MFC の map 速度比較

コーディング小手先テクニックとは多少毛色が違うかもですが、ふと興味が沸いたので調査してみました。マップライブラリの速度比較です。
STL の map と hash_map と、さらに MFC の CMap を比較してみました。
これら全て同じような機能のものなので、どれを使っても普通に動作させることは出来ると思うんですが、多少でも処理速度を稼ぎたい場合にどれを使えばよいかの参考にしたいと思いました。

で、ベンチマークアプリを作って試してみました。

一番ありそうな、文字列(string)をキーとしたマップで、map hash_map CMap それぞれ、insert(SetAt)、find(LookUp) を３秒間にどれだけ行えるかを測定してます。

なお、CMap に関してはハッシュテーブルサイズ（bucketサイズ）を調整することが出来ます。ヘルプには「最高のパフォーマンスには項目数の20%増しくらいの素数が良い」ということですが、とりあえずデフォルト値(17)と1009の2種類で試しています。
/*
hash_map にはハッシュテーブルサイズを調整するような関数がなさげだったので特に何もしてないんですが、この認識は正しいでしょうか？
*/

以下は、ベンチマーク結果をグラフにしたものです。(動作環境 PentiumM 1.73GHz の 795Mhz 動作時)

・・・・というわけで、実はかなり意外だったんですが、MFC の CMap のパフォーマンスがずば抜けてます。
デフォルトのハッシュテーブル値は17という小さすぎる値なので調整は必須なのですが、特に find に関しては STL の hash_map と比較して、項目数が多すぎない限り（ハッシュ値の衝突が少ない限り）は、2倍くらい高速という結果でした。
ただ、CMap はハッシュテーブル数の設定によって、パフォーマンスに大きく影響するみたいです。特にデフォルト値の場合、項目数が1000個を超えたあたりから極端に遅くなってます。衝突した後はテーブル内を上から単純に全検索っぽいので、衝突を出来るだけ避けたほうがよさげです。
それを言うと、STLのほうは項目数によらず比較的安定しています。
map はさすがに項目数が増えると徐々に遅くなってますが、hash_map に関してはかなり緩やかです。特にfindについては項目数による速度低下の少なさはダントツです。

とはいえ、実際のケースで考えると、やはり CMap の方がよさげな印象です。項目数は大体予想できるので適切なハッシュテーブル数を設定することもそれほど無理ではなさげですし、findで2倍の速度は魅力です。

・・・がしかし、STL がそこまで溝をあけられてしまうってのも不思議な気がします。
キーが string ってのが不得意なのか、単純にベンチマークアプリのミスか MFC 有利に働くように組んじゃったのか。

というわけで、ベンチマークアプリのソースを置いておきますので、もし興味のある方に是非見てもらって、ダメ出しとかご意見とか頂ければ幸いです。
こちらです BenchMap
VisualStudio2005 で組んだプロジェクト一式です。MFC を使用してますので、StandardEdition 以上でしかコンパイル出来ないと思いますのでご注意ください。