そろそろstd::dequeについて語ろうか

STLの一翼を担うdeque(デックと読むらしい)ですが、その性能に比していまいち知名度が低いようです。
そこで、少しdequeについておさらいしましょう。

dequeの構造

まずは、dequeの期待される内部構造から。
といっても、非常に単純で、std::vector *>とほぼ等価と考えてかまいません。固定長の領域(ページと呼ぶ)へのポインタを配列にして管理している構造です。
これにより、vectorと違い、begin() -- end()の範囲がメモリ上で連続していることは期待できません。が、両端への挿入による再確保が発生しても全要素の移動にはならないため、償却定数時間のvector::push_backとは違い、deque::push_backは真に定数時間で処理可能(追記:ページへのポインタのベクタを伸長する償却定数時間(ただし数ページの伸長に1回)が別にかかります)です。

dequeの特徴

• STLシーケンシャルコンテナの要件を(optional含め)すべて満たす
• ランダムアクセスイテレータを提供する
• シーケンスの任意の位置へのoperator []の呼び出しは定数時間[O(1)]で行われる
• シーケンスの先頭と末尾への要素追加/削除は定数時間[O(1)]で行われる
• シーケンスの中間への要素追加/削除は先頭または末尾の近いほうへの距離に比例[O(N)]した時間で行われる

vectorと比べて

• 先頭へ定数時間で追加/削除できる(vectorは末尾のみ償却定数[O(1)]、先頭は線形[O(N)]
• 中間への挿入が平均的に半分の時間でできる
• 要素が連続領域として確保されない
• イテレータを単純なT *にできない
• 1ページにつきsizeof(void *)の領域が余分に必要
• boolに対する特殊化がない(vector特殊化はSTLコンテナでは無い)

listと比べて

• ランダムアクセス可能
• 中間への挿入が線形時間[O(N)]
• 空間効率がいい

dequeの使い道

さて、上記の特徴を踏まえ、dequeの使い道を考えてみると…

• ソート済みシーケンス(挿入・削除のパフォーマンスが全体的にvectorより良い)
• 要素数が全く見積れない入力バッファ(vectorでは再確保のペナルティが大きい)
• boolの可変長配列(そもそもvectorは使えない場面が多い)

といったところでしょうか。

dequeのパフォーマンス

というわけでお待ちかねの実測タイムです。STLの可変長シーケンスコンテナであるvector/deque/listを比較しました。コードは最後に掲載しておきます。
測定環境はWindows 7(64bit) amd64-w64-mingw32-g++-4.5.1-prerelease -Oです。

intのコンテナ:一千万要素

elements count is 10000000
sequencial copy
 vector(non-reserve):100
 vector(reserved):57
 deque:67
 list:812
sequencial read - for_each (100 times)
 vector:655
 deque:2070
 list:7042
sequencial read - accumulate (100 times)
 vector:977
 deque:1015
 list:7062
sorting
 vector:857
 deque:1347
 list:7505
inserting 100 objects to next to top of sequence
 vector:1325
 deque:0
 list:0
erasing 100 objects from next to top of sequence
 vector:1297
 deque:0
 list:0
inserting 100 objects keep ordering
 vector:665
 deque:347
 list(1/100 times):1947

時間の単位はミリ秒です。ソート済みリストへの中間挿入はあまりにも遅いので、ほかの1/100の回数で測定しています。
さて、これを見ると、vectorの再確保のコストが思ったより小さいですね。また、ソートそのものは時間がかかっていますが、ソート順を保ったままの挿入は逆に速いです。そしてlistがあまりにも遅いのが少し可哀そうですので、もうひとつ測ってみました。

コピーコンストラクタ・コピー代入に時間のかかるオブジェクト:十万要素

elements count is 100000
sequencial copy
 vector(non-reserve):62
 vector(reserved):25
 deque:25
 list:35
sequencial read - for_each (100 times)
 vector:10
 deque:25
 list:45
sequencial read - accumulate (100 times)
 vector:7577
 deque:7592
 list:7752
sorting
 vector:352
 deque:367
 list:17
inserting 100 objects to next to top of sequence
 vector:2637
 deque:0
 list:0
erasing 100 objects from next to top of sequence
 vector:2455
 deque:0
 list:0
inserting 100 objects keep ordering
 vector:1450
 deque:600
 list:432

Tのコピコンの中でピジーループ回して時間稼ぎさせています。結果を見ると、listの面目躍如というところでしょうか。
肝心のdequeはというと、前回大きく差がついていたsortも今回はなかなか競っています。そしてソート順を保った挿入はvectorの半分の時間のままですね。

結論

この二つの測定結果を踏まえると、

• オブジェクトが小さいときは相当要素数が多くても(数百万程度でも)、「とりあえずvectorでOK」が成立する
• ソート済みシーケンスを作るならdequeが安定。
• vectorはわざわざreserveしても所要時間は1/3程度にしかならない。
• 中間への挿入が多いときはvectorよりdeque
• コピコンのコストが大きい時もvectorよりdeque
• 思ったよりvectorさん優秀でdequeマンセーできなかった
• list涙目

ということで、「中間挿入が多いから」という理由でlistを使ってた人、dequeを検討してはどうでしょうか。

追記:十万要素程度じゃキャッシュに全部乗るんじゃないか的なことを指摘されたので、サイズの大きなオブジェクトで再計測しました。

elements count is 100000
sequencial copy
 vector(non-reserve):77
 vector(reserved):32
 deque:37
 list:37
sequencial read - for_each (100 times)
 vector:7
 deque:30
 list:325
sequencial read - accumulate (100 times)
 vector:1857
 deque:1910
 list:1915
sorting
 vector:90
 deque:105
 list:45
inserting 100 objects to next to top of sequence
 vector:1505
 deque:0
 list:0
erasing 100 objects from next to top of sequence
 vector:1240
 deque:0
 list:0
inserting 100 objects keep ordering
 vector:810
 deque:372
 list:915

100個のintをまとめたオブジェクトを1要素にしています。傾向は大して変わらないですね。

測定に使用したコードを貼っておきます。

#include <deque>
#include <vector>
#include <list>
#include <array>
#include <random>
#include <utility>
#include <string>
#include <functional>
#include <algorithm>
#include <chrono>
#include <iostream>
#include <iterator>
#include <sstream>

//#define USE_HEAVY_COPY_CTOR 1

static const size_t seed_length = 16;
#if defined(USE_HEAVY_COPY_CTOR) || defined(USE_LARGE_OBJECT)
static const size_t SIZE = 100000;
#else
static const size_t SIZE = 10000000;
#endif
static const size_t READING_REPEAT = 100;
static const size_t INSERTING_REPEAT = 100;

template <typename TimeT = std::chrono::milliseconds, typename F>
inline TimeT take_time(F &&f) {
	const auto begin = std::chrono::system_clock::now();
	f();
	const auto end = std::chrono::system_clock::now();
	return std::chrono::duration_cast<TimeT>(end - begin);
}

template <typename F>
inline void bench(const std::string &s, F &&f) {
	const auto t = take_time<>(std::forward<F>(f));
	std::cout << s << t.count() << std::endl;
}

template <typename charT = char, typename T>
inline std::basic_string<charT> to_s(T v) {
	std::basic_stringstream<charT> ss;
	ss << v;
	return ss.str();
}

struct heavy_copy_ctor {
	static const int copy_ctor_cost = 100;
	heavy_copy_ctor() { }
	heavy_copy_ctor(int v): val(v) { }
	heavy_copy_ctor(const heavy_copy_ctor &o): val(o.val) {
		for (volatile int n=0; n<copy_ctor_cost; ++n) ;
	}
	heavy_copy_ctor &operator =(const heavy_copy_ctor &o) {
		val = o.val;
		for (volatile int n=0; n<copy_ctor_cost; ++n) ;
	}
	heavy_copy_ctor &operator +=(const heavy_copy_ctor &o) {
		val += o.val;
		return *this;
	}
	heavy_copy_ctor operator +(const heavy_copy_ctor &o) const {
		return heavy_copy_ctor(*this) += o;
	}
	bool operator <(const heavy_copy_ctor &o) const { return val < o.val; }
	int val;
};

struct large_object {
	static const int object_size = 100;
	large_object() { }
	large_object(int v) { val.fill(v); }
	large_object &operator +=(const large_object &o) {
		transform(o.val.begin(), o.val.end(), val.begin(), val.begin(), std::plus<int>());
		return *this;
	}
	large_object operator +(const large_object &o) const {
		return large_object(*this) += o;
	}
	bool operator <(const large_object &o) const { return val[0] < o.val[0]; }
	std::array<int, object_size> val;
};


#if defined(USE_HEAVY_COPY_CTOR)
typedef heavy_copy_ctor DATA_TYPE;
#elif defined(USE_LARGE_OBJECT)
typedef large_object DATA_TYPE;
#else
typedef int DATA_TYPE;
#endif

std::array<DATA_TYPE, SIZE> src;
std::array<DATA_TYPE, INSERTING_REPEAT> add_src;
int main() {
	using namespace std;
	function<int ()> rnd;
	{
		random_device rnd_dev;
		array<uint_least32_t, seed_length> seed;
		generate(seed.begin(), seed.end(), ref(rnd_dev));
		seed_seq seq(seed.begin(), seed.end());
		rnd = bind(uniform_int_distribution<>(), mt19937(seq));
		generate(src.begin(), src.end(), ref(rnd));
		generate(add_src.begin(), add_src.end(), ref(rnd));
	}
	vector<DATA_TYPE> vec;
	deque<DATA_TYPE> deq;
	list<DATA_TYPE> lis;
	cout << "elements count is " << SIZE << endl;

	cout << "sequencial copy" << endl;
	bench(" vector(non-reserve):", [&] {
		copy(src.begin(), src.end(), back_inserter(vec));
	});
	(decltype(vec)()).swap(vec); vec.reserve(SIZE);
	bench(" vector(reserved):", [&] {
		copy(src.begin(), src.end(), back_inserter(vec));
	});
	bench(" deque:", [&] {
		copy(src.begin(), src.end(), back_inserter(deq));
	});
	bench(" list:", [&] {
		copy(src.begin(), src.end(), back_inserter(lis));
	});

	cout << "sequencial read - for_each (" << READING_REPEAT << " times)" << endl;
	bench(" vector:", [&] {
		for (size_t n=0; n<READING_REPEAT; ++n) for_each(vec.begin(), vec.end(), [](const DATA_TYPE &) {;});
	});
	bench(" deque:", [&] {
		for (size_t n=0; n<READING_REPEAT; ++n) for_each(deq.begin(), deq.end(), [](const DATA_TYPE &) {;});
	});
	bench(" list:", [&] {
		for (size_t n=0; n<READING_REPEAT; ++n) for_each(lis.begin(), lis.end(), [](const DATA_TYPE &) {;});
	});

	cout << "sequencial read - accumulate (" << READING_REPEAT << " times)" << endl;
	bench(" vector:", [&] {
		for (size_t n=0; n<READING_REPEAT; ++n) accumulate(vec.begin(), vec.end(), DATA_TYPE(0));
	});
	bench(" deque:", [&] {
		for (size_t n=0; n<READING_REPEAT; ++n) accumulate(deq.begin(), deq.end(), DATA_TYPE(0));
	});
	bench(" list:", [&] {
		for (size_t n=0; n<READING_REPEAT; ++n) accumulate(lis.begin(), lis.end(), DATA_TYPE(0));
	});

	cout << "sorting" << endl;
	bench(" vector:", [&] {
		sort(vec.begin(), vec.end());
	});
	bench(" deque:", [&] {
		sort(deq.begin(), deq.end());
	});
	bench(" list:", [&] {
		lis.sort();
	});

	cout << "inserting " << INSERTING_REPEAT << " objects to next to top of sequence" << endl;
	bench(" vector:", [&] {
		for (size_t n=0; n<INSERTING_REPEAT; ++n) vec.insert(next(vec.begin()), add_src[n]);
	});
	bench(" deque:", [&] {
		for (size_t n=0; n<INSERTING_REPEAT; ++n) deq.insert(next(deq.begin()), add_src[n]);
	});
	bench(" list:", [&] {
		for (size_t n=0; n<INSERTING_REPEAT; ++n) lis.insert(next(lis.begin()), add_src[n]);
	});

	cout << "erasing " << INSERTING_REPEAT << " objects from next to top of sequence" << endl;
	bench(" vector:", [&] {
		for (size_t n=0; n<INSERTING_REPEAT; ++n) vec.erase(next(vec.begin()));
	});
	bench(" deque:", [&] {
		for (size_t n=0; n<INSERTING_REPEAT; ++n) deq.erase(next(deq.begin()));
	});
	bench(" list:", [&] {
		for (size_t n=0; n<INSERTING_REPEAT; ++n) lis.erase(next(lis.begin()));
	});

	cout << "inserting " << INSERTING_REPEAT << " objects keep ordering" << endl;
	bench(" vector:", [&] {
		for (size_t n=0; n<INSERTING_REPEAT; ++n) {
			vec.insert(lower_bound(vec.begin(), vec.end(), add_src[n]), add_src[n]);
		}
	});
	bench(" deque:", [&] {
		for (size_t n=0; n<INSERTING_REPEAT; ++n) {
			deq.insert(lower_bound(deq.begin(), deq.end(), add_src[n]), add_src[n]);
		}
	});
#if defined(USE_HEAVY_COPY_CTOR) || defined(USE_LARGE_OBJECT)
	bench(" list:", [&] {
		for (size_t n=0; n<INSERTING_REPEAT; ++n) {
			lis.insert(lower_bound(lis.begin(), lis.end(), add_src[n]), add_src[n]);
		}
	});
#else
	bench(" list(1/" + to_s(INSERTING_REPEAT) + " times):", [&] {
		for (size_t n=0; n</*INSERTING_REPEAT*/1; ++n) {
			lis.insert(lower_bound(lis.begin(), lis.end(), add_src[n]), add_src[n]);
		}
	});
#endif
}