前提
std::set に、多数のソート済みアイテムをできるだけ高速に追加したい。
具体的には、std::set<std::string> で要素数は 100000 くらい、各要素の文字数は多くて 128 程度、というような状況を想定している。
std::set へのコンテナのマージの一番典型的な手順は std::set::insert() の iterator を取るバージョンだと思われるが、こいつは追加される要素群がソートされていないことを前提としているので、必要以上に要素の比較が入ってしまう。
C++17 で std::set_union というものが追加されている。こいつはソート済みの 2 つのコンテナをマージしつつ第三のコンテナへ追加するという挙動を取る。元となる 2 つのコンテナは変更されず、出力先のコンテナへは各要素のコピーが追加されることになる。
これで済む状況も多いと思われるが、今回は既にあるコンテナへ他のコンテナの要素を追加したいという要件であり、適合しなかった。std::set への要素の追加はそれ自体が重い処理であるため、結果を受け取る一時コンテナを都度生成というのは避けたい。
同じく C++17 で std::set::merge() が追加されている。こいつはマージ元コンテナの各要素をマージ先コンテナへ move するという挙動を取る。ここでいう各要素というのは value_type ではなく、std::set の内部的なノードのことで、ノードの付け替えだけで済ますことによりノード生成処理を完全に省きつつマージできるという代物である。これにより std::set::insert() よりも圧倒的に高速に動作する。
…なのだが、当然マージ元となるコンテナは破壊的に変更されることになる。今回のケースではこれは避けたかった。加えて、std::set::merge() はマージ元とマージ先は同種のコンテナでなければならず、ソート済みの std::vector をマージといったことはできない。できればソート済みであればコンテナの種類を問わず受け付けるようにしたい。
実装
結論から書くと、こうなった。
// dst: std::set or std::map
// begin & end: iterator of sorted items
template<class Tree, class Iterator>
inline void InsertSortedSequence(Tree& dst, Iterator begin, Iterator end)
{
auto pos = dst.begin();
for (auto it = begin; it != end; ++it) {
pos = dst.emplace_hint(pos, *it);
++pos;
}
}
std::set::emplace_hint() は追加位置のヒントとなる iterator を与えられる。この iterator が適切な位置であればそのままそこに追加、そうでなかった場合は lower_bound() で探す、というような処理を行う。
ちなみに C++11 で std::set::insert() にもヒントを与えられるバージョンが追加されており、こちらでも速度にほぼ差はない。MSVC の実装ではこちらも内部的に emplace_hint() を呼んでいるようだ。
もう一点、std::set::merge() の性能を計測していて気づいたのだが、明らかに必要以上に要素の比較が走っている。どうもソートされていないことが前提の std::set::insert() と同様の手順で追加位置を探すようになっているようだ。
Visual Studio の実装だけでなく、gcc の実装でもそうなっているので、仕様上だか実装上だかの都合があるのかもしれない。ともあれ、それなら std::set::merge() の高速バージョンもやってみよう。
// dst: std::set or std::map
// src: source of elements. *will be emptied*.
template<class Tree>
inline void MergeOptimized(Tree& dst, Tree& src)
{
auto pos = dst.begin();
while (!src.empty()) {
auto node = src.extract(src.begin());
pos = dst.insert(pos, std::move(node));
++pos;
}
}
std::set::extract() は C++17 で追加されたもので、set の内部実装のノードを引っこ抜く。このノードは別の set へ insert() で移すことができ、これによりアロケーションなしでノードの移し替えができるようになっている。
なお、この実装だとマージ元コンテナは無条件で空になるが、std::set::merge() は重複によりマージされなかった要素は元コンテナに残ったままになるという違いがある。
結果
coliru で実行や編集ができるので、全ソースに興味がある方はこちらを参照。
要素数 100000 の 2 つの std::set をマージするという処理内容。処理時間、比較回数、malloc() 回数を計測し、冒頭で触れた STL のアルゴリズムと独自に実装したものを比較したところ、こうなった。
// MSVC (私の手元の環境)
std::set::insert(): 42.70ms, 2212207 compare, 200000 alloc
std::set::merge(): 18.91ms, 2112207 compare, 0 alloc
std::set_union(): 73.77ms, 199999 compare, 400000 alloc
InsertSortedSequence(): 36.93ms, 763326 compare, 200000 alloc
MergeOptimized(): 15.54ms, 763326 compare, 0 alloc
// gcc (Coliru)
std::set::insert(): 76.15ms, 2345048 compare, 200000 alloc
std::set::merge(): 39.99ms, 2245048 compare, 0 alloc
std::set_union(): 130.68ms, 399998 compare, 400000 alloc
InsertSortedSequence(): 62.37ms, 850417 compare, 200000 alloc
MergeOptimized(): 27.06ms, 850417 compare, 0 alloc
std::set::insert() より速いものを実装するのが目的だったので、とりあえず目的は達成できた。このサンプルではそこまで劇的な変化は見られないが、比較回数が大きく減っているため、比較処理が重い複雑なオブジェクトの場合はより顕著に速くなる。
std::set_union() は比較回数こそ圧倒的に少ないものの、ノード生成の多さが足枷となって意外と遅かった。逆に、ノード生成が不要な merge 系は予想以上に速かった。merge で済む状況なら積極的に使っていきたいところ。
C++17 にしろ C++20 にしろ、std::set::extract() のようなローレベルな機能がいろんなところに追加されていて、ちゃんと現場のニーズをわかってる人が仕様策定やってくれてるんだな感あってとても良いと思う。
余談
MSVC の実装では std::set や std::map はコンストラクタ内でノードを一つ生成するようになっており、例えば std::set<int> hoge; の一行だけで malloc() が呼ばれる。このため、1 秒間に数万回生成されるような一時オブジェクトに std::set が含まれていると、malloc() / free() だけでも馬鹿にできない処理量になってくる。注意が必要。(USD にそういう処理があって以前問題になった)
なお、gcc の実装では空の std::set や std::map は malloc() も走らない。