MENU
計算科学屋が運営するウェブサイト
  1. Home
  2. プログラミング
  3. C/C++
  4. 【C++】std::vectorにおける要素追加の速度比較（push_back, reserve, resize）

【C++】std::vectorにおける要素追加の速度比較（push_back, reserve, resize）

C/C++
C++ Google Benchmark Open Source Software

C++において，std::vectorは動的確保可能な配列として非常によく利用されます．配列を動的に確保できることで非常に使いやすい一方で，配列を確保する方法に次第では速度に大きく影響します．

std::vectorはこれまでに数多く比較されていると思いますが，実際どの程度の差があるかを定量的に評価したものはあまり存在しません．

今回はstd::vectorの要素追加方法に関して，どの程度優位性があるのかを（割と真面目に）比較してみました．

std::vectorは便利です．正しく使いましょう．

目次

結論は？　push_back() vs reserve() vs resize()

当然ながら，resize()を利用する場合が最も高速です．

速度は速いほうから下記のような順番になります．これも当然の結果ですね．

resize() > reserve() > push_back()

Optimized C++ ―最適化、高速化のためのプログラミングテクニック
Amazon
楽天市場
Yahooショッピング

検証する内容

下記の内容で速度比較を行います．

1. push_back()を工夫せずに使用するパターン
2. reserve()でメモリ領域を確保した後に，push_back()を使用するパターン
3. push_back()ではなく，resize()で要素を追加するパターン

1. push_back()を工夫せずに使用するパターン

push_back()は配列の末尾に要素を追加するものです．追加する際に，予め確保したメモリでは足りない場合メモリ領域を再確保します．


std::size_t vec_size = 1000;
std::vector<T> vec;
for (std::size_t i = 0; i < vec_size; ++i) {
  vec.push_back(i);
}

2. reserve()でメモリ領域を確保した後に，push_back()を使用するパターン

reserve()は配列のメモリ領域(capacity())を確保する関数です．データは確保していないため，配列サイズ（size()）には影響しません．


std::size_t vec_size = 1000;
std::vector<T> vec;
vec.reserve(vec_size);
for (std::size_t i = 0; i < vec_size; ++i) {
  vec.push_back(i);
}

3. push_back()ではなく，resize()で要素を追加するパターン

resize()は指定した要素数に対し，一括で配列を動的確保します．resize()を使用する場合は，予めデータ数が分かっている必要があります．


std::size_t vec_size = 1000;
std::vector<T> vec;
vec.resize(vec_size);
for (std::size_t i = 0; i < vec_size; ++i) {
  vec[i] = i;
}

速度比較

先ほど述べた3つのパターンに対して，データサイズが16, 32, 64 bitの要素に対し速度比較を行います．16, 32, 64 bitデータはそれぞれshort, int, longを使用します．

std::vectorの要素数を1から10,000,000まで増加させて，その速度を計測します．

Google Benchmarkを使用して速度計測しています．

Google Benchmark

Google Benchmarkに関しては下記記事にまとめています．

あわせて読みたい
C++でのベンチマークテストのためにGoogle Benchmarkライブラリを利用する 便利なベンチマークツールは使うべし！ 単体テストは重要性は近年では広く周知されています．一方で，性能に関してはなかなか議論されることが多くありません． その一…

検証用コードは下記のようになります．当然ながら最適化時の速度を検証しなければ意味がないため，最適化オプションを使用しています．最適化オプションは-O2です．

#include <benchmark/benchmark.h>

#include <vector>

namespace {

static std::size_t max_range = 10000000;

template <class T> void BM_VectorPushBack(benchmark::State &state) {
  const std::size_t vec_size = state.range(0);
  for (auto _ : state) {
    std::vector<T> vec;
    vec.clear();
    for (std::size_t i = 0; i < vec_size; ++i) {
      vec.push_back(i);
    }
  }
}
BENCHMARK(BM_VectorPushBack<short>)->RangeMultiplier(10)->Range(1, max_range);
BENCHMARK(BM_VectorPushBack<int>)->RangeMultiplier(10)->Range(1, max_range);
BENCHMARK(BM_VectorPushBack<long>)->RangeMultiplier(10)->Range(1, max_range);

template <class T> void BM_VectorPushbackWithReserve(benchmark::State &state) {
  const std::size_t vec_size = state.range(0);
  for (auto _ : state) {
    std::vector<T> vec;
    vec.reserve(vec_size);
    vec.clear();
    for (std::size_t i = 0; i < vec_size; ++i) {
      vec.push_back(i);
    }
  }
}
BENCHMARK(BM_VectorPushbackWithReserve<short>)
    ->RangeMultiplier(10)
    ->Range(1, max_range);
BENCHMARK(BM_VectorPushbackWithReserve<int>)
    ->RangeMultiplier(10)
    ->Range(1, max_range);
BENCHMARK(BM_VectorPushbackWithReserve<long>)
    ->RangeMultiplier(10)
    ->Range(1, max_range);

template <class T> void BM_VectorIndex(benchmark::State &state) {
  std::size_t vec_size = state.range(0);
  for (auto _ : state) {
    std::vector<T> vec;
    vec.clear();
    vec.resize(vec_size);
    for (std::size_t i = 0; i < static_cast<std::size_t>(state.range(0)); ++i) {
      vec[i] = i;
    }
  }
}
BENCHMARK(BM_VectorIndex<short>)->RangeMultiplier(10)->Range(1, max_range);
BENCHMARK(BM_VectorIndex<int>)->RangeMultiplier(10)->Range(1, max_range);
BENCHMARK(BM_VectorIndex<long>)->RangeMultiplier(10)->Range(1, max_range);

template <class T>
void BM_VectorPushbackWithReserveReuse(benchmark::State &state) {
  const std::size_t vec_size = state.range(0);
  std::vector<T> vec;
  vec.reserve(vec_size);
  for (auto _ : state) {
    vec.clear();
    for (std::size_t i = 0; i < vec_size; ++i) {
      vec.push_back(i);
    }
  }
}
BENCHMARK(BM_VectorPushbackWithReserveReuse<short>)
    ->RangeMultiplier(10)
    ->Range(1, max_range);
BENCHMARK(BM_VectorPushbackWithReserveReuse<int>)
    ->RangeMultiplier(10)
    ->Range(1, max_range);
BENCHMARK(BM_VectorPushbackWithReserveReuse<long>)
    ->RangeMultiplier(10)
    ->Range(1, max_range);

template <class T> void BM_VectorIndexReuse(benchmark::State &state) {
  std::size_t vec_size = state.range(0);
  std::vector<T> vec;
  vec.resize(vec_size);
  for (auto _ : state) {
    for (std::size_t i = 0; i < static_cast<std::size_t>(state.range(0)); ++i) {
      vec[i] = i;
    }
  }
}
BENCHMARK(BM_VectorIndexReuse<short>)->RangeMultiplier(10)->Range(1, max_range);
BENCHMARK(BM_VectorIndexReuse<int>)->RangeMultiplier(10)->Range(1, max_range);
BENCHMARK(BM_VectorIndexReuse<long>)->RangeMultiplier(10)->Range(1, max_range);

} // namespace

BENCHMARK_MAIN();

16bitデータ

Fig. 1 Comparison of Elapsed time between various element size for 16 bit data
Number of vector element1. push_back()2. push_back after reserve()3. resize()
10.0170.0170.017
100.1210.0410.026
1000.4130.2370.097
10002.582.280.584
1000024225.55
10000028022150.9
100000034522240513
1000000033087224676231
経過時間（μs)

32bitデータ

Fig. 2 Comparison of Elapsed time between various element size for 32 bit data
Number of vector element1. push_back()2. push_back after reserve()3. resize()
10.0190.0180.018
100.1250.0380.027
1000.4110.2570.105
10002.572.150.601
1000023.421.15.1
10000022721152.8
100000025752311829
10000000421022691913753
経過時間（μs)

64bitデータ

Fig. 3 Comparison of Elapsed time between various element size for 64 bit data
Number of vector element1. push_back()2. push_back after reserve()3. resize()
10.0170.0180.018
100.1270.0370.025
1000.4280.2290.101
10002.732.150.589
1000024.6245.22
10000024221255.2
1000000319821871206
10000000605363130421332
経過時間（μs)

16, 32, 64 bitデータ間における速度比較

Fig. 4 Comparison between 16, 32 and 64 bit for 10,000,000 element size

考察

Fig. 1-3において，計算時間はstd::vectorの要素数にほぼ線形比例して増加しています．

対数グラフため見た目ではわかりにくいですが，1. と2. の間には1.5-2倍近い速度の差があります．また，resize()を使用した場合は，push_back()を使用した場合と比較して圧倒的に高速であることがわかります．

また，要素数が小さい場合（例えば要素サイズ10）では他の要素数の場合と比べてpush_back()が顕著に遅い結果になりました．要素数が大きくなるほどpush_back()とreserve()の差が小さくなっています．

要素数が小さい場合は，push_back()を使用するとより遅くなるということが推察できます．（要素数に関してはstd::vectorの定義時に確保されている量によると思いますので，環境依存すると思います．）

Fig. 4は，同じ要素数（10,000,000）によるデータサイズによる速度を比較した結果を見てみます．要素のデータサイズ（bit数）が大きくなることで，格納速度が低下していること確認できます．また，データサイズ（bit）が大きいほど，reserve()による高速化の効果が高いことがわかります．

上記の結果より，要素のデータサイズに関わらず要素の追加に関しては，push_back()を使用するよりもreserve()やresize()のほうが高速化することが示されました．

メモリ確保の時間を省略した場合の速度比較

メモリ確保の時間，すなわち「配列を新たに生成する場合と再利用する場合の差」を確認します．

reserve()でメモリ確保したstd::vectorを再利用する場合

「配列を新たに生成する場合」は，std::vectorの生成と領域確保reserve()をした後，push_backをします．


std::size_t vec_size = 10000000;
// ここから
std::vector<T> vec;
vec.reserve(vec_size);
for (std::size_t i = 0; i < vec_size; ++i) {
  vec.push_back(i);
}
// ここまで計測する

「再利用する場合」は，すでにreserve()された配列を使用します．再利用するため，std::vector.clear()によりデータを削除した後push_back()します．


std::size_t vec_size = 10000000;
std::vector<T> vec;
vec.reserve(vec_size);
// ここから
vec.clear();
for (std::size_t i = 0; i < vec_size; ++i) {
  vec.push_back(i);
}
// ここまで計測する

下記は，要素数10000000における速度を比較したものです．要素のデータサイズが大きいほど，再利用した効果が高いことが分かります．

この結果により，std::vectorにおいてreserve()およびresize()にはそれ相応の時間を要することが分かりました．可能な場合は，生成済みの配列を再利用すると高速化するでしょう．

resize()で確保したstd::vector()を再利用する場合

「配列を新たに生成する場合」は，std::vectorの生成と領域確保resize()をした後，データを代入します．


std::size_t vec_size = 10000000;
// ここから
std::vector<T> vec;
vec.resize(vec_size);
for (std::size_t i = 0; i < vec_size; ++i) {
  vec[i] = i;
}
// ここまで計測する

「再利用する場合」は，すでにresize()された配列を使用します．


std::size_t vec_size = 10000000;
std::vector<T> vec;
vec.resize(vec_size);
// ここから
for (std::size_t i = 0; i < vec_size; ++i) {
  vec[i] = i;
}
// ここまで計測する

reserve()の場合と同様に，再利用する場合の方が高速であることが分かりますが，また，resize()の再利用の方がreserve()と比較して顕著な差があります．

まとめ

Google Benchmarkを使用してstd::vectorの要素追加の速度検証を行いました．

push_back()により要素を追加するreserve()により予めメモリ確保することにより高速化が可能になります．格納するデータ型のサイズにもよりますが，reserve()を使用したほうが1.5-2倍程度高速化します．また，データ型のサイズ大きくなるにつれて，速度差が大きくなります

追加する要素数が既知の場合はresize()を使用することが可能になります．push_back()と比べるとresize()を使用したほうが3-5倍程度高速となります．

高速化プログラミング入門
Amazon
楽天市場
Yahooショッピング
C/C++
C++ Google Benchmark Open Source Software
よかったらシェアしてね！
目次