[C++][ADAPT]データ分析、処理ライブラリADAPTの更新情報(1)。

C++ GitHub

ADAPTの更新情報である。リポジトリを公開してから3ヶ月間で色々と修正や機能追加してきたが、そのあたりについて簡単にまとめておく。

ADAPTについての説明はこちらへ。
ADAPTのGitHubリポジトリはこちらへ。

DTable、STableの追加

ADAPTがもともと有していたコンテナは、DTreeとSTreeである。これらは階層構造を基本としており、構造化されたデータを扱いやすい反面、速度的にはどうしてもテーブルに劣ってしまう。そこで、より高速なDTable、STableを追加した。

DTableは-1層と0層の要素しか持つことが出来ない代わりに処理がかなり簡素化されており、DTreeと比べて余計なオーバーヘッドがない。すごく大雑把に言えば、Treeと比べて走査や抽出などが2～3倍ほど速い。 ただし、STableは0層までしか定義しないSTreeと機能的に全く同等である。もう少し正確に言えば、0層までしか定義しないSTreeは今回の更新でSTableと同等の機能を呼び出すように変更した。0層までのSTreeは従来より高速化し、STableと同等になったわけである。よって、STableを敢えて使う意味は、テーブルであることを明示したいとき以外には特にない。そんな無意味なものを用意したのは、対称性を気にしてしまう物理屋の性だ。

使い方は0層までしか持たないTreeとほぼ同等である。違うのはDTableの0層の構造を定義するときに呼び出す関数だけ。

//DTreeの場合
DTree tree;
tree.SetTopLayer({ "root_field_name", FieldType::Str } });
tree.AddLayer({ { "field_name0", FieldType::I32 }, { "field_name1", FieldType::F64 } });
//treeの場合はさらに1層、2層を追加できる。

//DTableの場合
DTable table;
table.SetTopLayer({ "root_field_name", FieldType::Str } });
table.SetLayer(0, { { "field_name0", FieldType::I32 }, { "field_name1", FieldType::F64 } });
//DTableは1層以下を扱えない。SetLayer(0, ...)と0を与えているのは将来的な拡張の可能性があるため。

Extractの並列化

次のように既存のTreeから新たにTreeを生成するExtractという機能があるが、これを並列処理に対応させた。

DTree extract = tree | Filter(...) | Extract(...);

スレッド数はデフォルトではstd::hardware_concurrency()によって取得されるその処理系のスレッド数に一致する。明示的に指定したい場合はadapt::SetNumOfThreads(num_of_threads)を呼ぶ。
またadapt::SetGranularity(gran)とすることで、各スレッドの処理する粒度を指定することができる。デフォルトでは128である。この粒度granに基づき、0層要素をgran個ごとに区切って、区切られた区画ごとにスレッドが処理をしていく。granの値が小さすぎるとスレッド間の競合が増えるのでパフォーマンスが落ちるが、粒度が大きすぎるとスレッドごとの処理負荷が均一でなくなるためこれもパフォーマンスが落ちる。適切な粒度の値はtreeの構造や要素数によって異なるだろうし、tableを相手にするならもっと大きな値のほうが良いかもしれない。デフォルトの128という値も今後変更する可能性がある。

8コア16スレッドのRyzen 7 7700Xで、最大階層2、全245万要素のDTreeからExtractするテストを行ったところ、シングルスレッドで135ms、マルチスレッドで19msとまずまず順当に高速化できていた。DTableだと素の速度が早いことと各スレッドから得た結果をマージするコストが相対的に大きいことからそれほど効果はなく、粒度を調整してもせいぜい2-4倍程度の向上に留まった。
近いうちToVectorも並列化するつもりである。

Treeの要素の追加、削除などを行う関数を追加

Treeの要素を追加する関数としては、今まではReserveとPushのみが事実上使用可能な状態だった。ここに新たにResize、Assign、Insert、Erase、Popの5種類の関数を追加した。

//下層の要素数をsize個にする。std::vectorのresizeに近い。
void Resize(BindexType size);

//自身の各フィールドにそれぞれvs...を代入する。代入演算子のようなものと考えて良い。全フィールドに一括代入したい時に。
template <class ...Fields>
void Assign(Fields&& ...vs);

//下層要素のindex番目にvs...をフィールドとして持つ新たな要素を挿入する。std::vectorのinsertに近い。
//現時点では複数個を一気に挿入することはできない。
template <class ...Fields>
void Insert(BindexType index, Fields&& ...vs);

//下層の末尾要素を削除する。std::vectorのpop_backみたいなもの。
void Pop();

//下層要素に対して、指定されたindexからsize個分を削除する。std::vectorのeraseみたいなもの。
void Erase(BindexType index, BindexType size);

AND/OR演算子の短絡評価を可能に

Placeholderを用いたAND/OR演算のラムダ関数を定義するとき、内部的に短絡評価できていなかったので、これを改善した。例えば以下のコードでは、Filter関数に与えたlambdaを実行する際、x == 5がfalseであった場合にもy == 10が評価されていた。明らかに無駄な計算なので、短絡計算するよう修正した。

DTree tree;
auto [x, y, z] = tree.GetPlaceholder("x", "y", "z");
auto lambda = (x == 5 && y == 10);
tree | Filter(lambda) | Show(z);

なお、ラムダ関数中で使えるif_/switch関数も同様に、余計な評価を回避するようにした。

細かな修正

  1. KeyJoint使用時にコンパイルができない場合がある不具合の修正。
  2. first/last階層関数の追加。
  3. DTreeの要素数変化を伴う操作を行うときに、全要素がtrivially_copyableである場合に余計なオーバーヘッドを減らすように修正。

他にも色々とバグ修正をしたような気がするが、細かいところは覚えていない。

雑記

案の定大して使ってもらえていないようだが、仕方ない。OSSなんてそれなりに人目に触れる場所で宣伝しなければ気づいてさえもらえないことは、私もよく知っている。
たとえ需要がなくとも、自分自身が欲しているので更新は続ける。研究に導入できるかどうかは他人を説得できるかどうかに掛かっているのではっきり言って大博打だが、導入できれば利便性について大きなメリットがある。

Extractの並列化が終わったので（かなり冗長でよろしくない書き方になっているので、後々修正したいが……）、そろそろ3Dビューアの制作に着手したいところである。研究の方でかなり大型のファイルを扱う機会が増えており、旧ADAPTをベースとした3Dビューアでは持て余すようになってきたのだ。OpenADAPTは従来比でメモリ使用量60%減、速度10倍くらいに向上させたので1、大規模データ解析を行う上では何としてもこちらに切り替えたい。
しかし色々とハードルがある。特に気がかりなのは文字列式からラムダ関数を生成する機能で、任意のデータを可視化するためには必須なのだが、原理的に可能なもののコンパイル時間の肥大化が心配だ。今のところ、根本的な解決方法は思いついていない。どうしたものか。

  1. 旧ADAPTは私がC++歴2-3年の頃に設計したもので、当時の私の技術不足がよく分かる数字である。↩