過去の記事でvectorに比べてmapの全走査が遅いという比較を行ったことを思い出し，そういえばunordered_mapとの比較をしていなかったので比較をすることにした．
前回のコードに以下のようなコードを追加して実験．
今回は以下のようなデータ構造を追加
(b)や(c)は，keyのデータを別途vector配列に入れておいて，そちらを走査しながらmapを引くというコードをよく書いているので，これやるとどんくらい遅くなるのだろうということを調べるため．
前回のコードとのdiffはこんな感じ．
6d5
< #include <unordered_map>
46,47d44
< std::vector<int> key_vec;
< std::unordered_map<int, int> um;
53,54d49
< um[ *itr ] = 1;
< key_vec.push_back( *itr );
79,117c74,75
< // unordered_map
< double t5 = gettimeofday_sec();
< double umsum = 0.0;
< std::unordered_map<int, int>::iterator uitr = um.begin();
< while (uitr != um.end()) {
< umsum += (uitr->first * uitr->second);
< ++uitr;
< }
< double t6 = gettimeofday_sec();
<
<
< // map + key vec
< double t7 = gettimeofday_sec();
< std::vector<int>::iterator kitr = key_vec.begin();
< double kmsum = 0.0;
< while (kitr != key_vec.end()) {
< int key = *kitr;
< kmsum += (key * m[ key ]);
< ++kitr;
< }
< double t8 = gettimeofday_sec();
<
<
< // unordered_map + key vec
< double t9 = gettimeofday_sec();
< std::vector<int>::iterator kitr2 = key_vec.begin();
< double kumsum = 0.0;
< while (kitr2 != key_vec.end()) {
< int key = *kitr2;
< kumsum += (key * um[ key ]);
< ++kitr2;
< }
< double t10 = gettimeofday_sec();
<
<
< if (msum != vsum ||
< msum != umsum ||
< msum != kumsum) {
< std::cerr << "ERROR: msum != vsum or brabrabra" << std::endl;
---
> if (msum != vsum) {
> std::cerr << "ERROR: msum != vsum" << std::endl;
126,128d83
< std::cout << " umap time=" << (t6 - t5) << " sec." << std::endl;
< std::cout << " vec+map time=" << (t8 - t7) << " sec." << std::endl;
< std::cout << "vec+umap time=" << (t10 - t9) << " sec." << std::endl;
結果
O3最適化オプションの結果は以下のとおり．実験条件は前回と同じ．
% ./map-vs-vector_each_O3
========================================
min=0 max=100000000 num=1000000
idnum=994988
map time=0.025021 sec.
vector time=0.00304701 sec.
umap time=0.0163119 sec.
vec+map time=0.148234 sec.
vec+umap time=0.05696 sec.
========================================
========================================
min=0 max=100000000 num=2000000
idnum=1980206
map time=0.0489781 sec.
vector time=0.00605991 sec.
umap time=0.036946 sec.
vec+map time=0.305442 sec.
vec+umap time=0.125602 sec.
========================================
========================================
min=0 max=100000000 num=3000000
idnum=2955469
map time=0.0753331 sec.
vector time=0.0090471 sec.
umap time=0.0403191 sec.
vec+map time=0.455493 sec.
vec+umap time=0.144672 sec.
========================================
考察
- unordered_mapの全走査はmapよりも速い (1.5-2倍程度)
- keyだけvectorに入れてmap/unordered_mapから引くという操作をすると5倍以上遅くなる
- map vs. vec+map, umap vs vec+umapの比較
以外なことにunordered_mapがmapよりも速い．そしてkeyだけvectorに入れるとこれほどまで遅くなるとはこれまた意外．
なお@tkngさんのブログ記事によるとunordered_mapはメモリ的にもmapより効率がよいみたいなので，もはやmapを使う理由が存在しないような気がする．
unordered_といういかにもtypoしそうなタイピングコストとコンパイル時の-std=c++0xというタイピングコストくらいなのではないだろうか．前者はマクロを使えば解決するので，もはやmapの存在意義がわからない．
unordered_mapのハッシュがどのように実装されているのかソース読んでいないので知らないけれどきっとチェインハッシュだろうと勝手に考えてみる．そうするとテーブル部分は当然配列で持っているだろうし，各チェインについてたとえばvectorのような可変長配列で持っておくとキャッシュ効率的によい．というわけで全舐めについてもunodered_mapがmapに対して効率的だということがなんとなく納得できる感じ．さてハッシュだと衝突によるチェインの長さ増加を避けるためにテーブルサイズを最初から大き目に取っておくとする．するとアイテム数がごく少量の場合はmapの方が省メモリになるのではないか．
追加実験
それくらいなら調べられるだろうと思って調査．単純にmap
- 空のプログラム
- 808kB
- 初期状態 (宣言のみ)
- map: 808kB
- umap: 856kB
- 1アイテム追加
- map: 872kB
- umap: 872kB
- 5アイテム追加
- map: 872kB
- umap: 872kB
- 10アイテム追加
- map: 872kB
- umap: 872kB
- 100アイテム追加
- map: 876kB
- umap: 872kB
- 1000アイテム追加
- map: 900kB
- umap: 896kB
追加実験で得られた結果をまとめる
- ハッシュのテーブル初期サイズはどうやら6000 (= 48000 / (4 + 4)) アイテム?
- 宣言のみの状態だとmapの方が使用メモリが大きい
- アイテムを1個でも追加した状態では使用メモリサイズは等しくなる
- 1000個追加でunordered_mapの方が省メモリになる
- 予想と@tkngさんの検証からきっとこれよりアイテム数が増えてもunordered_mapの方が省メモリ
結論
ありがとうmap．君のことは忘れないよ．
