2008-08-12

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倍の遅さになった。

No comments: