背景

さて、そもそも存在を知られていない気がするので、boost::compressed_pairの説明を少ししていこう。これは、std::pairと基本的には同じなのだが、どちらかの型引数が空クラスだった場合にその領域を消し去るというものだ。

そもそも、通常はstd::pair<int, void>などは作ることができない。以下はコンパイルエラーになる。

#include <utility>
#include <iostream>

void f(){return;}

int main()
{
    std::pair<int, void> p(42, f());
    std::cout << p.first << std::endl;
    return 0;
}

[Wandbox]三へ( へ՞ਊ ՞)へﾊｯﾊｯ

ではこういう場合どうしようか。例えば、空のクラスを作り、それをいれてみる。

#include <utility>
#include <iostream>

struct empty_t{};

empty_t f(){return empty_t{};}

int main()
{
    std::pair<int, empty_t> p(42, f());
    std::cout << p.first << std::endl;
    return 0;
}

ところで、このペアのサイズはどれくらいになるだろう。よくある環境なら、これは8バイトになる。だが、intは4バイトだ。何故8バイトも取るのか？　その理由はアライメント要求にある。intは4バイトアライメントを要求する（大抵の場合は）。これは何を意味するかというと、intは4の倍数アドレスにしか置けないということだ。なので、pairを例えば連続したメモリ領域に置こうとした時（std::vectorにいれるなど）、int、empty_t、intと来たこの２つのintは、両方共4の倍数に置かれなければならない。もしempty_tがゼロでないサイズのオブジェクトなら、間隔は4バイト以上にならざるを得ない。なので、4バイトの倍数になるようにパディングが入ることになる。そして実際、empty_tは１バイト要求する。

なぜempty_tが１バイト要求するのか？　C++ではアドレスがオブジェクトの一意性に関わっているので、空のクラスでも一意的なアドレスを取れるようにしないといけない。例えば空のクラスを構造体のメンバとして使った場合、もしサイズがゼロだったら、空クラスへのポインタはその構造体中の次のメンバ変数の領域を指してしまうだろう。その要素が最後に配置されたとしても、メモリ空間中で隣接する別のオブジェクト（配列の次の要素など）を指してしまうかも知れない。そういうことを避けるため、最低限の1バイト（多分sizeof(T) == 1になるようにしていると思うが、これは大抵の場合1バイトだ）を取ることになる。中身は不定だと思う。

そういうわけで、このペアは本質的にint一個分のサイズで済むはずなのだが、実際には2個分要求することになってしまう。そして中身の半分はガラクタだ。いくらメモリが潤沢な現代とはいえ、CPUキャッシュまで潤沢なわけではない。むしろメモリ上でのデータの局所性が重要になってきている現代において、ガラクタによって必要なデータが遠くに行ってしまうのは辛いだろう。

というわけで、何とかしてこういう場合にサイズをint一個分で済ませるというのがboost::compressed_pairの目的である。

使いドコロ

そもそも空のクラスとのペアって何だよ、ペアじゃなくていいじゃないか、というのは妥当なツッコミである。一体全体どういう時にそんな問題が発生するのか？

この使いドコロは、メタプログラミングにある。例えば、重い処理をするにあたって先に計算を済ませておける部分があるとき、済ませておきたいというのは当然の欲求だ。そこで、値のインデックスと先に計算しておいた値のペアを置いておきたいとする。

template<typename Calculation>
struct cache
{
    std::vector<std::pair<std::size_t, typename Calculation::parameter_type>> values_;
};

だが、先に計算しておくべきパラメータが存在しないCalculationというのがあり得る。この場合、parameter_typeをvoidにすると上記の構造体はコンパイルできないし、empty_typeにするとメモリを無意味に消費してしまう。そいう場合のためにboost::compressed_pairが存在する。

少し話が抽象的すぎてよくわからないので、具体例を出してみる。読者は分子動力学シミュレーションをご存知だろうか。

分子動力学法 - Wikipedia

なんだかゴチャゴチャ書いているが、要するに原子間にかかる力（分子力場）をうまく設定して、ニュートンの運動方程式を数値積分して原子が動くのを見て楽しむことだ。よく材料力学や生物物理学などの分野で活用されている。例えば、イオン同士の間に静電相互作用のポテンシャルを入れるとか、化学結合についてバネ（調和振動子）ポテンシャルを入れるとか、そういうことをする。

さて、この中でも最も基本的だと思われる、Lennard-Jonesポテンシャルを例に上げることにしよう。これは単純な式ながら分子間力のかなり良い近似になっているので、殆どの分子力場に何らかの形で含まれている。分子間力は2つの要素からなり、瞬間的な電子分布のゆらぎによる双極子間相互作用、つまりロンドン分散力による引力と、電子同士が近接した時のパウリの排他率による斥力である。いろいろおもしろい話はあるが、そういう話をしにきたわけではない。

さて、分子シミュレーションの計算量は多い。Lennard-Jonesのような分子間力は全ての粒子の間に作用するので、計算には全てのあり得る粒子のペアを考える必要があり、これにはO(n²)の時間を要する。これで粒子数が1万とかだと（この数はタンパク質のシミュレーションでは標準的な数だ）、愚直に計算していると統計力学的に意味のある話ができるくらいの時間シミュレーションを実行するには信じられないくらいの時間がかかる。

で、効率化したいというのは当然の欲求ということになる。一般に、最も効率のよい最適化は、計算しないことだ。分子間力にはカットオフという概念がある。多くのポテンシャルは無限遠点で値がゼロになるようにされていて（これは強い相互作用によるクオークの閉じ込めみたいな例外的な場合を除いて妥当な話だろう）、そのため、ある有限の距離でも無視できる程度の弱さまで減衰する。そのため、ある程度以上遠い粒子の間の力は計算しなくていい。これがカットオフだ。

これだけでもある程度速くはなるが、どうせ計算しないペアを見てスキップするというのは少しアホらしい。このため、先に「相互作用しそうなペア」をリストアップしておいて、そのペアだけについて計算するという方法が取られている。もちろん粒子はシミュレーション中に動くので、このリストを時々アップデートする必要があるわけだが、そこらへんのトリックは各自調べてほしい。簡単に説明しておくと、先にカットオフよりも長い距離でペアを探索しておいて安全マージンを作っておき（このためリストの一部は無駄になるが、まあそれはそんな数ではないので）、粒子が動いた分だけマージンを減らしていくという感じだ。

さて、話が長くなってきたが、もう少し説明を追加しないといけない。このLennard-Jonesポテンシャルは2つのパラメータを取る。粒子の大きさと、力の強さだ。もちろん、これらのパラメータは原子の種類によって変わる。特に、これは原子のペアに依存するので、原子の種類が増えると組み合わせ的に増大する。これはやっていられないので、各原子についてのパラメータからペアについてのパラメータを決める方法が考えられている。ローレンツ・ベルテロ則を使えば、各原子のパラメータだけを覚えておいて、ペアについてのパラメータは相加平均と相乗平均でオンデマンドに計算することができる。

やっと本題だが、相乗平均はsqrtを必要とする。だがsqrtは重い処理だとして知られている。そのため、力の計算のときに何度もしたくはない。ところで、我々は相互作用しそうなペアのリストを作って使いまわしているのだった。なら、このリストについでに相乗平均の値を持たせてしまえばよい！

というわけで、以下のようなクラスが発生するだろう。

template<typename Potential>
struct NeighborList
{
    // list of { pair of {
    //    neighboring particle index, pre-calculated parameter
    // } }
    std::vector<std::pair<
        std::size_t, typename Potential::value_type
        >> pairs;

    // list of { range of {neighbor of i-th particle} }
    std::vector<std::pair<std::size_t, std::size_t>> neighbors;
};

ああ、ようやく戻ってきた。だが、このPotentialの中には、例えばパラメータが一様なのでそもそも相乗平均なんかとらなくていいとか、事前計算が掛け算一個とかで格納するメリットがほぼ無いとか、そういうものが後々出てくるだろう。そうすると、これはまさしく上記の問題に遭遇することになる。こういう場合にcompressed_pairを使えば、何も気にすることなく全ての場合に対応できる。そうでなければ、意味不明なメタプログラミングか（constexpr ifを使えば簡単になるかもしれない）、メモリの無駄遣いに耐えるしか選択肢がなくなる。

長くなりすぎてしまった。少し珍しい場合のことを考えるためには、前提を共有する必要があって説明が不必要に長くなってしまう。抽象的な例を挙げているだけの方がマシだったかもしれない。

仕組み

ところで、ではcompressed_pairは何をどうやって空クラスのサイズをゼロにしているのだろうか。これを理解するには、empty base optimization (EBO)というものを説明せねばなるまい。基底クラスには、その派生クラスとポインタの値が違わなければならないという保証はないので、基底クラスが空の場合、本当にサイズをゼロにすることができる。このとき、基底クラスへのポインタは派生クラスのポインタと一致する。さらに特定の場合、最初のメンバ変数へのポインタとも一致するが、それはさておき。

EBOをうまく使っている例はちょいちょい見受けられる。例えば、short string optimization(SSO)だ。これは文字列が十分短い時は動的確保をせずにクラス内に持ってしまうというもので、できるだけ小さいクラスにできるだけ多くのchar buf[N]を詰め込むために、いろいろなテクニックを駆使している。その一つがEBOで、アロケータはたいてい状態を持たない（単にnew/deleteするだけ）ので、空のクラスだ。同じサイズのクラスに1文字でも長い文字列を格納したいので、これに費やす1バイトをcharに割り当てたい。なので、他のメンバを一度構造体のメンバとして持ち、その構造体がアロケータを継承することでEBOを有効にしている。SSOは以下の記事で詳しく解説されている。

qiita.com

さて、もうお分かりの通り、compressed_pairもEBOを活用している。ペアの片方が空だった場合、それを継承してしまうのだ。するとEBOによって空のクラスのサイズが消え去る。使う側は何も気にしなくてよい、というわけだ。

まとめ

というわけでboost::compressed_pairは、template引数に応じて必要だったり不要だったりする値があるとき、メタプログラミングなしでメモリの使い方を最適化できる便利なクラスだ。これを期に検討されてはいかがだろうか。

in neuro

boost::compressed_pairの使いドコロ

背景

使いドコロ

仕組み

まとめ