2008-05-06

unordered_setはどのくらい早いのか。

unorderd_setの速度を調べるために、以下のコードを書いた。VC9で実行した結果、以下のようになった。

class std::set<unsigned int,struct std::less<unsigned int>,class std::allocator<unsigned int> >
insert : 0.284398
find : 0.102093
class stdext::hash_set<unsigned int,class stdext::hash_compare<unsigned int,struct std::less<unsigned int> >,class std::allocator<unsigned int> >
insert : 0.293333
find : 0.0481863
class boost::unordered_set<unsigned int,struct boost::hash<unsigned int>,struct std::equal_to<unsigned int>,class std::allocator<unsigned int> >
insert : 0.14261
find : 0.00541996

もちろん、挿入や検索の仕方に問題があるのかもしれないが、なぜMSVCのhash_setはこんなに遅いのだろうか。unordered_setとはすこし違うが、しかしVC9のhash_setは、ドキュメントにこそかかれていないものの、TR1とほぼ同じ意識したつくりになっている。std::lessを使うことになっているのが問題なのだろうか。このコードでは、hash_setはboostのunordered_setに比べて非常に遅い。挿入が倍遅いのはともかくとして、検索が10倍遅いのは、とても気になる。

いろいろなことを試した。まずスレッドの優先度をリアルタイムにしてみたが、結果は同じであった。次に、_SECURE_SCLを0としてみたが、やはり結果は変わらなかった。何故こんなに遅いのだろう。最近出た、MSVCのunordered_setも試してみたいところだが。

template < typename SET >
void check()
{
  std::cout << typeid(SET).name() << std::endl ;

  LARGE_INTEGER now, dt, freq ;
  QueryPerformanceFrequency( &freq ) ;

  SET set ;

  QueryPerformanceCounter( &now ) ;
  for ( unsigned int i = 0 ; i != 1000000 ; ++i )
  {
    set.insert(i) ;
  }
  QueryPerformanceCounter( &dt ) ;

  std::cout << "insert : " << double(dt.QuadPart - now.QuadPart) / double(freq.QuadPart) << std::endl ;

  QueryPerformanceCounter( &now ) ;
  for ( unsigned int i = 0 ; i != 1000000 ; ++i )
  {
    set.find( i ) ;
  }
  QueryPerformanceCounter( &dt ) ;
  std::cout << "find : " << double(dt.QuadPart - now.QuadPart) / double(freq.QuadPart) << std::endl ;
}

int main()
{
  for ( int i = 0 ; i != 5 ; ++i )
  {
    check< std::set< unsigned int > >() ;
    check< stdext::hash_set< unsigned int > >() ;
    check< boost::unordered_set< unsigned int > >() ;
  }
}

1 comment:

You can use some HTML elements, such as <b>, <i>, <a>, also, some characters need to be entity referenced such as <, > and & Your comment may need to be confirmed by blog author. Your comment will be published under GFDL 1.3 or later license with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.