動機

OpenGLとかを使ってると大量の頂点情報をvectorに格納するとかをよくやらなきゃいけないんだけど。どうやったら美しく、高速にできるか考えてみた。

注）時間を計るために、

using namespace std::chrono;

class StopWatch{
public:
    void start(){timeStamp = system_clock::now();};
    double stop(){return (system_clock::now()-timeStamp).count();};

protected:
    time_point<std::chrono::system_clock>  timeStamp;
};

こんなクラスを作って使ってます。

また、vectorに格納するクラスは以下。

struct Vertex{
    Vertex(const float &x = 0.0, const float &y = 0.0, const float &z = 0.0):
    x(x),y(y),z(z){}
    float x,y,z;
};

push_back

参考のためにpush_backで10万個の頂点を初期化。

sw.start();
std::vector<Vertex> vertices;
for(int i = 0; i < 100000; i++){
    vertices.push_back(Vertex(0,0,0));
}
std::cout << "push_back:" << sw.stop() << std::endl;

処理時間4475マイクロ秒。

reserve + push_back

reserveで許容量を指定してからpush_backすれば、若干早くなるのではと思いやってみる。

sw.start();
std::vector<Vertex> vertices;
vertices.reserve(100000);
for(int i = 0; i < 100000; i++){
    vertices.push_back(Vertex(0,0,0));
}
std::cout << "push_back(reserve):" << sw.stop() << std::endl;

処理時間2422マイクロ秒。断然速い。reserveやらない手はないんだな。

emplace_back

sw.start();
std::vector<Vertex> vertices;
for(int i = 0; i < 100000; i++){
    vertices.emplace_back(0,0,0);
}
std::cout << "emplace_back:" << sw.stop() << std::endl;

処理時間3304マイクロ秒。自分でインスタンスを作るよりも速い。

vertices.push_back(Vertex(0,0,0)); を
vertices.push_back(std::move(Vertex(0,0,0)));
に置き換えると、大体同じくらいの速さで実行されるので、emplace_backは多分コピーしてないため速いのかな？

emplace_back + reserve

sw.start();
std::vector<Vertex> vertices;
vertices.reserve(100000);
for(int i = 0; i < 100000; i++){
    vertices.emplace_back(0,0,0);
}
std::cout << "emplace_back(reserve):" << sw.stop() << std::end;

2619マイクロ秒。単純なpush_backに比べると二倍の速さ、emplace_backとreserveを組み合わせるのが多分一番高速。

全て同じ値で埋める場合

全て同じ値でvectorを埋める場合は、コンストラクタの機能を使え、さらなる高速化ができる。

default_insert

デフォルト・インサートによる初期化。コンストラクタは全てデフォルト値が設定してあるので可能。

sw.start();
std::vector<Vertex> vertices(100000);
std::cout << "default insert:" << sw.stop() << std::endl;
sw.stop();

処理時間1639マイクロ秒。

fill

fillによる初期化。

sw.start();
std::vector<Vertex> vertices(100000, Vertex(0,0,0));
std::cout << "fill:" << sw.stop() << std::end;

1303マイクロ秒。面白いことに、デフォルト値を使うより速い。

考察

簡単にいうと、入れる値が全部同じなら、当たり前だがコンストラクタの（サイズ、値）を入れるのが一番速いようだ。この時にデフォルト値の使用は遅くなる。

要素数がわかっているなら、reserve + emplace_backのコンボが最強。

vectorの初期化

動機