Dinkumware、お前には失望した

前回、VCのハッシュマップがあまりにも遅いことを疑問に思っていた。テストした結果、要素の検索が定数時間ではなく、対数時間だったのだ。さて、VC9のSP1も出たことだし、パフォーマンスの向上も謳っているので、さっそくunordered_setを試してみた。

前回のコードをそのまま実行すると、なぜかDinkmwareのunordered_setが動かない。いや、要素の挿入と検索はできるのだが、それから先が動かない。五分ほど考えて、check関数から戻っていないのだと結論した。しかしcheck関数が終わらない理由はひとつしかない。Dinkmwareのunordered_setのデストラクタが終わらないからだ。

ためしにデストラクタの実行にかかる時間を調べてみると、恐ろしく長い時間がかかっている。信じてくれ、百万件の要素を入れたunordered_setのデストラクタの実行を待つ間に昼寝ができる。もちろん、setやBoostのunordered_setでは、デストラクタの実行は一秒以内に終わる。いい加減、VCはDinkmwareと手を切ったほうが良いんじゃねえの。この前だってauto_ptrの本当にしょうもないバグがあったし。

しかし不思議なことに、clear()の実行にかかる時間を調べてみると、とても早い。しかも、clear()を呼び出した場合は、デストラクタの実行も早い。一体どうなっているんだ。clearはひょっとしたらメモリをリークしているのではないかと疑ったが、どうもリークしている気配はない。はて、これが例のVC++ブログに書いてあった、eraseのパフォーマンスに問題がある、と言うやつだろうか。しかしclearに問題は無いとはこれ如何に。

#include <iostream>
#include <set>
#include <unordered_set>
#include <boost/unordered_set.hpp>

template < typename SET >
void check(LARGE_INTEGER & end_user_code)
{
　　　　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 ;


　　　　QueryPerformanceCounter( &end_user_code ) ;
　　　　// clear()をコメントアウトすると、
　　　　// Dinkumwareのunordered_setのデストラクタが非常に遅くなる。
　　　　set.clear() ;

}

int main()
{
　　　　LARGE_INTEGER now, dt, freq ;
　　　　QueryPerformanceFrequency( &freq ) ;
　　　　
　　　　for ( int i = 0 ; i != 5 ; ++i )
　　　　{
　　　　　　　　check< std::set< unsigned int > >( now ) ;
　　　　　　　　QueryPerformanceCounter( &dt ) ;
　　　　　　　　std::cout << "destructer : " << double(dt.QuadPart - now.QuadPart) / double(freq.QuadPart) << std::endl ;
　　　　　　　　
　　　　　　　　check< boost::unordered_set< unsigned int > >( now ) ;
　　　　　　　　QueryPerformanceCounter( &dt ) ;
　　　　　　　　std::cout << "destructer : " << double(dt.QuadPart - now.QuadPart) / double(freq.QuadPart) << std::endl ;

　　　　　　　　check< std::tr1::unordered_set< unsigned int > >( now ) ;
　　　　　　　　QueryPerformanceCounter( &dt ) ;
　　　　　　　　std::cout << "destructer : " << double(dt.QuadPart - now.QuadPart) / double(freq.QuadPart) << std::endl ;

　　　　}
}

追記：
リリースビルドをすっかり忘れていた。リリースビルドならば、デストラクタの不可解で非現実的な遅さは解消された。リリースビルドの場合、要素の挿入はBoostより三割ほど遅いだけだが、しかし検索はstd::setの二分の一の時間かかる。Boostより十倍遅い。デストラクタもやはりBoostとは十倍遅いので、一桁が違うが。しかし、このままでは、デバッグビルドで実行ができない。
検索にかかる時間が気になる。std::setより二倍早いだけというのがどうも解せない。Boostの実装はstd::setより二十倍も早いだけに、なおさら不満だ。定数時間？
さらに、メモリ使用量も、Boostより多いようだ。うーん。不満たらたら。

追記2:
Checked Iteratorを無効にすると、Dinkumwareの実装は、Boostの実装に比べ、10倍の遅さから、5倍の遅さになった。