Orz日記 by Akio Morita

_ [SAD][YaSAI]GMPのC++版は遅延評価

数値リテラルの扱いをGMP/MPFRを使って実装しようと考えているのだが、 数値クラスを扱いやすくするために、C++上のクラスと 演算子オーバーロードを定義する方法を考察中。

単純な実装では、a=b+cを実行するにはb+cの結果を格納する 一時オブジェクトfooを生成してaに対する代入演算子の オペランドとして使用後に破棄する必要があるが、この一時オブジェクトが 多倍長精度整数や多倍長精度浮動小数点であった場合、生成破壊のコストが 高く付く(式が複雑な場合は特に)訳で、性能のボトルネックになるのは 確実である。既存の実装はどのようにしてそれを避けているかを調べてみた。

MPFR自身にはC++サポートは存在しないが、GMPにはC++サポートがある。 で、ヘッダーを読んでみて目から鱗が...

結論は、演算子が式を表現するProxyオブジェクトを返すことで、 実際の式評価を評価結果の格納先が確保されるまで遅延する(遅延評価)ことで、 全ての演算を3オペランド形式で実行し、余分な一時オブジェクトの 生成コストを回避していた。 GMPの実装では、演算子表現に関数オブジェクト、式のProxyオブジェクトは テンプレートクラスから実体化している。また、一部の演算は テンプレートクラスの特殊化を行い、演算量を削減している。

このテクニック自体は、ベクトルやマトリクス演算子にも応用できるはず。

実装上の注意としては、次の点があげられる。

• 代入演算子と複合代入演算子の格納先を右辺の式が参照することがあるので、右辺の評価値が確定するまで代入先のオペランドの更新を遅延しなければならない。
• 提供する数学関数群は、Proxyオブジェクトを受け取れるようオーバーロードする必要あり。(ユーザー定義クラス間の自動変換は行われないので、関数の引数に式が書けない)

遅延評価なので、最終的な結果が代入されない場合は Proxyオブジェクトの 生成破壊のみで、演算評価を行わないですませることが出来る

ただ、コンパイラの仕事は大変そうだ(w