the difference of processing speed with various "push back" method

result.md

Result

All the results are shown in second.

benchmark A

Debug

num	push_back	resize	reserve	emplace_back	reserve alt	resize alt
0	0	0	0	0	0	0
2000000	1.39	0.422	0.984	1.312	0.953	0.406
4000000	2.813	0.843	1.985	2.734	1.906	0.797
6000000	4.188	1.281	2.969	4.094	2.859	1.187
8000000	5.797	1.703	3.969	5.687	3.844	1.61
10000000	6.797	2.125	4.969	6.625	4.766	1.985

Release

num	push_back	resize	reserve	emplace_back	reserve alt	resize alt
0	0	0	0	0	0	0
2000000	0.047	0.016	0.015	0.031	0.016	0.016
4000000	0.093	0.047	0.031	0.063	0.031	0.015
6000000	0.125	0.047	0.046	0.11	0.016	0.031
8000000	0.187	0.079	0.062	0.156	0.031	0.032
10000000	0.188	0.079	0.078	0.172	0.047	0.047

benchmark B

Debug

num	push_back	resize	reserve	emplace_back	reserve alt	push back alt	push back alt move
0	0	0	0	0	0	0	0
1000000	1.063	0.594	0.687	0.969	0.625	1.234	1.078
2000000	2.157	1.156	1.391	2.047	1.25	2.562	2.25
3000000	3.266	1.735	2.047	3.063	1.86	3.828	3.375
4000000	4.562	2.297	2.735	4.282	2.485	5.312	4.703
5000000	5.234	2.906	3.422	4.875	3.094	6.172	5.422

Release

num	push_back	resize	reserve	emplace_back	reserve alt	push back alt	push back alt move
0	0	0	0	0	0	0	0
1000000	0.094	0.109	0.062	0.078	0.063	0.14	0.094
2000000	0.187	0.235	0.14	0.172	0.125	0.266	0.187
3000000	0.266	0.328	0.187	0.266	0.203	0.407	0.282
4000000	0.391	0.453	0.266	0.375	0.266	0.563	0.375
5000000	0.453	0.594	0.313	0.453	0.297	0.64	0.406

vector_push_A.cpp

#include <vector>
#include <fstream>
#include <iostream>
#include <iomanip>
#include <Windows.h>

class A
{
public:
  A()
  {
    a = 100;
  }
  A(int i)
  {
    a = i;
  }
  int a;
  int b;
  int c;
};

void makeVector(int vector_size, const int vtype, std::ofstream &ofile)
{
  std::vector<A> vector;
  DWORD start = GetTickCount();
  switch (vtype)
  {
  case 1:
    //push back
    for (int i = 0; i < vector_size; i++)
    {
      vector.push_back(A(i));
    }
    break;
  case 2:
    //resize
    vector.resize(vector_size);
    for (int i = 0; i < vector_size; i++)
    {
      vector[i] = A(i);
    }
    break;
  case 3:
    //reserve
    vector.reserve(vector_size);
    for (int i = 0; i < vector_size; i++)
    {
      vector.push_back(A(i));
    }
    break;
  case 4:
    //emplace back
    for (int i = 0; i < vector_size; i++)
    {
      vector.emplace_back(i);
    }
    break;
  case 5:
    //reserve alt
    vector.reserve(vector_size);
    for (int i = 0; i < vector_size; i++)
    {
      vector.emplace_back(i);
    }
    break;
  case 6:
    //resize alt
    vector.resize(vector_size);
    for (int i = 0; i < vector_size; i++)
    {
      vector[i].a = i;
    }
    break;
  default:
    break;
  }
  DWORD end = GetTickCount();
  std::cout << vtype << std::endl;
  double time = (double)(end - start) / 1000.0;
  std::cout << "duration = " << time << "sec.\n";
  size_t capacity = vector.capacity();
  std::cout << "size" << vector.size() << std::endl;
  std::cout << "capacity" << capacity << std::endl;
  ofile << "," <<std::setprecision(16)<< time;
}

int main()
{
  std::cout << "start" << std::endl;

  std::ofstream ofile;
  ofile.open("comp.csv");
  ofile << "num,push_back,resize,reserve,emplace_back,reserve alt,resize alt\n";
  const int max = 10000000;
  for (int i = 0; i <= max; i += max/5)
  {
    ofile << i;
    makeVector(i, 1, ofile);
    makeVector(i, 2, ofile);
    makeVector(i, 3, ofile);
    makeVector(i, 4, ofile);
    makeVector(i, 5, ofile);
    makeVector(i, 6, ofile);
    ofile << std::endl;
  }
  ofile.close();
  return 0;
}

vector_push_B.cpp

#include <vector>
#include <fstream>
#include <iostream>
#include <iomanip>
#include <Windows.h>

class A
{
public:
  A(int size_)
  {
    size = 10;
    arr = new double[size];
  }

  A() = default;

  // move ctor
  A(A&& o) noexcept
  {
    size = o.size;
    arr = o.arr;
    o.arr = nullptr;
  }

  // copy ctor
  A(const A& o)
  {
    size = o.size;
    arr = new double[size];
    memcpy(arr, o.arr, size);
  }

  A &operator=(const A &o)
  {
    if (this != &o)
    {
      size = o.size;
      arr = new double[size];
      memcpy(arr, o.arr, size);
    }
    return *this;
  }

  ~A()
  {
    delete[] arr;
  }

private:
  double* arr;
  int size;
};

void makeVector(int vector_size, const int vtype, std::ofstream &ofile)
{
  std::vector<A> vector;
  DWORD start = GetTickCount();
  switch (vtype)
  {
  case 1:
    //push back
    for (int i = 0; i < vector_size; i++)
    {
      vector.push_back(A(i));
    }
    break;
  case 2:
    //resize
    vector.resize(vector_size);
    for (int i = 0; i < vector_size; i++)
    {
      vector[i] = A(i);
    }
    break;
  case 3:
    //reserve
    vector.reserve(vector_size);
    for (int i = 0; i < vector_size; i++)
    {
      vector.push_back(A(i));
    }
    break;
  case 4:
    //emplace back
    for (int i = 0; i < vector_size; i++)
    {
      vector.emplace_back(i);
    }
    break;
  case 5:
    //reserve alt
    vector.reserve(vector_size);
    for (int i = 0; i < vector_size; i++)
    {
      vector.emplace_back(i);
    }
    break;
  case 6:
    //push back alt
    for (int i = 0; i < vector_size; i++)
    {
      auto item = A(i);
      vector.push_back(item);
    }
    break;
  case 7:
    //push back alt move
    for (int i = 0; i < vector_size; i++)
    {
      auto item = A(i);
      vector.push_back(std::move(item));
    }
    break;
  default:
    break;
  }
  DWORD end = GetTickCount();
  std::cout << vtype << std::endl;
  double time = (double)(end - start) / 1000.0;
  std::cout << "duration = " << time << "sec.\n";
  size_t capacity = vector.capacity();
  std::cout << "size" << vector.size() << std::endl;
  std::cout << "capacity" << capacity << std::endl;
  ofile << "," << std::setprecision(16) << time;
}

int main()
{
  std::cout << "start" << std::endl;

  std::ofstream ofile;
  ofile.open("comp.csv");
  ofile << "num,push_back,resize,reserve,emplace_back,reserve alt,push back alt,push back alt move\n";
  const int max = 5000000;
  for (int i = 0; i <= max; i += max / 5)
  {
    ofile << i;
    makeVector(i, 1, ofile);
    makeVector(i, 2, ofile);
    makeVector(i, 3, ofile);
    makeVector(i, 4, ofile);
    makeVector(i, 5, ofile);
    makeVector(i, 6, ofile);
    makeVector(i, 7, ofile);
    ofile << std::endl;
  }
  ofile.close();
  return 0;
}

Benchmark A

Debug

• グループ1: 領域再割当てが入る → 最遅
• グループ2: 領域再割当てが入らない push_back
• グループ3: 代入時のオーバーヘッドが一番少ない？

Release

• グループ2と3の差が詰まっている
• reserve_alt resize_alt がコンストラクタ呼ばれる回数最小なので、最速になる

Benchmark B

Debug

• move セマンティクスを使えない push back alt が圧倒的に遅い
• グループ1: 領域再割当てが入る → 遅い
• グループ2: 領域再割当てなし
• reserve より reserve_alt が速い → emplace_back の効果が見える

Release

• コンストラクタを無駄に呼ぶ必要がある resize が遅くなる？