boost::container::flat_(multi)set/map
flat_(multi)set/mapについてはかなり昔のアーティクル『なぜsetを使っちゃいけないの？』で少しだけ触れました。そこではこう述べています。
- NオーダとlogNオーダとの差が顕著になるくらいに要素数が大きいと思われるとき
- 挿入回数が検索回数と同程度もしくはそれ以上である、すなわち挿入に要する時間を無視できないとき
- 要素の挿入順がランダム（昇順でない）なとき
- 挿入／検索が交互に行われ、挿入フェーズと検索フェーズとに分離できないとき
これら4つのケースがすべて当てはまるなら、setを使うべきだろう。setはまさにそれが目的で設計されたものなのだから。しかしながら、4つのケースのどれかがあてはまらないのであれば、setのような複雑な実装によるデータ構造は無駄であり、単純なソート済みvectorの方がずっと高いパフォーマンスを手にできるだろう。
高いパフォーマンスを手にできるであろう"単純なソート済みvector"で実装されているのが flat_(multi)set/mapです。要素が一列に平たく並んでいるので"flat"なんですな。
メモリの使われ方（空間）と挿入／検索スピード（時間）について、std::setとflat_setとを比較してみます。
まずはメモリの使われ方。特製allocatorを仕込み、数個の要素を挿入してその様子を観察します。
void memory_usage() {
cout << "\n==== memory usage\n";
const int N = 10;
{
cout << "\n--- " << N << " items insertion into 'set'\n";
std::set<int,std::less<int>,epi::mallocator<int>> fs;
for ( int i = 0; i < N; ++i ) {
fs.insert(N-i-1);
}
for ( const int& item : fs ) {
cout << setw(4) << item << " @ " << static_cast<const void*>(&item) << endl;
}
cout << endl;
}
cout << endl;
{
cout << "\n--- " << N << " items insertion into 'flat_set'\n";
boost::container::flat_set<int,std::less<int>,epi::mallocator<int>> fs;
for ( int i = 0; i < N; ++i ) {
fs.insert(N-i-1);
}
for ( const int& item : fs ) {
cout << setw(4) << item << " @ " << static_cast<const void*>(&item) << endl;
}
cout << endl;
}
cout << endl;
}
flat_setはメモリの取得と解放を繰り返しながら次第に領域を拡げています。また各要素のアドレスも先頭から末尾まで連続して並んでいます。std::vectorの挙動そのものです。
検索スピードはどうでしょう。要素数10万のstd::setとflat_setに対する10万回の検索に要する時間を計測しました。
// 関数fの呼び出しに要する時間を測る
template<typename Function, typename ...Args>
void measure(Function f, Args ...args) {
using namespace std::chrono;
auto start = high_resolution_clock::now();
f(args...);
auto stop = high_resolution_clock::now();
std::cout << duration_cast<milliseconds>(stop - start).count() << "[ms]\n";
}
void search_performance() {
cout << "\n==== search\n";
const int N = 100000;
std::vector<int> v(N);
iota(begin(v), end(v), 0);
std::set<int> s;
boost::container::flat_set<int> fs;
for ( int item : v) {
s.insert(item);
fs.insert(item);
}
{
cout << "--- " << N << " items searching from 'set'\n";
measure([&]() { for ( int item : v) s.find(item);});
}
{
cout << "--- " << N << " items searching from 'flat_set'\n";
measure([&]() { for ( int item : v) s.find(item);});
}
}
flat_setはstd::setと同等の性能を叩き出してます。
最後に挿入。std::setとflat_setそれぞれに1～9999を昇順／降順に挿入してみました。
void insertion_performance() {
cout << "\n==== insert\n";
const int N = 10000;
std::vector<int> v(N);
iota(begin(v), end(v), 0);
{
cout << "--- " << N << " items insertion into 'set' (ascend)\n";
std::set<int> s;
measure([&]() { for ( int item : v) s.insert(item);});
}
{
cout << "--- " << N << " items insertion into 'flat_set' (ascend)\n";
boost::container::flat_set<int> fs;
measure([&]() { for ( int item : v) fs.insert(item);});
}
reverse(begin(v), end(v));
{
cout << "--- " << N << " items insertion into 'set' (descend)\n";
std::set<int> s;
measure([&]() { for ( int item : v) s.insert(item);});
}
{
cout << "--- " << N << " items insertion into 'flat_set' (descend)\n";
boost::container::flat_set<int> fs;
measure([&]() { for ( int item : v) fs.insert(item);});
}
}
std::setでは昇順／降順で所要時間に大きな差はありませんが、flat_setは降順での挿入がかなり苦手のようです。要素をリニアにかつ昇順に格納せにゃならんので、挿入のたんびにコピーが頻発しますからね。
おマケにもう一つ、要素の重複を許すflat_multisetに同値要素を複数挿入したときのふるまいです。int値の一の位を無視して29,28,27,...2,1,0を挿入します。一の位を無視するので29～20,19～10,9～0はそれぞれ同値要素となります。
#include <iostream>
#include <iomanip>
#include <boost/container/flat_set.hpp>
using namespace std;
using namespace boost::container;
template<typename T>
struct less1 {
bool operator()(T x, T y) const {
return x/10 < y / 10;
}
};
int main() {
const int N = 30;
{
flat_multiset<int,less1<int>> fs;
for ( int i = 0; i < N; ++i ) {
fs.insert(N-i-1);
}
for ( int item : fs ) {
cout << item << ' ';
}
cout << endl;
}
cout << endl;
}
ごらんのとおり、同値要素を複数挿入すると挿入した順序で並んでくれてます。これはありがたい。少しばかりコードを読んでみたところ、挿入位置をupper_boundで決定していました、なるほどね。
……やっぱりスゴいわBoost。標準ライブラリでは物足りない部分をスマートに実装してくれてます。Boostなしではコードの書けないC++'erが少なくないのもうなずけます。
