VC++のunordered_set/unordered_mapが遅い件
正確に言うと、insertが同種のset/mapに比べて圧倒的に遅い。
最近、メモリの節約のために辞書的なオブジェクトを作成して、同値のオブジェクト(例えば文字列)を再利用するようなコードを書いたところ、unordered_set/unordered_mapで思うような性能が得られなかった。
コンテナ以外のアロケーションの影響を受けないように、あらかじめ文字列を用意して、それを辞書に登録する以下のサンプルコードを書いて、Visual Studio 2015でプロファイルをとってみた。
#include "stdafx.h" using namespace std; namespace { struct char_cmp : public binary_function<const char*, const char*, bool> { result_type operator()(first_argument_type l, second_argument_type r) const { if (!l) { if (!r) return false; return true; } else { if (!r) return true; return strcmp(l, r) < 0; } } }; struct char_hash : public unary_function<const char*, size_t> { size_t operator()(argument_type key) const { return hash_value(key); } }; struct char_equal_to { typedef const char* first_argument_type; typedef const char* second_argument_type; typedef bool result_type; bool operator()(first_argument_type pL, second_argument_type pR) const { return strcmp(pL, pR) == 0; } }; template <typename Set> __declspec(noinline) void TestSet(const vector<string>& samples) { Set set; for (auto& s : samples) set.insert(s.c_str()); } } int main() { vector<string> samples; samples.reserve(100000); default_random_engine generator; uniform_int_distribution<int> distribution(33, 126); for (int i = 0; i < 100000; ++i) { samples.emplace_back(); auto& str = samples.back(); str.reserve(300); for (int j = 0; j < 300; ++j) str += distribution(generator); } TestSet<unordered_set<const char*, char_hash, char_equal_to>>(samples); TestSet<set<const char*, char_cmp>>(samples); return 0; }
で、結果がこちら
サンプルの要素数が増えれば増えるほど差は広がるばかり。確認のためTDM-GCCで同等のコードを書いてみたところ、むしろunordered_set/unordered_mapの方がinsertは高速だったので、これはVisual StudioのSTLの実装特有の問題っぽい。
Visual Studio上でunordered_set/unordered_mapを旧来のset/mapの代わりに使う際には、必ずベンチマークをとって、挿入性能劣化に見合う検索性能の向上の恩恵に与れるかどうかを確認したほうが良さそうだ。
やれやれ……
追記:
xoinu.hatenablog.com
2年前にint型のコンテナで挿入のパフォーマンスのチェックをやってた。そのときの結果と少し矛盾している。これを見るにVC++のxhashヘッダにあったstd::hash_value()関数がよろしくないのかもという気がする。
再帰呼び出しをループに置き換える
半年に一度くらい、古いコードで使っている再帰呼び出しが原因でスタックオーバーフローになるという不具合が発見され、その都度ループで書き直す修正を入れている。再帰呼び出しをループに展開する方法は、「幅優先探索」や「深さ優先探索」というキーワードで探すと見つけることができる。そのエッセンスだけメモしておく。
再帰呼び出しのうち、トップダウンで処理していくものについては、キューを使うと比較的簡単に展開できる。たとえば
struct Node { Node* left; Node* right; : };
という構造体があって、
void ProcessNode(Node* node) { : : (do something) : if (node->left) ProcessNode(node->left); if (node->right) ProcessNode(node->right); }
のような再帰呼び出しがあるとき、ProcessNode関数は以下のように展開できる。
void ProcessNode(Node* node) { list<Node*> nodeList; nodeList.push_back(node); while (!nodeList.empty()) { node = nodeList.front(); nodeList.pop_front(); : : (do something) : if (node->left) nodeList.push_back(node->left); if (node->right) nodeList.push_back(node->right); } }
ボトムアップに処理していくものも基本的な考え方は一緒であるが、
- キューの代わりにスタックを使う
- スタックを積むときと実際に処理をするときの二度、ノードを訪れることになるので、今どっちのタイミングなのか、知るためのフラグが必要
になる点が少し面倒になる。模擬コードは以下のようになるはず(自分で試してね)。
namespace { struct Data { Data(Node* n) : node(n), isTraversed(false) {} Node* node; bool isTraversed; }; } void ProcessNode(Node* node) { vector<Data> nodeList; nodeList.push_back(node); while (!nodeList.empty()) { auto& data = nodeList.back(); node = data.node; if (!data.isTraversed) { data.isTraversed = true; if (node->left) nodeList.push_back(node->left); if (node->right) nodeList.push_back(node->right); } else { nodeList.pop_back(); : : (do something) : } } }
再帰呼び出しで書くと、単にコード中の "do something" の位置を if 文の前に持ってくるか後ろに置くかだけの差であり、記述としては簡便なうえに、マシンスタックを利用したほうがヒープよりも高速に動作する。つまりスタックオーバーフローを起こさない限りは再帰のほうが一概に優れているので、もろもろ考慮してどちらの実装方法を選ぶか決めましょう。
Cron の設定メモ
Firefox設定メモ ~MS PゴシックをMeiryo UIに置換~
Google Chromeが頻繁にクラッシュするのと、メモリ使用量が必要以上に多いので、Firefoxに戻ってきた。久々に帰ってきてみたら、UIがGoogle Chromeっぽくなっていて全然違和感がない。HTML5になってから動画の再生にもプラグインが必要なくなったので、プラグインは全てアンイストールないしdeactivateした。
やるべきことは、userContent.cssをいじって「MS Pゴシック」を「Meiryo UI」フォントに置き換えたくらい。Webブラウザの世界の技術も標準化が進み枯れてきたのか、オジサンの想像力が枯れてきたのか。
具体的には以下の2ステップ。
%APPDATA%\Mozilla\Firefox\Profiles\XXXXXXXX.default
以下に chrome というフォルダをつくって、userContent.cssというファイルを作成する。中身はかつてGoogle Chromeでサポートされていたユーザスタイルシートと同じで、たんに
@charset "UTF-8"; @font-face { font-family: "MS Pゴシック"; src: local("Meiryo UI"); } @font-face { font-family: "MS PGothic"; src: local("Meiryo UI"); } @font-face { font-family: "MS P明朝"; src: local("Meiryo UI"); } @font-face { font-family: "MS PMincho"; src: local("Meiryo UI"); }
などとしておいた。私は英語版Windowsなのでフォント名は「Meiryo UI」だが、日本語版の場合は「メイリオ」などとする必要があるかもしれない。Google Chromeはご丁寧にユーザスタイルシートファイルの変更のイベントを拾って、動的に既に開いているページに変更を適用してくれたけれども、Firefoxの場合は再起動が必要。設定はたいてい一度限りだし、この方がよい実装だと思う。今のところなんの不満もない。
コンテナ内の検索の速度について(2) ~setの使いどころ~
C++エクササイズその3。前回、前々回の実験で、setの良さが発揮できなかったものの、何となく経験に反する結果だったので、もう一つだけ実験してみた。
具体的には、要素の中身をintからstringに変え、要素数2000から50000のコンテナに対してそれぞれ100万回検索をかけて時間を測定した。
結果
横軸がコンテナの要素数、縦軸が100万回findするのに要した時間(単位:秒)
ソート済みvectorはそれでも大健闘。挿入の速さやメモリ効率を考えると使いどころは多いと思う。string程度の大きさのオブジェクトで、ある程度比較関数も複雑になってくると、メモリ上の構造のシンプルさよりもアルゴリズム的な優位性が利いてきて、setに分がでてくるということなんだろうか。
まとめ
intのような単純なオブジェクトでなければ、やはりsetの方が検索は速いが、ソート済みvectorにも挿入の速さやメモリ効率などのアドバンテージがあるので、状況に応じて両方使いこなすとよい。単に検索目的であればunordered_set一択。
コード
#include <iostream> #include <set> #include <list> #include <vector> #include <deque> #include <unordered_set> #include <random> #include <functional> #include <algorithm> #include <omp.h> #include <string> using namespace std; static void BenchmarkFindString() { default_random_engine generator; uniform_int_distribution<int> distribution; auto dice = bind(distribution, generator); uniform_int_distribution<int> distChar(65, 90); auto diceChar = bind(distChar, generator); uniform_int_distribution<size_t> distStrLen(16, 128); auto diceStrLen = bind(distStrLen, generator); vector<size_t> DATA_LENGTH_ARRAY(25); size_t next = 2000; for (auto& len : DATA_LENGTH_ARRAY) { len = next; next += 2000; } vector<string> QUERY_DATA(1000000); for (auto& dat : QUERY_DATA) { auto len = diceStrLen(); dat.reserve(len + 1); for (size_t i = 0; i < len; ++i) dat += (char)diceChar(); } cout << "size,vector,set,unordered_set" << endl; for (auto DATA_LENGTH : DATA_LENGTH_ARRAY) { vector<string> vals(DATA_LENGTH); for (auto& val : vals) { auto len = diceStrLen(); val.reserve(len + 1); for (size_t i = 0; i < len; ++i) val += (char)diceChar(); } cout << DATA_LENGTH; { vector<string> cont(begin(vals), end(vals)); sort(begin(cont), end(cont)); cont.erase(unique(begin(cont), end(cont)), end(cont)); double dStart = omp_get_wtime(); for (auto& val : QUERY_DATA) lower_bound(begin(cont), end(cont), val); cout << ',' << (omp_get_wtime() - dStart); } { set<string> cont(begin(vals), end(vals)); double dStart = omp_get_wtime(); for (auto& val : QUERY_DATA) cont.find(val); cout << ',' << (omp_get_wtime() - dStart); } { unordered_set<string> cont(begin(vals), end(vals)); double dStart = omp_get_wtime(); for (auto& val : QUERY_DATA) cont.find(val); cout << ',' << (omp_get_wtime() - dStart); } cout << endl; } } int main(int argc, char* argv[]) { BenchmarkFindString(); return 0; }
コンテナ内の検索の速度について
追記:この記事には続きがあります。
C++エクササイズその2。前回の実験で、要素の追加についてはvectorの性能が際立っていたので、今度は要素の検索について実験してみた。
vectorに対して要素の検索をする場合、誰もが思いつくのは
というわけで、今回はソート済みvectorに対するstd::lower_bound()、set
- コンテナに対して100万回検索をかける
- コンテナサイズは20000から500000まで、20000刻み。各コンテナは同じ乱数を使って初期化(中身は一緒)
結果
さすがにunordered_setは速い。しかしソート済みvectorに対する二分岐探索は、setよりも速い。あれ、set、いいとこ無いじゃん。vectorに比べて挿入は400倍遅くて、検索も2倍から3倍遅いとは。
まとめ
- 検索に関してはunordered_set最強。これは技術書どおりでホッとした
- ソート済みの要素に対して検索をかけられるならば、vectorのほうがsetよりも速い
- 前回の結果と組み合わせると、ソート済みvectorは挿入も検索もsetを凌ぐパフォーマンスを示している。これはハードウェア的な問題なのか、単にsetの実装がマズいのか...。
コード
実験に使ったコードは以下の通り。開発環境はVisual Studio 2013 (msvc12)で、コンパイラオプションも特にいじらず素のリリースモジュールで実験しました。
#include <iostream> #include <set> #include <vector> #include <unordered_set> #include <random> #include <functional> #include <algorithm> #include <omp.h> using namespace std; static void BenchmarkFind() { default_random_engine generator; uniform_int_distribution<int> distribution; auto dice = bind(distribution, generator); vector<size_t> DATA_LENGTH_ARRAY(25); size_t next = 20000; for (auto& len : DATA_LENGTH_ARRAY) { len = next; next += 20000; } vector<int> QUERY_DATA(1000000); for (auto& dat : QUERY_DATA) dat = dice(); cout << "size,vector,set,unordered_set" << endl; for (auto DATA_LENGTH : DATA_LENGTH_ARRAY) { vector<int> vals(DATA_LENGTH); for (auto& val : vals) val = dice(); cout << DATA_LENGTH; { vector<int> cont(begin(vals), end(vals)); sort(begin(cont), end(cont)); cont.erase(unique(begin(cont), end(cont)), end(cont)); double dStart = omp_get_wtime(); for (auto val : QUERY_DATA) lower_bound(begin(cont), end(cont), val); cout << ',' << (omp_get_wtime() - dStart); } { set<int> cont(begin(vals), end(vals)); double dStart = omp_get_wtime(); for (auto val : QUERY_DATA) cont.find(val); cout << ',' << (omp_get_wtime() - dStart); } { unordered_set<int> cont(begin(vals), end(vals)); double dStart = omp_get_wtime(); for (auto val : QUERY_DATA) cont.find(val); cout << ',' << (omp_get_wtime() - dStart); } cout << endl; } } int main(int argc, char* argv[]) { BenchmarkFind(); return 0; }