mapとvectorを走査する速度の違い

数日前に@niamさんのつぶやきを読んで適当にreplyしたものの，いいっぱなしも申し訳ないので本当に速度に差が出るかを検証してみた．たぶん常識なのだろうけれど，僕は体験しないと理解できない愚者なので実験．

想定している状況として

• 機械学習などで用いる というペアのデータを扱うデータ構造のいくつかある選択肢のうち mapとvector> という2つを比較
• よく利用される内積計算に必要な全要素を舐めるという操作の時間を計測

当初の予想

• mapの実装は赤黒木なのに対してvectorは配列なので，要素が多くなったときにキャッシュミスが少なくて速いだろう．
  • (赤黒木は平衡2分木なので，配列で実装されていると思ったけれど，どうやら違うらしいということが後でわかる．)

こんなコードで実験．実験内容はこんな感じ．fidを生成するのに乱数を使っているのは，ここらへんのコードの書き方を思い出したかったから．しかも重複除去しているので，若干数が減っているのはご愛嬌．

なお，実験条件は以下のとおり．

• 実験条件
  • CPU: Core2Duo E8500 3.16GHz (32bit)
  • Memory: 4GB
  • Linux kernel: 2.6.26-2-686
  • gcc: 4.3.2
  • -O2オプション (-O3でも速度変わらず)

#include <iostream>
#include <cstdlib>
#include <vector>
#include <map>
#include <set>

#include <time.h>
#include <sys/time.h>

#define RAND ((double)rand() / (double)RAND_MAX)


double
gettimeofday_sec ()
{
  struct timeval tv;
  gettimeofday(&tv, NULL);
  return tv.tv_sec + (double)tv.tv_usec*1e-6;
}


int
get_rand (int min, int max)
{
  return (int) (((max - min) * RAND) + min);
}


std::set<int> *
get_int_set (int num, int min = 0, int max = 100000000)
{
  std::set<int> *s = new std::set<int>;
  for (int i = 0; i < num; i++) {
    s->insert( get_rand(min, max) );
  }
  return s;
}


void
test (int min, int max, int num)
{
  std::map<int, int> m;
  std::vector< std::pair<int, int> > v;
  
  std::set<int> *s = get_int_set( num, min, max );
  std::set<int>::iterator itr = s->begin();
  while ( itr != s->end() ) {
    m[ *itr ] = 1;
    v.push_back( std::pair<int, int>( *itr, 1 ) );
    ++itr;
  }

#ifdef MAP
  // map
  double t1 = gettimeofday_sec();
  double msum = 0.0;
  std::map<int, int>::iterator mitr = m.begin();
  while (mitr != m.end()) {
    msum += (mitr->first * mitr->second);
    ++mitr;
  }
  double t2 = gettimeofday_sec();
#endif

#ifdef VEC
  // vector
  double t3 = gettimeofday_sec();
  double vsum = 0.0;
  std::vector< std::pair<int, int> >::iterator vitr = v.begin();
  while (vitr != v.end()) {
    vsum += vitr->first * vitr->second;
    ++vitr;
  }
  double t4 = gettimeofday_sec();
#endif

  std::cout << "========================================" << std::endl;
  std::cout << "  min=" << min << " max=" << max << " num=" << num << std::endl;
  std::cout << "  idnum=" << v.size() << std::endl;
#ifdef MAP
  std::cout << "     map time=" << (t2 - t1) << " sec." << std::endl;
#endif
#ifdef VEC
  std::cout << "  vector time=" << (t4 - t3) << " sec." << std::endl;
#endif
  std::cout << "========================================" << std::endl;
}


int
main (int argc, char *argv[])
{
  test( 0, 100000000, 1000000 );
  test( 0, 100000000, 2000000 );
  test( 0, 100000000, 3000000 );

  return 0;
}

結果はこんな感じ．

% g++ -O2 -DMAP -DVEC map-vs-vector.cpp
% ./a.out
========================================
  min=0 max=100000000 num=1000000
  idnum=994988
     map time=0.0197878 sec.
  vector time=0.00178003 sec.
========================================
========================================
  min=0 max=100000000 num=2000000
  idnum=1980206
     map time=0.0388448 sec.
  vector time=0.00352812 sec.
========================================
========================================
  min=0 max=100000000 num=3000000
  idnum=2955469
     map time=0.05687 sec.
  vector time=0.00528502 sec.
========================================

また，とりあえず簡単にキャッシュミスを測れるvalgrindでL2キャッシュミス計測してみたのだけれど，手持ちの環境ではL2キャッシュミスを測れないよー，とWARNINGが出たので別の環境で検証予定．

% g++ -O2 -DMAP map-vs-vector.cpp
% velgrind --tool=cachegrind ./a.out
(うまく計測できなかったので割愛)

% g++ -O2 -DVECTOR map-vs-vector.cpp
% velgrind --tool=cachegrind ./a.out
(うまく計測できなかったので割愛)

というわけで全要素を舐める場合にmapは著しく不利であることがわかった．10倍程度の差が出たのは驚き．また，どうやらSTLのmap実装は右ノード，左ノードへのポインタを持っているらしく，それを追っかけるのにコストがかかっているのかなぁ (未検証)．平衡二分木なので配列でも持てる気がするのだけれど．

mapの利点は探索効率がよい (vectorのO(n)に対してO(log n)) のだけれど，今回の実験条件のように値がソートされている場合には，二分探索 (binary_search) が利用可能であるため，実はmapである利点はほとんどない気がする．なお，mapではなくソート済み配列を使おうぜ，というのはEffective STLの23項「連想コンテナをソート済みvectorに置き換えることを検討しよう」に詳しく書かれている．(mapが左右ノードへのポインタを保持する実装であることもこれで知った)

C++ (主にSTL) は色々便利だけれど，内部で何をやっているかということをきちんと理解しないと後で怪我をしそうなので，時間をみつけてこういう知識をちょくちょく貯めたいなぁ．

Effective STL―STLを効果的に使いこなす50の鉄則