Expression Templateの蛇足的な話
Preface
前にプリプロセサを駆使してシリアライザを書いたことがあったのですが、Expression Template(以下 式テンプレート)を使えば#define使わなくても近いようなことできるなーと思いついたので、実際に作ってみました。
で、そっちを説明しようと思ったんですが、やっぱり気が変わって、式テンプレート自体の自分なりの理解を簡単に説明したいと思います。 ちなみに式テンプレートのちゃんとした入門は、参考URLの方で錚々たる方々が素晴らしい記事を書いているので、そちらを参考にしてください。この記事はまぁ、蛇足的な、自己満足のためのものです。
Introduction
式テンプレートは、最初、行列やベクトルを使った科学計算の効率化のために考案されました。 例えば以下のようにVectorクラスの演算を行うとします。
Vector v_result, v1, v2, v3;
v_result = v1 + v2 - v3;
この時、式テンプレート手法を用いていないVectorクラスの場合、各「+」「-」演算子が評価される度に一時オブジェクトが生成されてしまいます。密ベクトルクラスの場合要素数がdouble型で1万次元やそれ以上が普通だったりするので一度生成される度に8 * 10000 = 約79KBのコピーが発生してしまい、使い物にならないプログラムができあがります。
そこで、一時オブジェクトを生成せずに「v_result = v1 + v2 - v3;」という記述を可能とするのが式テンプレートです。
ただこういう説明から入ると誤解してしまうのですが、式テンプレートは科学計算だけに利用されるものではありません。 (僕も科学計算をするのであればublasなどの既に実装されているライブラリを使えばいいと思って、本の説明も飛ばしてしまうことが多かったです。)
それでは式テンプレートとは何なのか、ということをオレオレ解釈で述べてみると、
C++で制限つきの遅延評価を実現する仕組み
だと思っています。
Imprementation
式テンプレートは2段階の処理に分かれます。 「構築フェーズ」と「評価フェーズ」です。下の図は件の式をフェーズごとに分解した図です。
演算子の優先順位から、まず右辺の構築フェーズが実行され、その後評価フェーズが実行されます。計算を必要な時(評価フェーズ)まで遅延させるのが式テンプレートの目的です。
Construction Phase
構築フェーズは以下のような構文木を作成するフェーズです。
Expというのは一時的に引数と計算方法を保持するプロキシオブジェクトです。 保持といっても参照を保持するだけですので、コピーは行われません。 (また、コンパイラの最適化によって最終的にこのプロキシオブジェクトは削除されますのでオーバーヘッドもありません。)
実際にコードを書くと以下のようになります。 (Vector型は簡単のため、配列ではなくint型を一つだけ保持するようにしています。 またこれ以外のメソッドも本来必要ですが、着目して欲しい箇所だけ抜きだしています。 全体のコードを確認しながら先に進みたい方はこちらを参照)
class Vector {
int i_;
public:
Vector(int i) : i_(i) {}
template
Exp operator+(const R &r){
return Exp(*this, r);
}
};
template
class Exp {
const L &lhs_;
const R &rhs_;
public:
Exp(const L& l, const R& r) : lhs_(l), rhs_(r) {}
template
Exp, OpMinus, R2> operator-(const R2 &r){
return Exp, OpMinus, R2>(*this, r);
}
};
まず右辺の式「v1 + v2 - v3」は+,-演算子が左結合ですので「v1 + v2」が評価され、Vectorクラスのoperator+メソッドが呼ばれます。ここでは、以下のようにExpの一時オブジェクト(以下 Exp<v1, +, v2>のように表記)を返しています。
template
Exp operator+(const R &r){
return Exp(*this, r);
}
次に「Exp<v1, +, v2> - v3」が評価されここではExp::operator-が呼ばれます。
template
Exp, OpPlus, R2> operator-(const R2&r){
return Exp, OpMinus, R2>(*this, r);
}
これで上記のようなExpオブジェクトの入れ子になった構文木オブジェクトをoperator=に渡して評価フェーズが始まります。
Evaluation Phase
次に評価フェーズでは、上記の構築フェーズで作成した構文木を自由に渡り歩くことにより実行されます。 ここで重要なのは評価フェーズでは上記で構築された構文木の、オブジェクト(v1, v2, v3)、それぞれの計算方法(OpMinus, OpPlus)全てにアクセスできるという点にあります。
実際に構文木を渡り歩く処理を書いてみます。 (今回も着目して欲しい箇所だけ抜き出しています)
struct OpPlus {
static int apply(int i, int j){
return i + j;
}
};
struct OpMinus {
static int apply(int i, int j){
return i - j;
}
};
template
class Exp {
const L &lhs_;
const R &rhs_;
public:
int eval() const {
return Op::apply(lhs_.eval(), rhs_.eval());
}
};
class Vector {
int i_;
public:
template
Vector& operator=(const E& exp){
i_ = exp.eval();
return *this;
}
int eval() const{
return i_;
}
};
まず、「Vector::operator=」から「Exp::eval()」が呼び出され、次に「lhs.eval()」つまりExp<v1, +, v2>を評価します。 Exp<v1, +, v2>::eval()は「OpPlus::apply(v1.eval(), v2.eval())」を評価して返します。 v1.eval(), v2.eval()はそれぞれ自分の持っているデータを返しているだけですので「v1.i + v2.i_」という二つのint型の和を返すことになります。以下同様です。
Application
例えば、式テンプレートを使ったロガーの実装を考えてみるとします。 tkngさんの日記で、google-glogはデストラクタを使うことで、書き出す文字列が確定してから一度に出力するという操作を実現しているという話がありました。
式テンプレートを使えば、
#definee LOG(x) LogMessage(x).stream() = LogMesage(x).dummy()
int main(void){
int x = 0;
size_t z = 3;
LOG(INFO) << x << "y" << z;
}
のようなコードを書いた場合、LogMessage(x).stream()が返す一時オブジェクトのoperator=が呼ばれる時には、x, "y", zといった書き出すべき文字列が確定しているので、デストラクタを使った場合と同様に一度に書き出すことが可能となります。
デストラクタを使うのではなく、こういった実現方法もあるのではないか、と思った次第でした。 本当にできるかどうかは試していないのでわからないですが、式テンプレートのことを「一時オブジェクトを消す仕組み」と覚えるのではなく、「遅延評価を実現する仕組み」と考えることで応用範囲が広がるんじゃないかと思っています。
Postscript
今回説明に用いたコードはgithubに上げていますので、全体を見たい方はこちらをご確認ください。また最初に話したシリアライザーのコード自体はまだ未完成ですが、この辺に転がしてあります。
boost::lambdaもそうですし、boost::xpresiveなど式テンプレートの手法を利用したライブラリは今後も増えて行きそうですね。 自分で式テンプレート対応のベクトルクラスを作るときはもちろん必要ですし、ライブラリを利用する場合でも、どういう仕組みかどうかを知っておくと、効率的に使えるようになると思います。 (僕はよく知りませんが、boost::protoを使えばさらに書き易くなるようです。)
Refences
参考URL Faith and Brave - C++で遊ぼう: Expression Template 本の虫: Expression Template Cry’s Diary: 日本で一番分かりやすく書いたつもりのExpression Templateの説明 Cry’s Diary: ETの考え方とその簡単な実装 With Unz: Expresion Template参考書籍
C++テンプレートテクニック
