みんな元気にしてたかい。vector, list, deque, setのパフォーマンス実験を再びやってみたよ。前回との違いは以下の点だ。
- findやinsertをテストする箇所は、コンテナの中の固定位置に対してのみ行っていたが、今度は乱数を使ってコンテナの中のランダムな場所や値に対してテストするようにした。
- insertやeraseは、入力のイテレータをadvanceなどで作成している時間も含めて計測してしまっていたものを、今回は純粋に処理を行っている部分のみを計測するようにした。
- 時間計測には標準関数のclock()を使用していたのだがこれをやめ、WindowsOSの中でも最高精度を誇るマルチメディアタイマーを使用するようにした。(ExclusiveMMTimerもちょっとだけバージョンアップしたので気になる人はチェックしてみてくれ)（あまり変わらなかったが）
- VisualStudio2008SP1の標準のSTLと、STLport5.2.1とで、比較実験を行った。
でも結果はやっぱり前回の日記の結論をひっくり返すようなことにはならなかった。以下が実験に使ったコードだ。前回のよりはすっきりしたかな。
#include <windows.h> #include <mmsystem.h> #include <iostream> #include <vector> #include <list> #include <algorithm> #include <ctime> #include <set> #include <deque> #include <string> using namespace std; #define N 1000000 #define P 4000 class ExclusiveMMTimer{ // // Exclusive Multi-Media-Timer Wrapper (C) 2009 nursmaul // version 1.0 // // CB concept: void cb( ExclusiveMMTimer* mm ) // // interval ごとに、別スレッドにてcbを呼びます。 // 前回のcb呼び出しが終わらないうちに、また別のスレッドで // 次のcbが呼ばれないように、排他制御をサポートしています。 // // このため、cbの処理の一番最後（cbでPostMessageしたならそのPostMessageの // ハンドラ処理の最後）において、本クラスのReleaseExclusive() を呼ぶようにします。 // //#include <windows.h> //#include <mmsystem.h> //#pragma comment( lib, "winmm.lib" ) と、 // LONGLONG ExclusiveMMTimer::m_exclusive_counter; // を、CPPコードのどこかに挿入して下さい。 // protected: ExclusiveMMTimer( UINT interval ) :m_interval( interval ), m_elapsed(0), m_last(0) { m_exclusive_counter=0; } public: virtual ~ExclusiveMMTimer( void ){} template< class T > static ExclusiveMMTimer* Create( T cb, UINT interval, UINT resolution ){ // ヘルパー関数だよ return new ExclusiveMMTimerSub< typename T >( cb, interval, resolution ); } static ExclusiveMMTimer* Create( UINT interval, UINT resolution ); static LONGLONG ReleaseExclusive( void ){ return ::InterlockedDecrement64( &m_exclusive_counter ); } virtual void CallBack( void )=0; const LONGLONG Elapsed( void ) const { return m_elapsed; } const LONGLONG ElapsedStep( void ){ LONGLONG tmp = m_elapsed-m_last; m_last = m_elapsed; return tmp; } public: static LONGLONG m_exclusive_counter;// 排他処理用 UINT m_timer_id; UINT m_interval; LONGLONG m_elapsed; LONGLONG m_last; }; template< class CB > class ExclusiveMMTimerSub: public ExclusiveMMTimer { public: ExclusiveMMTimerSub( CB cb, UINT interval, UINT resolution ) :m_cb( cb ), ExclusiveMMTimer( interval ) { m_timer_id = ::timeSetEvent( interval, resolution, (LPTIMECALLBACK)ExclusiveMMTimerSub::lc_timerCB, (DWORD_PTR)this, TIME_PERIODIC ); } ~ExclusiveMMTimerSub( void ){ ::timeKillEvent( m_timer_id ); } void CallBack( void ){ m_cb( this ); m_elapsed += m_interval; } static void CALLBACK lc_timerCB( UINT uTimerID, UINT uMsg, DWORD dwUser, DWORD dw1, DWORD dw2){ ExclusiveMMTimer* stb = reinterpret_cast<ExclusiveMMTimer*>( dwUser ); if( ::InterlockedExchangeAdd64( &stb->m_exclusive_counter, 1 ) ==0 ){ stb->CallBack(); } return; } private: CB m_cb; }; #pragma comment( lib, "winmm.lib" ) LONGLONG ExclusiveMMTimer::m_exclusive_counter; class MyCallback{ public: MyCallback( void ){} public: void operator()( ExclusiveMMTimer* mm ){ // 排他処理完了を通知（これを忘れると次のインターバルでCBに飛んでこない） ExclusiveMMTimer::ReleaseExclusive(); } }; // Add template< class Cont > void Add( Cont& cont, int val ){ cont.push_back( val ); } template<> void Add< set<int> >( set<int>& cont, int val ){ cont.insert( val ); } // Find template< class Cont > typename Cont::iterator Find( Cont& cont, int val ){ return find( cont.begin(), cont.end(), val ); } template<> typename set<int>::iterator Find< set<int> >( set<int>& cont, int val ){ return cont.find( val ); } //Sort template< class Cont > void Sort( Cont& _cont ){ sort( _cont.begin(), _cont.end() ); } template<> void Sort<list<int>>( list<int>& _cont ){ _cont.sort(); } template<> void Sort<set<int>>( set<int>& _cont ){} //RemoveIf >4000 template< class Cont > void RemoveIfGt4k( Cont& cont ) { cont.erase( remove_if( cont.begin(), cont.end(), bind2nd( greater<int>(), P ) ), cont.end() ); } template<> void RemoveIfGt4k<set<int>>( set<int>& cont ) { return; } template< class Cont > struct testContainer { typedef typename Cont::iterator ContIter; testContainer( void ){} void operator()( void ){ ExclusiveMMTimer* mm = // 時間計測用 ExclusiveMMTimer::Create( MyCallback(), 1, 1 ); // setup { for( int i=0; i<N; ++i ) Add( _cont, i ); cout<< mm->ElapsedStep() << " ms setup "<< N <<" elems."<<endl; } // sort { Sort( _cont ); cout<< mm->ElapsedStep() << " ms sort()"<<endl; } // find { for( int i=0; i<1000; ++i ){ Find( _cont, rand()/(float)RAND_MAX*_cont.size() ); }// i cout<< mm->ElapsedStep() << " ms 1000 times find()"<<endl; } // find and erase { unsigned int cnt=0; for( int i=0; i<1000; ++i ){ ContIter it = Find( _cont, rand()/(float)RAND_MAX*_cont.size() ); if( it!=_cont.end() ){ mm->ElapsedStep(); _cont.erase( it ); cnt += mm->ElapsedStep(); } }// i cout<< cnt << " ms 1000 times erase()"<<endl; } // advance { for( int i=0; i<1000; ++i ){ ContIter it = _cont.begin(); int val = rand()/(float)RAND_MAX*(_cont.size()-1); advance( it, val ); } cout<< mm->ElapsedStep() << " ms 1000 times advance()"<<endl; } // insert { unsigned int cnt=0; for( int i=0; i<1000; ++i ){ ContIter it = _cont.begin(); int val = rand()/(float)RAND_MAX*(_cont.size()-10); advance( it, val ); mm->ElapsedStep(); _cont.insert( it, 88 ); cnt += mm->ElapsedStep(); } cout<< cnt << " ms 1000 times insert()"<<endl; } // remove_if gt 4k { mm->ElapsedStep(); RemoveIfGt4k( _cont ); cout << mm->ElapsedStep() <<" ms remove_if() gt 4k"<<endl; } delete mm; cout<<endl; } Cont _cont; }; int main( int argc, char* argv[] ) { vector< int > vec; list< int > lst; set< int > st; deque< int > qu; cout<< "vector"<<endl; testContainer< vector<int> >()(); cout<< "list"<<endl; testContainer< list<int> >()(); cout<< "deque"<<endl; testContainer< deque<int> >()(); cout<< "set"<<endl; testContainer< set<int> >()(); const float cps = static_cast< const float >( CLOCKS_PER_SEC ); { set< int > st; for( int i=0; i<N; ++i ){ st.insert( i ); }// i size_t n = st.size(); clock_t ri1 = clock(); for( int i=P; i<n; ++i ){ set< int >::iterator it = st.find( i ); if( it!= st.end() ) st.erase( it ); }// i clock_t ri2 = clock(); cout << "find >"<<P<<" and erase set: " << (ri2-ri1)/cps << endl; cout << endl; } return 0; }
出力：
[VC9(VC2008)SP1の付属STL]/[STLPort5.2.1]の比較結果は以下。（単位はms）
| operation | vector | list | deque | set |
| setup | 9/5 | 68/43 | 18/8 | 182/116 |
| sort | 15/12 | 113/52 | 160/25 | - |
| find() | 259/1 | 2093/14551 | 2238/370 | 1/1 |
| erase() | 224/226 | 1/1 | 2843/443 | 2/1 |
| advance | 1/0 | 2180/9626 | 1/1 | 6775/6723 |
| insert | 205/207 | 4/4 | 2908/474 | 0/0 |
| remove_if() | 1/1 | 46/36 | 7/3 | - |
これを見てまずわかることは以下のような感じか。
- STLportは全般にVC++9のSTLより若干高速めだ。
- vectorのfindは、STLportだとどうしちゃったのと聞きたいくらい超高速だ。とても同じコンテナとは思えない。これはプログラミングパラダイムのシフトにすらなりえるのではないか。（一応何度か確認したが私の計測ミス・バグ・勘違いだったらご指摘を）
- dequeの実装ははるかにSTLportの方がましなようだ。
- vectorのeraseはSTLportの方がちょっとだけ遅いが、同等であるともいえる程度だ。
- STLportは、listのadvance, findのパフォーマンスが、明らかにVC++9のSTLのそれに劣る。
まあ５点目については、listではadvanceやfindなんて使う意味がないし、使う場面自体がないので問題はないはず。逆に言うとlistでfindやadvanceは速くなくていいのである。しかしもし、既存コードがそのように書かれてしまっており、もはや変えられないという場合は、この点は考慮しなくてはならないだろう。（コードの方を変えることをオススメするが。そこはコストをかけてもいい改善項目だろう。）
パフォーマンス云々とは別に、STLportは非標準の魅力あるコンテナやアダプタ（unary_compose, binary_compose、hash_map, その他たくさん）が使えるのはとても魅力的だ。あとSTLportのライセンス的にもとても使いやすいのも魅力的だ。まあ一度非標準を使っちゃうと標準に戻れなくなるということもあるが。
STLportは有名だしみんな使ってる。EffectiveSTLでも一部解説があるほどだ。導入も前に日記に書いたようにとても簡単だ。
最後に本計測ではコンテナのパラメータにはintを使用したが、STLコンテナを本格的に使う場合はポインタを格納するケースが殆どなので、本計測の結果は実用開発案件でのコンテナ検討材料としても十分なものだとおじさんは考えているよ。
