値返ししよう。
小さな算術クラスは値返ししようというお話。
以前(といっても1年半以上前だが)僕はconst参照を使ってET(Expression Template)を実装しようと試みたことがある。
const参照ならコピーのコストが無いので、これがさらに最適化すればETが実装できるはずだと。実際に自作のベクタークラスを用いて書いてみたら成功した。
しかし成功したんだが、その過程で新たなことがわかってしまった。それは、
const 参照を使わずに値で変数を保持し、値で返したほうが良い
ということだ。
さらにそこまでしてもETを使っている限りうまく最適化できない場合があり、
素直な実装に劣る
ということまでわかってしまった。
どういうことか、ベクタークラスを例にとって説明します。ETでは元となるクラスを「式(項)クラス」のなかに保持する。ここでconst 参照をつかうということは、以下のようになる。
class Vector;//要素をdouble型で持っている3次元型 template<class P,class Q>//P,QにはVector型もしくはVector型からなる式クラスが入る class Expression2_plus{//2項 + 演算子からなる項 private://member! const P & left; //const 参照 ここと const Q & right;//const 参照 ここのことね。 public: //const参照をメンバに入れるときは初期化リストを使う Expression2_plus(const P & lhs,const Q & rhs):left(lhs),right(rhs){} double operator[](std::size_t i)const{ return left[i] + right[i] ; } }
//ほんとはP,Qってこんなジェネリックにしちゃまずい。 //対処法はCRTPを使う。 template<class P , class Q> inline Expression2_plus<P,Q> operator+(const P& lhs, const Q& rhs){ return Expression2_plus<P,Q>(lhs,rhs); }
使うときには
Vector v1(1,2,3); Vector v2(4,5,6); Vector v3(7,8,9); double a = (v1+v2+v3)[2];//2+5+8 = 15
なんてことができる。
しかし式クラス中にメンバ変数は値で持っていた方が良い。
const P left; //const値 ここと const Q right;//const値 ここを変更したです。
以下の関数を例にとってgccの-S出力を見てみる。コンパイラはMinGW g++ (gcc version 3.4.2 (mingw-special)) 最適化オプションは -O2
void func(Vector & out, const Vector & a1, const Vector & a2, const Vector & a3){ out = a1+a2+a3; }
以下メンバをconst参照(59)
pushl %ebp movl %esp, %ebp pushl %ebx subl $52, %esp movl 12(%ebp), %eax movl 8(%ebp), %ebx movl %eax, -12(%ebp) movl 16(%ebp), %eax movl %eax, -16(%ebp) leal -12(%ebp), %eax movl %eax, -24(%ebp) leal -16(%ebp), %eax movl %eax, -20(%ebp) movl -24(%ebp), %eax movl -20(%ebp), %edx movl %eax, -32(%ebp) movl 20(%ebp), %eax movl %edx, -28(%ebp) movl %eax, -36(%ebp) leal -32(%ebp), %eax movl %eax, -48(%ebp) leal -36(%ebp), %eax movl %eax, -44(%ebp) movl -48(%ebp), %eax movl -44(%ebp), %edx movl %eax, -56(%ebp) movl %edx, -52(%ebp) movl -56(%ebp), %edx movl (%edx), %eax movl (%eax), %ecx movl 4(%edx), %eax movl (%eax), %eax fldl (%eax) movl -52(%ebp), %eax faddl (%ecx) movl (%eax), %eax faddl (%eax) fstpl (%ebx) movl -56(%ebp), %edx movl (%edx), %eax movl (%eax), %ecx movl 4(%edx), %eax movl (%eax), %eax fldl 8(%eax) movl -52(%ebp), %eax faddl 8(%ecx) movl (%eax), %eax faddl 8(%eax) fstpl 8(%ebx) movl -56(%ebp), %edx movl (%edx), %eax movl (%eax), %ecx movl 4(%edx), %eax movl (%eax), %eax fldl 16(%eax) movl -52(%ebp), %eax faddl 16(%ecx) movl (%eax), %eax faddl 16(%eax) fstpl 16(%ebx) addl $52, %esp popl %ebx popl %ebp ret
以下メンバを値で保持(33)
pushl %ebp movl %esp, %ebp pushl %ebx subl $228, %esp movl 12(%ebp), %ecx movl 16(%ebp), %eax movl 20(%ebp), %edx movl 8(%ebp), %ebx fldl 8(%ecx) fldl 16(%ecx) fldl 8(%eax) fldl 16(%eax) fldl (%eax) fxch %st(4) faddp %st, %st(2) faddp %st, %st(2) fxch %st(2) faddl (%ecx) fldl 8(%edx) fldl 16(%edx) fxch %st(2) faddl (%edx) fxch %st(4) faddp %st, %st(1) fxch %st(2) faddp %st, %st(1) fxch %st(2) fstpl (%ebx) fstpl 8(%ebx) fstpl 16(%ebx) addl $228, %esp popl %ebx popl %ebp ret
追い討ちをかけるように、以下はETを使わずに素直な実装。(29)
pushl %ebp movl %esp, %ebp pushl %ebx subl $100, %esp movl 16(%ebp), %eax movl 12(%ebp), %edx movl 20(%ebp), %ecx movl 8(%ebp), %ebx fldl (%eax) fldl 8(%eax) fldl 16(%eax) fxch %st(2) faddl (%edx) fxch %st(1) faddl 8(%edx) fxch %st(2) faddl 16(%edx) fxch %st(1) faddl (%ecx) fxch %st(2) faddl 8(%ecx) fxch %st(1) faddl 16(%ecx) fxch %st(2) fstpl (%ebx) fstpl 8(%ebx) fstpl 16(%ebx) addl $100, %esp popl %ebx popl %ebp
最後のやつはアセンブラリスニングが苦手な僕でも何やってるかわかる。スタックの処理が最適化しきれていない気がするがほぼ完璧なコードだ。
今回はgccで行なったが、cl(Visual C++)でもほぼ同様の結果が出た。
const参照の弊害がわかると思う。勿論最適化をかけなければ値よりもconst参照のほうが良いだろう。しかしconst参照は最適化を阻害する。なぜなのかは僕にはわからない*2。
少なくともコピーのコストが元々小さいクラスにおいては値によるコピーを選択する方が無難だろう。
おまけ:
上記までのコードはoperator+の仮引数のところでconst参照を使っている。そこでETのコードのうち関数の引数まで値にしてみるとどうなるか。(追記:以下のコードは実際の実装ではスライシングが起こるので危険)
たとえば以下のように。
//ほんとはP,Qってこんなジェネリックにしちゃまずい。 //対処法はCRTPを使う。 template<class P , class Q> inline Expression2_plus<P,Q> operator+(const P lhs, const Q rhs){ return Expression2_plus<P,Q>(lhs,rhs); }
以下メンバも仮引数も値
pushl %ebp movl %esp, %ebp subl $360, %esp fldl -347(%ebp) movl 8(%ebp), %eax fldl -339(%ebp) fldl -331(%ebp) fxch %st(2) fstl -344(%ebp) faddl -323(%ebp) fxch %st(1) fstl -336(%ebp) fxch %st(2) fstl -328(%ebp) fxch %st(2) faddl -315(%ebp) fxch %st(2) faddl -307(%ebp) fxch %st(1) faddl -348(%ebp) fxch %st(2) faddl -340(%ebp) fxch %st(1) faddl -332(%ebp) fxch %st(2) fstpl (%eax) fstpl 8(%eax) fstpl 16(%eax) leave ret
大量のスタックあとが痛々しいがすばらしいコードだとおもう。
でもこいつを最適化なしでコンパイルすると1000行を超えるリストを吐き出す。もはや、いやがらせ以外の何者でもない。
追記:
上のように関数呼び出しまで値渡しだとまずいですね。
これらのコードはCRTPを使うんだけど必ず1演算につき一回はconst参照を使って実質的な型に変換してやらなければならない。だから値渡しすると、スライシングしてしまう。
ずいぶん昔に書いたコードを書き換えたりするもんだからこういう失敗をするんだ!>俺
id:paserry さんおかげで気がつきました。ありがとうございます。
参考:http://d.hatena.ne.jp/paserry/20041203