2020.02.13 プログラミング

【速度実験】vectorのpush_back()とemplace_back()はなにが違うのか？

はじめに

久しぶりの速度実験です．

今回も，C++のvectorについての調査実験です．

前回は，vectorのメモリ確保についての実験でした．

【関連記事】C++速度実験その２！vector配列の扱いについて

これが，意外と検索結果の上位に表示されているみたいで，多くの方々に閲覧されています．

稚拙な内容と文で，恥ずかしい思いと嬉しい思いが混ざっていますが，そんなワケで続編をやろう！となりました．

なお，本記事では小難しい話はしません，というか書いている私がまだ深く理解できていないので，下手なことを書くと誤解が生まれちゃうので...

push_back()とemplace_back()

さて本題です．

C++のvectorクラスは，C++利用者にとっては無視できないとても便利なコンテナクラスです．

他にも配列として扱えるクラスはありますが，とりあえずこれ使っとけっていうクラスです．

が，要素を格納する関数が２種類あります．

そう，push_back()とemplace_back()です．

emplace_back()はC++11から追加された関数です．

結果としては，同じ「要素を格納する関数」なのですが，何が違うのでしょうか？

コピーとムーブ

それは，要素をvectorに渡すときに生じます．

push_back()の場合，引数として受け取ったものをコピーするために一時的なオブジェクト生成がなされるようで，その際その引数のコピーコンストラクタやデストラクタが逐一呼ばれるようです．(あってるのかな)

が，それは無駄ということで，emplace_back()が登場しました．

emplace_back()は，引数として受け取ったもののクラスのコンストラクタ引数から，直接コンストラクトするため無駄がないとか．

...うーん，ちょっと複雑．

よくある話

push_back()とemplace_back()の話題は結構あって，検索するとたくさん出てきます．

そして結論として，「とりあえずemplace_back()を使っとけ」となっている記事が多いですね．

それを信じて私もそうしていましたが，どの程度速くなるのかは気になりますよね．

それでは，早速実験してみましょう．

実験条件

まずは共通の実験条件です．

コード全体は最後に載せますが，実験解説のときに使用するコードはその一部になります．

実験マシンスペック

OS	MacOS 10.15.3 (macbook pro 13 2018)
CPU	Intel(R) Core(TM) i7-8559U CPU @ 2.70GHz (4 cores)
RAM	16 GB

計測

時間の計測はchronoを使用してミリ秒単位で計測したのち，秒単位に直して観察します．

描画

今回は実験結果を比較しやすいようにグラフ描画を行いますが，その際matplotlibcppというライブラリを使用します．

PythonのmatplotlibをC++で使えるようにしてくれたヘッダオンリライブラリです．

ちょっと環境構築が面倒ですがC++でグラフ描画するなら，今のところ一番便利かな？

ソースは以下に載せておきます．

lava/matplotlib-cpp: Extremely simple yet powerful header-only C++ plotting library built on the popular matplotlib

実験1 : double型

まずは64bit浮動小数点型から．

void expt1(int size){
    vector<double> vec;
    vec.reserve(size);
    for(int i = 0; i < size; ++i)
        vec.emplace_back(0.1);
}

void expt2(int size){
    vector<double> vec;
    vec.reserve(size);
    for(int i = 0; i < size; ++i)
        vec.push_back(0.1);
}

void expt1(int size){

vector<double> vec;

vec.reserve(size);

for(int i = 0; i < size; ++i)

vec.emplace_back(0.1);

}

void expt2(int size){

vector<double> vec;

vec.reserve(size);

for(int i = 0; i < size; ++i)

vec.push_back(0.1);

}

この二つを，サイズ1万~100万までを1万刻みで与え，10試行平均を観察します．

スポンサードリンク

実験結果1

そんなに差は出ませんでしたね．

push_back()の方は，小さなデータサイズでかなり時間がかかっていますが，なぜなんでしょうね？

ちょっとわかりません，何かしらのオーバーヘッドでしょうか...

実験2 : 小さな適当Class

次は自分で作った適当なクラスを格納してみます．

今回はこんな適当クラスを用意してみました．

class Sample{
private:
    double x, y;
public:
    Sample(double x, double y): x(x), y(y){};
    ~Sample(){};
};

class Sample{

private:

double x, y;

public:

Sample(double x, double y): x(x), y(y){};

~Sample(){};

};

小さなクラスですが，どうなるでしょうか．

あ，ちなみにクラスを格納するときに， emplace_back(Sample(0.1, 0.1)) とやったらpush_back()と同じです．

emplace_back(0.1, 0.1) のようにコンストラクタの引数を渡すことでemplace_back()の良さが出るそう．

ちなみにサイズや試行回数は先ほどと同じです．

実験結果2

ややemplace_back()の方が速い...かな？

微妙ですね，そんなに大きな差ではなさそうです．(有意差は面倒なので調べてません)

まあそれもそのはず，大事なのはコピーのときに大きな計算コストがかかるかどうか，です．

今回はコピーコンストラクタを特に実装していなかったので，このような結果になったのしょう．

(push_back()の小さいサイズでの低速現象は，依然としてありますが，もう無視しましょう)

実験3 : コピーコンストラクタが重めのクラス

というワケで実装しなおしてみましょう．

クラスは以下のように改変．

class Sample{
private:
    double x, y;
public:
    Sample(double x, double y): x(x), y(y) {};
    // コピーコンストラクタ
    Sample(const Sample&){ for(int i = 0; i < 100; ++i){ /*ちょっとした処理*/} };
    ~Sample(){};
};

class Sample{

private:

double x, y;

public:

Sample(double x, double y): x(x), y(y) {};

// コピーコンストラクタ

Sample(const Sample&){ for(int i = 0; i < 100; ++i){ /*ちょっとした処理*/} };

~Sample(){};

};

ちょっとワケあって脳筋な実装だけど，よしとします．

実験結果3

ここで結構差が出ました．

やはり，push_back()とemplace_back()の大きな差はコピーですね．

でも，この結果から単純にemplace_back()の方が優れていると結論づけて良いのかどうか...

補足

ちなみに emplace_back(Sample(0.1, 0.1)) で実験すると，以下のようにどちらもコピーコンストラクタが呼ばれてしまい差は出ません．

実験4 : 文字列を要素とする場合

最後は文字列(string)クラスでやってみます．

void expt1(int size){
    vector<string> vec;
    vec.reserve(size);
    for(int i = 0; i < size; ++i)
        vec.emplace_back("sample text");
}

void expt2(int size){
    vector<string> vec;
    vec.reserve(size);
    for(int i = 0; i < size; ++i)
        vec.push_back("sample text");
}

void expt1(int size){

vector<string> vec;

vec.reserve(size);

for(int i = 0; i < size; ++i)

vec.emplace_back("sample text");

}

void expt2(int size){

vector<string> vec;

vec.reserve(size);

for(int i = 0; i < size; ++i)

vec.push_back("sample text");

}

なぜなら，よく使うクラスの中ではコピーコンストラクタが比較的重そうなクラスだから．

ちなみにstringのコピーコンストラクタでは，メモリ領域確保に加え，forループによるchar配列コピーが行われているようです．

(↓参考: C/C++ ポインタ入門 > 文字列クラス > コピーコンストラクタ)

// stringのコピーコンストラクタ
String::String(const String &x)
    : m_allocSize(x.m_allocSize)  // キャパシティを初期化
    , m_data(new char[x.m_allocSize])    // 文字列領域を初期化
    , m_size(x.m_size)      // サイズを初期化
{
    for(int i = 0; i <= m_size; ++i) {
        m_data[i] = x.m_data[i];            // '\0' まで文字をコピー
    }
}

// stringのコピーコンストラクタ

String::String(const String &x)

: m_allocSize(x.m_allocSize) // キャパシティを初期化

, m_data(new char[x.m_allocSize]) // 文字列領域を初期化

, m_size(x.m_size) // サイズを初期化

{

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

m_data[i] = x.m_data[i]; // '\0' まで文字をコピー

}

実験結果4

やはり結果に差が出ましたね．

stringを格納するならばemplace_back()の方が速いです．

まとめ

今回はvectorのpush_back()とemplace_back()の比較実験を行いました．

結論としては「とりあえずemplace_back()使っとけ」は間違ってはなさそうです．

特にコピーコンストラクタが重めのものはemplace_back()が力を発揮します．

それより，データサイズが小さいときにpush_back()が遅いのはなぜ？？

実験に使用したコード

main.cpp

/**
 * C++速度実験：vectorのpush_back()とemplace_back()について
 * 
 * @author Hiroshi ARAKI
 * @copyright Hiroshi ARAKI
 * @date 2020.01.13
 */

#include <iostream>
#include <vector>
#include <chrono>
#include <map>
#include <string>

#include "matplotlibcpp.h"

#define MINIMUM_SIZE 10000    // vector最小サイズ
#define MAXIMUM_SIZE 1000000  // vector最大サイズ


using namespace std;
namespace plt = matplotlibcpp;


/**
 * サンプルクラス
 */
class Sample{
private:
    double x, y;
public:
    Sample(double x, double y): x(x), y(y) {};
    // コピーコンストラクタ
    Sample(const Sample&){ for(int i = 0; i < 100; ++i){ /*ちょっとした処理*/} };
    ~Sample(){};
};

/**
 * 実験１
 * @param size
 */
void expt1(int size){
    vector<Sample> vec;
    vec.reserve(size);
    for(int i = 0; i < size; ++i)
        vec.emplace_back(Sample(0.1, 0.1));
}

/**
 * 実験２
 * @param size
 */
void expt2(int size){
    vector<Sample> vec;
    vec.reserve(size);
    for(int i = 0; i < size; ++i)
        vec.push_back(Sample(0.1, 0.1));
}

int main() {
    int trial = 10;  // 試行回数

    // 描画用 (x-axis)
    vector<double> x;
    x.reserve(1000);
    for(int s = MINIMUM_SIZE; s <= MAXIMUM_SIZE; s += MINIMUM_SIZE)
        x.emplace_back(s);

    // 結果記録用
    vector<double> results1(MAXIMUM_SIZE / MINIMUM_SIZE, 0);
    vector<double> results2(MAXIMUM_SIZE / MINIMUM_SIZE, 0);

    // 時間記録用
    chrono::system_clock::time_point start, end;

    /* 実験１ */
    for(int t = 0; t < trial; ++t) {
        cout << "Expt1: Trial " << t << "/" << trial << endl;
        for(int s = MINIMUM_SIZE; s <= MAXIMUM_SIZE; s += MINIMUM_SIZE){
            start = chrono::system_clock::now();
            expt1(s);
            end = chrono::system_clock::now();
            results1[s / MINIMUM_SIZE] += chrono::duration_cast<chrono::milliseconds>( end - start ).count() / 1000.0;
        }
    }


    /* 実験２ */
    for(int t = 0; t < trial; ++t) {
        cout << "Expt2: Trial " << t << "/" << trial << endl;
        for(int s = MINIMUM_SIZE; s <= MAXIMUM_SIZE; s += MINIMUM_SIZE){
            start = chrono::system_clock::now();
            expt2(s);
            end = chrono::system_clock::now();
            results2[s / MINIMUM_SIZE] += chrono::duration_cast<chrono::milliseconds>( end - start ).count() / 1000.0;
        }
    }

    // 10試行平均時間にする
    for(auto& res: results1) {
        res /= static_cast<double>(trial);
    }
    for(auto& res: results2) {
        res /= static_cast<double>(trial);
    }

    // 実験１の描画
    map<string, string> args1{
            {"label", "emplace_back()"},
            {"c", "blue"}
    };
    plt::plot(x, results1, args1);

    // 実験２の描画
    map<string, string> args2{
            {"label", "push_back()"},
            {"c", "orange"}
    };
    plt::plot(x, results2, args2);


    plt::xlabel("vector size");
    plt::ylabel("elapsed time [sec]");
    plt::legend();
    plt::save("result.png");

    return 0;


}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

/**

* C++速度実験：vectorのpush_back()とemplace_back()について

* @author Hiroshi ARAKI

* @copyright Hiroshi ARAKI

* @date 2020.01.13

#include <iostream>

#include <vector>

#include <chrono>

#include <map>

#include <string>

#include "matplotlibcpp.h"

#define MINIMUM_SIZE 10000 // vector最小サイズ

#define MAXIMUM_SIZE 1000000 // vector最大サイズ

using namespace std;

namespace plt = matplotlibcpp;

/**

* サンプルクラス

class Sample{

private:

double x, y;

public:

Sample(double x, double y): x(x), y(y) {};

// コピーコンストラクタ

Sample(const Sample&){ for(int i = 0; i < 100; ++i){ /*ちょっとした処理*/} };

~Sample(){};

};

/**

* 実験１

* @param size

void expt1(int size){

vector<Sample> vec;

vec.reserve(size);

for(int i = 0; i < size; ++i)

vec.emplace_back(Sample(0.1, 0.1));

}

/**

* 実験２

* @param size

void expt2(int size){

vector<Sample> vec;

vec.reserve(size);

for(int i = 0; i < size; ++i)

vec.push_back(Sample(0.1, 0.1));

}

int main() {

int trial = 10; // 試行回数

// 描画用 (x-axis)

vector<double> x;

x.reserve(1000);

for(int s = MINIMUM_SIZE; s <= MAXIMUM_SIZE; s += MINIMUM_SIZE)

x.emplace_back(s);

// 結果記録用

vector<double> results1(MAXIMUM_SIZE / MINIMUM_SIZE, 0);

vector<double> results2(MAXIMUM_SIZE / MINIMUM_SIZE, 0);

// 時間記録用

chrono::system_clock::time_point start, end;

/* 実験１ */

for(int t = 0; t < trial; ++t) {

cout << "Expt1: Trial " << t << "/" << trial << endl;

for(int s = MINIMUM_SIZE; s <= MAXIMUM_SIZE; s += MINIMUM_SIZE){

start = chrono::system_clock::now();

expt1(s);

end = chrono::system_clock::now();

results1[s / MINIMUM_SIZE] += chrono::duration_cast<chrono::milliseconds>( end - start ).count() / 1000.0;

}

/* 実験２ */

for(int t = 0; t < trial; ++t) {

cout << "Expt2: Trial " << t << "/" << trial << endl;

for(int s = MINIMUM_SIZE; s <= MAXIMUM_SIZE; s += MINIMUM_SIZE){

start = chrono::system_clock::now();

expt2(s);

end = chrono::system_clock::now();

results2[s / MINIMUM_SIZE] += chrono::duration_cast<chrono::milliseconds>( end - start ).count() / 1000.0;

}

// 10試行平均時間にする

for(auto& res: results1) {

res /= static_cast<double>(trial);

}

for(auto& res: results2) {

res /= static_cast<double>(trial);

}

// 実験１の描画

map<string, string> args1{

{"label", "emplace_back()"},

{"c", "blue"}

};

plt::plot(x, results1, args1);

// 実験２の描画

map<string, string> args2{

{"label", "push_back()"},

{"c", "orange"}

};

plt::plot(x, results2, args2);

plt::xlabel("vector size");

plt::ylabel("elapsed time [sec]");

plt::legend();

plt::save("result.png");

return 0;

}

CMakeLists.txt

matplotlibcppを使用する場合のCmakeLists.txtは以下のように書く必要があります．

適当に参考にしてください．

cmake_minimum_required(VERSION 3.14)
project(expt)

set(CMAKE_CXX_STANDARD 14)

find_package(Python3 COMPONENTS Development NumPy)
add_executable(expt main.cpp)

target_include_directories(expt PRIVATE ${Python3_INCLUDE_DIRS} ${Python3_NumPy_INCLUDE_DIRS})
target_link_libraries(expt Python3::Python Python3::NumPy)

cmake_minimum_required(VERSION 3.14)

project(expt)

set(CMAKE_CXX_STANDARD 14)

find_package(Python3 COMPONENTS Development NumPy)

add_executable(expt main.cpp)

target_include_directories(expt PRIVATE ${Python3_INCLUDE_DIRS} ${Python3_NumPy_INCLUDE_DIRS})

target_link_libraries(expt Python3::Python Python3::NumPy)

おしまい．

【速度実験】vectorのpush_back()とemplace_back()はなにが違うのか？

はじめに

push_back()とemplace_back()

コピーとムーブ

よくある話

実験条件

実験マシンスペック

計測

描画

実験1 : double型

実験結果1

実験2 : 小さな適当Class

実験結果2

実験3 : コピーコンストラクタが重めのクラス

実験結果3

補足

実験4 : 文字列を要素とする場合

実験結果4

まとめ

実験に使用したコード

main.cpp

CMakeLists.txt

おすすめの関連記事