STL パフォーマンス計測

　何故か今ごろ（2003年2月）になってSTLを使いはじめてしまった。

　対称性や移植性は MFC のコレクションクラスよりも高く、強力＆便利なアルゴリズムも使用でき、とても有用なように思える。

　そのパフォーマンスが気になるので、VC++6.0 付属 STL について少し調べてみた。なお、環境はペン４ 1.8GHz、RAM512メガ、Win2K である。

■ 配列末尾への追加（push_back）

　単純に配列末尾にデータを追加する場合：


            vector<int> CPtrArray
    10,000     0.00       0.00
    30,000     0.00       0.01
   100,000     0.00       0.14
   300,000     0.02       1.03
 1,000,000     0.06      10.02
 3,000,000     0.16
10,000,000     0.59

　vector が配列サイズを倍々にするのに対し、CPtrArray はデフォルトでは要素をひとつづつ拡張するのでサイズが大きくなった場合のオーバーヘッドが大きい。

　サイズ拡張に時間を費やしていると思われるので、vector::reserve(), CPtrArray::SetSize() であらかじめ必要なサイズを確保した場合：


            vector<int> CPtrArray
    10,000     0.00       0.00
    30,000     0.00       0.00
   100,000     0.00       0.02
   300,000     0.00       0.00
 1,000,000     0.03       0.03
 3,000,000     0.11       0.08
10,000,000     0.33       0.27
30,000,000     0.98       0.83

　CPtrArray がわずか 10% ほど高速

　あらかじめサイズが分かっていれば reserve() でサイズ指定した方が2倍ほど高速だが、実時間の差はわずか。

　vector<CString> に対し、push_back(CString()) を実行した場合：


            vector<int> vector<CString>
    10,000     0.00       0.00
    30,000     0.00       0.01
   100,000     0.00       0.03
   300,000     0.02       0.14
 1,000,000     0.06       0.36

　vector の処理よりも CString コンストラクタ、コピー処理の方が時間を費やしている。

　push_back(CString()) の代わりに、あらかじめ作成しておいた CString オブジェクト str を push_back(str) した場合：


            vector<int> push_back(CString()) push_back(str)
    10,000     0.00           0.00           0.00
    30,000     0.00           0.01           0.01
   100,000     0.00           0.03           0.03
   300,000     0.02           0.14           0.14
 1,000,000     0.06           0.36           0.34

　ヌル文字列のコンストラクタはほとんど時間を費やしておらず、コピー処理の方が支配的である。

■ ソーティング

　ランダムシャフルされた vector<int> vecInt を sort(vecInt.begin(), vecInt.end()) でソート


              sort()
    10,000     0.00
    30,000     0.02
   100,000     0.01
   300,000     0.06
 1,000,000     0.22

　予想以上に高速。vector を sort() すると、CString の比較、交換処理が支配的になると思われる。


               int    CString
    10,000     0.00     0.01
    30,000     0.02     0.11
   100,000     0.01     0.44
   300,000     0.06     1.58
 1,000,000     0.22     6.13

　実際に確かめてみたのが上表。処理時間の90%以上がCString の比較、交換処理に費やされるよう。

　ランダムシャフルされた vector<int> vecInt を set<int> setInt に insert（insert すると昇順にソートされる）


              sort()  set::insert()
    10,000     0.00     0.03
    30,000     0.02     0.22
   100,000     0.01     0.88
   300,000     0.06     1.48
 1,000,000     0.22     7.66

　set<int>::insert() は O(log N) なので、全体の処理時間は sort() と同じ O(N logN）であるが、実時間は sort() よりもかなり遅い

　set はデータを常に昇順に保つという制約がある。sort() は最終結果のみを昇順にするので制約がゆるい。その分、sort() が高速である。