コンテナへの挿入の速度について

C++エクササイズ。今回は挿入の速度に的を絞って計測してみた。

やったこと

ランダムな整数値を50000個生成
整数値をコンテナに挿入する
2の操作を各コンテナにつき10回繰り返す

vectorについてはさらに3つの異なる条件でも実験してみた。

(R) ... あらかじめ領域をreserveする
(RS) ... setは挿入時に値をソートし、ユニークかどうかのチェックもするので、vectorで同等の後処理をする（vector + sort + unique）
(RSS) ... 後処理ではなく、挿入時にユニークかどうかを二分岐探索でチェックする（よりsetに近い挙動）

結果

（単位：秒）

vector<int>     0.0305866
vector<int>(R)  0.00266554
vector<int>(RS) 0.0445996
vector<int>(RSS)        1.97772
set<int>        17.7869
unordered_set<int>      36.134
list<int>       76.8214
deque<int>      15.5323

発生する乱数のレンジを小さくして、衝突が起こりやすくすれば、setの速度はもう少し上がる。しかし、極端な例としてレンジを [0, 10] にしても、vector + sort + unique の速度にはダブルスコアで負けてしまった。vector強し。

1秒あたりの挿入数をグラフにプロットしてみた（対数グラフ）
f:id:xoinu:20140814170831p:plain

まとめ

この結果、実はCPUのキャッシュがどれくらい有効に使われているかとかのほうが利いているのかもしれない（それもまた良い発見）。STLportなどの異なるSTLの実装、異なるハードウェアでも、また違った傾向が観察できるはず。

とりあえず覚えておくと良いのは

連続領域が安全に確保できるならvectorを使っておけば間違いない
reserveしたvector最強。なるべくreserveを呼んでおく
検索を必要とせず、単にソート済みのユニークな要素のリストがほしければsetではなくvector + sort + unique の組み合わせを使う（場合によっては1万倍以上の差が出る）
実は検索が必要な場合も、二分岐探索で挿入、検索するほうがパフォーマンスが出るかもしれない（これはあとで検証する）
list/setへの挿入のコストはvectorのpush_backとは次元が違う
dequeとvectorもこれだけ差が出る（似て非なる）

といったところ。雑感としては、unordered_set、dequeの結果は想像したoptimalな挙動とかけ離れていると感じる。本当にパフォーマンスが必要とされるところではSTLを信用せず、必要があれば自作するという選択肢もアリだと思った。

たまにこうやって手を動かして、速度を体感しておくのは大切ですね。

コード

使ったコードは以下の通り。開発環境はVisual Studio 2013 (msvc12)を使った。

#include <iostream>
#include <set>
#include <list>
#include <vector>
#include <deque>
#include <unordered_set>
#include <random>
#include <functional>
#include <algorithm>
#include <omp.h>

using namespace std;
int main(int argc, char* argv[])
{
  default_random_engine generator;
  uniform_int_distribution<int> distribution;
  const int LOOP_COUNT = 10;
  const size_t DATA_LENGTH = 50000;
  vector<int> vals(DATA_LENGTH);
  auto dice = bind(distribution, generator);

  for (auto& val : vals)
    val = dice();

  double dStart = omp_get_wtime();

  //-----------------------------------------------------------------
  for (int i = 0; i < LOOP_COUNT; ++i)
  {
    vector<int> cont;

    for (auto val : vals)
      cont.push_back(val);
  }

  cout << "vector<int>\t" << (omp_get_wtime() - dStart) << endl;

  //-----------------------------------------------------------------
  dStart = omp_get_wtime();

  for (int i = 0; i < LOOP_COUNT; ++i)
  {
    vector<int> cont;
    cont.reserve(DATA_LENGTH);

    for (auto val : vals)
      cont.push_back(val);
  }

  cout << "vector<int>(R)\t" << (omp_get_wtime() - dStart) << endl;

  //-----------------------------------------------------------------
  dStart = omp_get_wtime();

  for (int i = 0; i < LOOP_COUNT; ++i)
  {
    vector<int> cont;
    cont.reserve(DATA_LENGTH);

    for (auto val : vals)
      cont.push_back(val);

    sort(begin(cont), end(cont));
    cont.erase(unique(begin(cont), end(cont)), end(cont));
  }

  cout << "vector<int>(RS)\t" << (omp_get_wtime() - dStart) << endl;

  //-----------------------------------------------------------------
  dStart = omp_get_wtime();

  for (int i = 0; i < LOOP_COUNT; ++i)
  {
    vector<int> cont;
    cont.reserve(DATA_LENGTH);

    for (auto val : vals)
    {
      auto lb = lower_bound(begin(cont), end(cont), val);
      if (lb != end(cont) && *lb == val)
        continue;
      cont.insert(upper_bound(begin(cont), end(cont), val), val);
    }
  }

  cout << "vector<int>(RSS)\t" << (omp_get_wtime() - dStart) << endl;

  //-----------------------------------------------------------------
  dStart = omp_get_wtime();

  for (int i = 0; i < LOOP_COUNT; ++i)
  {
    set<int> cont;

    for (auto val : vals)
      cont.insert(val);
  }

  cout << "set<int>\t" << (omp_get_wtime() - dStart) << endl;

  //-----------------------------------------------------------------
  dStart = omp_get_wtime();

  for (int i = 0; i < LOOP_COUNT; ++i)
  {
    unordered_set<int> cont;

    for (auto val : vals)
      cont.insert(val);
  }

  cout << "unordered_set<int>\t" << (omp_get_wtime() - dStart) << endl;

  //-----------------------------------------------------------------
  dStart = omp_get_wtime();

  for (int i = 0; i < LOOP_COUNT; ++i)
  {
    list<int> cont;

    for (auto val : vals)
      cont.push_back(val);
  }

  cout << "list<int>\t" << (omp_get_wtime() - dStart) << endl;

  //-----------------------------------------------------------------
  dStart = omp_get_wtime();

  for (int i = 0; i < LOOP_COUNT; ++i)
  {
    deque<int> cont;

    for (auto val : vals)
      cont.push_back(val);
  }

  cout << "deque<int>\t" << (omp_get_wtime() - dStart) << endl;

  return 0;
}

空想犬猫記

※当日記では、犬も猫も空想も扱っておりません。（旧・エト記）

コンテナへの挿入の速度について

結果

まとめ

コード