この間、Boost 1.65がリリースされた。リリースノートをざっと見た所、新規ライブラリがいくつか入っている。そのPolyCollectionなるものが気になったのでざっと見てみることにした。これはその覚え書きである。
PolyCollectionは、多相型向けのコンテナだ。基底クラスを指定してその派生クラスを格納したり、anyによってDuckTypingしたり、std::functionに関数ポインタや関数オブジェクトを放り込んだりする際にいちいち生じるヒープアロケーション、それによるキャッシュヒット率の低下と、仮想関数呼び出し時の分岐予測の失敗を解決する。
base_collection
既知の問題
中を見る前に、そもそも何が問題で、なぜこれが作られたかに触れておこう。
例えばあなたがアクションゲームを作っていたとする。オブジェクト指向的設計によって、敵キャラクターは全てclass enemyから派生しているとする。
class enemy{}; class waddle_dii: public enemy{}; class waddle_duu: public enemy{}; // 名前は某ピンクの悪魔とは無関係だ。いや、綴り違うし。
敵をどこかに格納しておく必要はよく生じるだろう。そういう時は、最も単純には以下のようにするだろう。
std::vector<std::unique_ptr<enemy>> enemies;
そして、例えばプレイヤーが何らかの技を繰り出して全ての敵を無条件に倒す場合、
for(auto&& enem: enemis) { enem->beaten(); }
のようにして倒した時に必要な処理を施すだろう。ゲーム作ったことないけど。
さて、このenemiesはポインタを持っている配列だ。ここに直接オブジェクトが入っている訳ではなく、オブジェクトはどこかよくわからないところにとりあえず確保されて、そこへのポインタが格納されている。特にアクションゲームのように速度が重要な時、これは主に2つの問題を生じる。第一に、オブジェクトがメモリ上で連続していない可能性があるので、ある要素があるメモリ位置から近接した領域をごっそりキャッシュに持ってきても、次の要素がそこに入っている確率が（配列に比べて）低くなる。当然、キャッシュヒット率は低下し、メモリアクセスが増え、CPUは遊ぶ。CPUが超高速になってメモリが追いついていない現代、これは速度の点から好ましくない。第二に、この配列には派生クラスがランダムに挿入されているので、もしそこに何らのパターンがなければ、上記のようなループ中の処理にパターンがなくなり、分岐予測が失敗しやすくなる。よってパイプラインハザードが頻繁に起き、折角の計算結果を捨てることが多くなる。
また、公式の説明文には書かれていないので私の憶測だが、オブジェクトが一つ一つ確保されていくのでヒープアロケーションの回数が嵩みそうだ。これも、std::vector<waddle_dii>であったなら、一気にがさっと確保したのちcapacityを超えない間はリアロケーションが必要なくなる。
解決策
ではどういう解決策が考えられるだろうか。上記の問題は全て、決まったオブジェクトの配列ではなく基底クラスへのポインタの配列になっていることで生じる問題だ。なので、決まったオブジェクトの配列を使うことで全て解決する。
例えば、敵キャラクターがwaddle_diiとwaddle_duuしか存在しないと最初から最後までわかっているなら、脳筋で以下のようにできるだろう。
std::vector<waddle_dii> waddle_diis;
std::vector<waddle_duu> waddle_duus;
std::vector<enemy*> enemies; // 上記vectorの要素を指す
これでwaddle_diiとwaddle_duuはメモリ上で連続した位置に配置されるのでキャッシュヒット率は向上し、std::vectorを適切にreserveすることでヒープアロケーションの回数も減るだろう。素晴らしい。だが現実的には敵キャラクターは数百はいるわけで、こんな脳筋解決策は常にできるわけではない。それに、enemy*越しに見にいくなら、分岐予測は同じ理由でやはり失敗するだろう。
ではどうするか。分岐予測に関しては、waddle_diiをループしている時はwaddle_diiだけが来るようにすれば改善が見込める。ではループは以下のように書けば良いのだ。
for(auto&& dii: waddle_diis) { dii->beaten(); } for(auto&& duu: waddle_duus) { duu->beaten(); }
そして敵キャラクターが100種類いたら100個のループを書くのか？ 敵を格納する必要のある全ての箇所で？ それはちょっとどうかしているとしか言いようがない。BOOST_PP_ENUMを……いや、何でもない。
我々は連想配列を知っている。上記は、例えば以下のようにして連想配列に置き換えることができる。
std::unordered_map<std::type_info const*, std::any> enemies; enemies[&typeid(waddle_dii)] = std::vector<waddle_dii>{}; enemies[&typeid(waddle_duu)] = std::vector<waddle_duu>{};
こうすれば、新たな知らない型が来た時にはこのmapに新たなkey-valueペアを付け加えれば良い。keyが型情報、valueが新たな派生型専用のベクタだ。
派生型は派生型同士でまとまって配置されるので、キャッシュヒット率は高まる。
あとはこれを上手く回せるようなイテレータを使えば、同じ派生型をまとめてループするようにでき、それを全派生型に対して行うことも可能になる。
この発想をより洗練させて効率よくしたのがboost::base_collectionだ。
別の解決策
一応、他にも解決策はある。例えば、敵キャラクターの数が決まっているなら、variantが使える。これは型安全な共用体だ。
共用体なので、そのサイズは入りうる型の中で最も大きなオブジェクトのサイズになる。静的にサイズが決まるので、そのままvectorに放り込むことができる。
std::vector<std::variant<waddle_dii, waddle_duu>> enemies;
さらに、visitorによって簡単にアクセスすることができ、また型による処理の分岐を外から注入できる。
struct visitor { void operator()(waddle_dii& w) const noexcept {/*ある処理*/;} void operator()(waddle_duu& w) const noexcept {/*別の処理*/;} }; for(auto&& enem: enemies) std::visit(visitor{}, enem);
ただし欠点もある。まず、分岐予測はまたも失敗するだろう。enemiesに型がどのように配置されているか、何も前提が置けないからだ。
さらに、variantの欠点だが、敵オブジェクトの中に一つだけ非常にサイズの大きい物があって、かつその敵がほぼ現れないときだ。
実際にはenemiesの中に一つもそのオブジェクトが入らなくても、variantは最も大きいオブジェクトと同じサイズを確保する。
これは場合によってはメモリをとてつもなく無駄遣いすることになるだろう。
それと、これは本質的には重要でないが、敵オブジェクトのサイズが似たりよったりだったとしても、100種類の敵キャラクターがいれば、
variantの宣言は非常に面倒になる。
typedef std::variant<Enem1, Enem2, ... Enem100> enemy_type;
これは大変だ。
base_collectionの中身
std::functionやanyとtype_erasureの話もしようと思っていたが既に1時間くらい経ってしまっているしこのままではいつまで経っても終わらないので本題に入ろう。
今boostの公式Webサイトから1.65.0をダウンロードして解凍し、ビルドしたところだ。
本気で中身をじっくり見る気はないので大雑把に見ていく。
まず、boost/poly_collection/base_collection.hppを見てみる。
これだけ似たようなクラスを作るのだから、基本的なところはジェネリックに書いていると思われるので、ここには単なるtemplate特殊化か派生クラスだけがあると予想できる。実際そうだった。
template<typename Base,typename Allocator> class base_collection: public detail::poly_collection_impl::poly_collection< detail::base_model<Base>,Allocator> { ...
では基底クラスの方を見に行こう。detail::poly_collection_implまでが名前空間なので、boost/poly_collection/detail/poly_collection.hppに本体が入っている。
こちらは流石に長い。1176行ある。それでも決して読みにくいコードではないので、流し見でなんとなく雰囲気はつかめる。とりあえず1134行目で宣言されているsegment_map map;が唯一のメンバ変数であり、コンテナ本体のようだ。この型はどう定義されているのかを見てみる。118行目だ。
using segment_map=type_info_map< segment_type, newdelete_allocator_adaptor< typename std::allocator_traits<Allocator>::template rebind_alloc<segment_type> > >;
実態はtype_info_mapというものらしい。アロケータに深入りすると帰ってこれなくなりそうなので、type_info_mapとsegment_typeを調べてみよう。type_info_mapはpoly_collection/detail/type_info_map.hppで定義されている。segment_typeはなんだろう。これはすぐ上に定義があって、
using segment_type=detail::segment<Model,Allocator>;
となっている。これもpoly_collection/detail/segment.hppで定義されているようだ。ではそのファイルに飛んで見る。どうやらsegmentは2つのメンバ変数を持っている。
using base_sentinel=typename Model::base_sentinel; // ... using segment_backend_unique_ptr= typename segment_backend::segment_backend_unique_ptr; // ... segment_backend_unique_ptr pimpl; base_sentinel snt;
sentinelはModelの中で定義されており、backend_unique_ptrはすぐ上でsegment_backendの中で定義されている型として定義されている。segment_backendはdetail/segment_backend.hppで定義されていて、インターフェースを定義するための抽象仮想クラスのようだ。その37,38行目で、segment_backend_unique_ptrは以下で定義されている。
using segment_backend_unique_ptr= std::unique_ptr<segment_backend,void(*)(segment_backend*)>;
ところで、値が代入されるときはどうなるのだろう。122~126行目にpush_backがある。また、261,262行目にimplが、283,284行目にfilterがあって、push_back中で使われている。
template<typename T> base_iterator push_back(const T& x) { return filter(impl().push_back(subaddress(x))); } // ... segment_backend& impl()noexcept{return *pimpl;} const segment_backend& impl()const noexcept{return *pimpl;} // ... void filter(base_sentinel x){snt=x;} base_iterator filter(const range& x){snt=x.second;return x.first;}
segmentのpush_backはこのsegment_backend_unique_ptr型に対して何かしている。対して、sentinelはそこで帰ってきた値が代入されている、つまり更新されている。rangeを受け取った場合は後側を取るようなので、endに該当する意味のものを格納しているのだろうと推測できる。
しばらくはsegment_backend_unique_ptrの方を見てみる。これは仮想クラスへのポインタなので、実際の型はここではわからない。segment::makeがsegmentを作っているので、Model::make<T>が実際の型を作って代入しているのだろう。
template<typename T> static segment make(const Allocator& al) { return Model::template make<T>(al); }
ではModelが何をしているか少し見に行こう。detail/base_model.hppを見てみる。
84~89行目で、segment_backend_implementationがDerivedな型に対してpacked_segment<base_model, Derived, Alloc>のように定義されている。そして、107~111行目のmakeがこの型へのポインタを返しているようだ。恐らく、segmentのbackend_unique_ptrの中身はpacked_segmentだと考えていいだろう。
template<typename Derived,typename Allocator> using segment_backend_implementation=packed_segment< base_model, Derived, typename std::allocator_traits<Allocator>::template rebind_alloc<Derived> >; // ... template<typename Derived,typename Allocator> static segment_backend_unique_ptr make(const Allocator& al) { return segment_backend_implementation<Derived,Allocator>::new_(al,al); }
ではdetail/packed_segment.hppを見に行く。309行目のstoreが値を格納している。store型は、45~51行目で定義されており、vector型だ。ただし、value_holderというクラスを持っている。
using store_value_type=value_holder<Concrete>; using store=std::vector< store_value_type, value_holder_allocator_adaptor< typename std::allocator_traits<Allocator>:: template rebind_alloc<store_value_type> > >; // ... store s;
これはまあvalueをholdしているのだが、std::aligned_storageを用いてholdしている（実際には、value_holder_baseが持っていて、value_holderはそれを継承している）。
template<typename T> class value_holder_base { protected: typename std::aligned_storage<sizeof(T),alignof(T)>::type s; };
ここでaligned_storageを使っているのは、後でイテレータを上手くやるためだろうなと思う。stride_iteratorがsizeof(T)を持つようになっていて、その分スキップしていくように実装されているからだ。これをするためには、ポインタをずらした時に正しくオブジェクトの先頭に来ていることが保証できないといけない。ただ、aligned_storageについてそこまで詳しくないので憶測だ。
segmentが何を持っているかある程度片がついたので、sentinelの方も見てみよう。この型は、base_modelではBase*として定義されている。また、rangeの後半としても使われている。「歩哨・見張り」の名称の通り、恐らく最後尾（end)を指すポインタなのだろう。iterator_implがseg_posとsentinelが一致しているかどうかを確認していることも証拠の一つだ。実際、packed_iteratorの285行目で、
base_sentinel sentinel()const noexcept { return base_iterator{ value_ptr(s.data()+s.size()), sizeof(store_value_type) }; }
とあり、これはsentinelとしてstoreの先頭ポインタからstore.size()だけずらした場所を指している。
base_modelではbase_iteratorとしてstride_iteratorなるものを使っており、これは中でsize_t strideを覚えておいて、advanceの際にポインタにstrideずつ足していくというものだ。
型Tに対するポインタは通常は自動的にsizeof(T)だけずらされるが、stride_iteratorはこちらが設定した幅だけずらす。
using base_iterator=stride_iterator<Base>;
detail/stride_iterator.hppの106~107行目を見るとわかりやすい。型情報をその型の占める大きさとして各stride_iteratorが覚え、イテレータが毎回その分だけ動くことで、異なる型の配列に対するイテレータをいちどきに扱えるようにしている。これによってbase_collectionはrange-based-forのような機能に対応しているのだ。
void increment()noexcept{p=value_ptr(char_ptr(p)+stride_);} void decrement()noexcept{p=value_ptr(char_ptr(p)-stride_);}
ところで、base_collectionがbeginで返すのはbase_collection::iterator型で、これはiterator_impl型だ。iterator_implは中で2種類のイテレータを持っている。124,125行目だ。
// 型宣言 using segment_type=typename PolyCollection::segment_type; using const_segment_base_iterator= typename PolyCollection::const_segment_base_iterator; using const_segment_base_sentinel= typename PolyCollection::const_segment_base_sentinel; using const_segment_map_iterator= typename PolyCollection::const_segment_map_iterator; // ... const_segment_map_iterator mapit,mapend; const_segment_base_iterator segpos;
ここで、とsegment_base_iteratorは上記の通りsegment::base_iteratorだ。つまり、segment::Model::base_iterator、ここでModelがbase_modelなら、base_model::base_iteratorはstride_iteratorなので、base_modelの場合はsegment_base_iterator == stride_iteratorとわかる。
mapの中にあるそれぞれのvectorのイテレータを内部に持つためには確かにこれが一番よさそうだ。
あとは、インクリメントするときにsegposの方がsentinelと一致しているかどうか確認して、一致していればmapの次の要素へ切り替える。こうすることで、それぞれのsegmentを乗り換えることができる。
void increment()noexcept { if(++segpos==sentinel()){ ++mapit; next_segment_position(); } }
最後に、type_info_mapだ。完全に終わった気になっていたが、これを最初に後回しにしたままだ。まあいい。これはもう予想がついていて、(unordered_)mapに{type_info, segment}が入っているのだろう。見てみる。
メンバは2つある。
map_type map; cache_type cache;
ひとつ目は簡単だ。予想通りのマップだ。最初に定義がある。
using map_type=std::unordered_map< const std::type_info*,T, type_info_ptr_hash,type_info_ptr_equal_to, typename std::allocator_traits<Allocator>::template rebind_alloc<std::pair<const std::type_info* const,T>> >;
しかしふたつ目はなんだろう。定義は、
using cache_type=std::unordered_map< const std::type_info*,iterator, std::hash<const std::type_info*>,std::equal_to<const std::type_info*>, newdelete_allocator_adaptor< typename std::allocator_traits<Allocator>::template rebind_alloc<std::pair<const std::type_info* const,iterator>> > >;
なんだこれは。単により単純な型に見える。std::hashとstd::equal_toがポインタ型について特殊化されているので、これはキーとして単にポインタを持っているだけに見える。
さらに、値としては自身のイテレータなので、これは完全に高速化目的だとわかる。findなどを高速化するのだ。何故だ？
ところで最初にコメントがある。内容を要約すると以下のようになる。
動的リンクライブラリなどのために、標準は同じ型に対して互いに異なる複数の
std::type_infoを持つことを許容している。よってtype_info::operator==やtype_info::hash_codeは非常に重い処理になってしまう。type_info_ptr_hashとtype_info_ptr_equal_toは同じ型に対する複数の型情報を適切に扱うが、高速化を図るため、一度ルックアップされたtype_infoに対してより高速なハッシュによるマップを作成し、重いtype_info::hash_codeを呼び出す回数を減らしている。
なるほど。実行のタイミングでリンクする場合、同じ型が相手方に存在しているかは不明だし、std::type_infoの制限は確かにあまり強くできない。こうなるとhash_codeがどう実装されているか気になるが、特性からして明らかに実装定義だろう。
まとめ
新しく入ったライブラリの中身を少し覗いてみたが、随所にある工夫が中々面白かった。特に、type_info::hash_codeがそのようになっていることは知らなかったのでとても勉強になった。
個人的には、以前SIMD用のコンテナを作った時に自分が命名したstride_iteratorと全く同名のイテレータが途中で出てきたことが一番衝撃的だったが、これは自分の命名センスに自身を持つべきと解釈して構わないのだろうか。
(追記16:54; 読みにくかったのでboostからコードをより多く引用することにした)
