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 > >() ;
　　}
}