ややプログラム紀行

博士1年のプログラムに関する日記

Vectorの再利用

Vectorとかそういう系の動作速度はよく話題になりますが、僕も描画回りのプログラミングをしててその問題に当たりました

Push関数でデータをためていって、最後に一気に描画っていうスタイルなんですが、どうもデータをlistに積んでるところで処理が遅くなってるようです

調べてみたらすぐに検証してるサイトがありました

C++で大規模な配列追記のパフォーマンス

見てみると、listはvectorとかに比べて遅いですね

よく「listは挿入が速い」なんていわれるんで勘違いしがちですが、要素の間への挿入は速いけれど、末尾への挿入はvectorとかのほうが全然速いようです

これを読んでからvectorを使った実装にしてみたんですが、それでも少し遅い・・・

vectorの中身を見てみたときの記憶だと、一回要素を確保さえすれば、消してから再確保しても速いと思ってたので意外です(「vectorの中覗いたときの記事」、1年半前か・・・少し適当なこと書いてるかも)

計ってみると、事前確保している場合もしてないのとほぼ同タイム・・・!どういうこっちゃ

どうやらnewの処理速度はさして重要ではなく、push_back自体のオーバーヘッドが大きいようです

(ついでに書きますが、どうやらlistはpush_backのたびにnewをしてるようです、それで遅いんですね多分)

これでは描画処理よりデータ積むのに時間かかっちまう・・・

そこでvectorの再利用をしてみようと思います

再利用って言っても大したことではないんですが、今回扱っている2D描画に必要なデータはクラスとかではないただの数値なのでコンストラクタなどを呼ぶ必要がありません

なのでわざわざpush_backを使わないで演算子を使って直接データを入れようっていう計画です

まずpush_backと演算子ではどれくらいスピードが変わるのか確かめてみました

#include <iostream>

#include <chrono>

#include <vector>

using namespace std;

using namespace chrono;

void main()

{

vector<int> vec1, vec2;

vec1.resize(100000);

vec1.clear();

vec2.resize(100000);

system_clock::time_point start;

milliseconds result;

start = system_clock::now();

for (int i = 0; i < 100000; i++){

vec1.push_back(10);

}

result = duration_cast<milliseconds>(system_clock::now() - start);

cout << "----push_back----" << endl;

cout << result.count() << "ms" << endl << endl;

start = system_clock::now();

for (int i = 0; i < 100000; i++){

vec2[i] = 10;

}

result = duration_cast<milliseconds>(system_clock::now() - start);

cout << "----[]演算子----" << endl;

cout << result.count() << "ms" << endl << endl;

}

(なんか表示崩れとる・・・まあいいか)

結果:

----push_back----

41ms

----演算子----

5ms

みたいな感じになりました

一応説明しとくと、vec1はあらかじめ要素を確保することで、vector内のメモリプールは確保しておいてから、要素を全消し

vec2は要素を確保したらそのまま放置してます

そして要素挿入時はvec1は普通にpush_back、vec2は演算子で上書きをしてます

割と差が出ました

実際に使うときは、前フレームで確保した要素数より少ない間は[]演算子、要素数を超えた場合はpush_back、って感じで使い分けるといいかと思います

しかし描画でZオーダーで並び替えるの本当にめんどくさい・・・

並び替えはlistのほうが得意だけど、毎フレーム作り直すようなのは苦手だからなー

これは我流コンテナ・・・やるしかないのか・・・!