AoSとSoAなflat_map
std::mapを線形配列に落とし込むことで、イテレータ走査やメモリレイアウトを効率化したflat_mapについては以前説明しました。
当時私が実装したflat_mapはArray of Structure(AoS)形式の実装で、構造体を線形配列に配置するものでした。これはキーと値がメモリ上で並んだ位置に配置されるので、キーから検索した直後に値を使う場合にはキャッシュに載っている可能性が高くなる利点があります。
一方Structure of Array(SoA)形式の実装も考えられ、C++23で導入されるstd::flat_mapはこちらの実装となる予定です。この形式ではキーの配列と値の配列がそれぞれ用意されることで、キーの走査速度がAoSに比べて良くなることが期待されます。特に値が巨大である場合には、AoSではキーがかなり飛び飛びになるためキー走査でキャッシュヒット率が期待できず、そこまでパフォーマンスの向上が期待できません。しかしSoAではキーの走査ではキーの配列を走査するだけなので常にキーが連続した空間に配置され、高速にキーを走査できるという利点があります。
AoSとSoAはHigh Performance Computing(HPC)の分野ではよく扱われる問題ですが、一般的にはあまり意識されない問題だと思います。
C++23のflat_map*1ではKeyとValueのコンテナをそれぞれテンプレートパラメータで指定できるため、任意のコンテナをそれぞれ指定できます。 これは一般にzip_iterator*2と呼ばれるイディオムを使って実装されますが、現在の標準仕様ではzip_iteratorを任意のアルゴリズムに適用するということが困難でした。P2321ではこれを解決し、zip_iteratorの代わりにzip viewというものを適用します。C++23のflat_mapでは内部的にこれと同等のものを使い、複数のコンテナをあたかも1つのコンテナのように扱いflat_mapを実現します。
一方もともと私が実装していたflat_mapではvector<pair<Key, Value>>のようなコンテナをベースとするため、テンプレートパラメータにはただ1つのコンテナだけを受け取るような実装になっていました。しかし、これはzip_iteratorを返すコンテナを実装できれば1つのflat_mapでAoSとSoAのどちらも提供できる可能性があり、一度は実装を試したものの当時はアルゴリズムへの適用が困難で諦めていました。
しかしP2321が出現したことでその夢が実現できる見通しとなり、先日その実装が完了しました*3。
#include <flat_map/flat_map.hpp> flat_map::flat_map<Key, Value> aos; // AoS style flat_map #include <flat_map/tied_sequence.hpp> using soa_container = flat_map::tied_sequence<std::vector<Key>, std::deque<Value>>; flat_map::flat_map<Key, Value, std::less<Key>, soa_container> soa; // SoA style flat_map
専用コンテナを使うため型が冗長であるものの、1つの実装でどちらにも対応できるようになり、簡単にメモリレイアウトの変更を試せる様になりました。
とりあえず一通りのテストは通るので概ね問題ないとは思いますが、dangling referenceがどこかにありえるとは思うので、適当にいじめてもらえると大変助かります。
