悪いデータ構造のオーバーヘッドと最適化
データ構造(miraiの用語では内部データ構造)は最適化の余地がある。C言語はいくつかの強制的な仮定をstructやunionに対して行うので、コンパイラは(仮にプログラマがバカでも)最善を尽すことはできない。
miraiは内部データ構造とエッジデータを明確に分離するので、データ構造の実現方法はコンパイラが決めることになる。
既存の研究としてはLLVMを用いた、以下のようなものがある(再掲)。
背景
CellのSPEのようなストリームプロセッサや近年のプロセッサにおけるキャッシュのプリフェッチ等、データ構造に対する操作のうち、データ構造に本質的でない部分がパフォーマンスの多くを占めるアーキテクチャが多い。つまり、データ構造に対する操作 - これは通常のプログラミングでは演算に次いで多い - の多くに関してアーキテクチャに特化した最適化の余地があるということになる。
miraiの想定するデータ構造最適化
重要なのは、これらの最適化の有効性はアーキテクチャにより異なるという点で、C言語のソースコードをただ単純にコンパイルするだけではこれらの最適化を効果的に行うことはできない。ソースコードからソースコードへの変換は状況を改善する可能性があるが、(miraiで言うところの)エッジデータであるか否かの判定には一定の問題がつきまとう*1。
また、自動的な最適化は(今のところ)主眼ではない。至近の目標は、様々なアーキテクチャに対して異なるアプローチが有効であることの広範な証明といえる。
- ポインタの圧縮
64bitアーキテクチャにおいてポインタは64bit長となるが、通常、64bit空間全体にポインタが分布することは無い。
そこで、ポインタの代りに序数を使うか、オフセットアドレスのみを格納することとして32bitやより短い数に抑えることを考える。多くの場合、このポインタの圧縮よりも次のページングが有効な解決策となる。
- ページング
いくつかの表を集積して、一つの表にまとめる。
細かいメモリの確保はヒープを断片化し、無駄なメモリ領域を生み、メモリアクセスを分散させる。メモリアクセスを適切なサイズ(これはアーキテクチャごとに異なる)にまとめ、周囲のアクセスを可能なかぎりキャッシュにヒットさせる。
もっとも、2分木の記述に対してこの最適化を施してもB-treeになるわけではない。これは自動的なバランスを提供できない*2。
この最適化が想定しているのは、『複数の表を集積した構造体の生成』であり、ポインタの圧縮(ポインタの数が減らせる)や、関連する構造体の集積を考えている。
- リスト操作、検索操作の生成
miraiのデータ構造記述にはchainやkey-mapの形で予め非常によく利用されるセマンティクスが抽象化されて存在するため、順方向操作しか利用しないなら逆ポインタを挿入しないといった最適化が可能になる。
また、単純なトラバースのループを分散処理する際のデータ分割等にも使用できる。
- 構築/破壊操作の生成
中心的なアイデアではあるが、これはよく考察されていない。
エッジデータから内部データ構造への変換を、エッジデータへのアクセスパターンから生成することができるのではないかと考えている。しかし、アクセスパターンを静的に解析することは困難であるため、現在のところ良い方法が見つかっていない。
通常のコンパイラにおけるプロファイラを利用した最適化のように、実際のファイルや通信ログを利用した最適化手法が有力と言える。
想定するアーキテクチャ固有の最適化
これらを行った後の構造体が、アーキテクチャによって全く異なるということを期待している。もし、アーキテクチャが異なっていても同様なデータ構造が採用できるならば、C言語のセマンティクスでも十分に実現可能であるということになる。
このような最適化は通常アーキテクチャ固有のコードとして分離した上で行われるケースが多いように思うが、一つ一つのプロトコル実装においてこれらを行うのは人手では非常に難しい。
また、インテリジェントなキャッシュを備えたOoO(out-of-order)プロセッサはこのような最適化を行わなくても十分に速いが、ストリームプロセッサのような小規模ハードウェアがOoOプロセッサと同等のパフォーマンスを発揮するためにはこれらの最適化は必須と言える。
- プリフェッチ/ダブルバッファリング
近年のプロセッサは、投機的ロードやプリフェッチを備えている。これは特にランダムなグラフのトラバースや行列の読みこみ等で重要になる。プリフェッチはキャッシュライン単位で行われるため、連続してアクセスされる可能性が高い要素を連続して配置する。
ストリームプロセッサでは、非常に遅延の多いDMAを介してしかメインメモリへのアクセスが行えないケースが多いため、ダブルバッファリングを行うようなコードを自動的に生成する。
- SIMDフレンドリな操作
SIMDプロセッサは、非常に特徴的なベクタ操作(ベクタのコピーや入れかえ、シャッフル)が高速に行えるという特徴がある。
例えば、序数をベクタとして格納し、選択操作を並列的に行う。
