Expression templatesのダングリング対策について¶
本記事では、expression templatesの概要を述べ、欠点の一つであるダングリングする可能性に対処する方法を示します。
Expression templatesとは¶
数値線形代数で最初に使われた手法で、構文木をテンプレートを使って擬似的に作ります。 利点は、一時変数の作成コストを削減できる点です。
例えば、3次元ベクトルa, b, cに対して、
を計算しようとすると、まずtmp = a + bが計算され、次にsum = tmp + cが計算されるでしょう。
Expression templatesでは、この計算を
のように一括で行うことで一時変数を作らなくて済むようにします1。 実際に、Eigenで使われています。
欠点は、コンパイル時のエラーメッセージが表現が複雑になるほど読みにくくなることとダングリングする可能性があることです。
Expression templatesの実装例¶
Expression templatesの実装例として、実際に私が書いたコードの一部を抜粋し、改変しました。
template <class L, class Op, class R>
class BinaryExpr final {
public:
static_assert(std::is_same_v<typename L::Domain, typename R::Domain>, "Domain mismatch!");
static_assert(std::is_same_v<typename L::Range, typename R::Range>, "Range mismatch!");
using Domain = typename L::Domain;
using Range = typename L::Range;
BinaryExpr() = delete;
BinaryExpr(const BinaryExpr&) = default;
BinaryExpr(BinaryExpr&&) = default;
BinaryExpr& operator=(const BinaryExpr&) = default;
BinaryExpr& operator=(BinaryExpr&&) = default;
~BinaryExpr() = default;
BinaryExpr(const L& l, const R& r) : l_(l), r_(r) {}
// Calculate x of this
Range operator()(const Domain& x) const { return Op::Apply(l_(x), r_(x)); }
const auto& read_l() const { return l_; }
const auto& read_r() const { return r_; }
private:
const L& l_;
const R& r_;
};
struct Plus final {
template <class R>
requires(!std::is_floating_point_v<R>)
static R Apply(R&& l, R&& r) {
return std::forward<R>(l) + std::forward<R>(r);
}
template <class R>
requires std::is_floating_point_v<R>
static R Apply(R l, R r) {
return l + r;
}
};
struct Multiply final {
template <class R>
requires(!std::is_floating_point_v<R>)
static R Apply(R&& l, R&& r) {
return std::forward<R>(l) * std::forward<R>(r);
}
template <class R>
requires std::is_floating_point_v<R>
static R Apply(R l, R r) {
return l * r;
}
};
BinaryExprのテンプレート引数Opは二項演算を表し、PlusやMultiplyが代入されることを想定しています。
LとRは関数オブジェクトを想定しています。
そして、operator()で受け取った引数xをlとrに渡して、Op::Apply関数が呼び出し、計算結果が返されます。
ついでに、関数クラスも作りましょう。
class F {
public:
using Domain = double;
using Range = double;
template <class T>
F(T&& f) : f_(f) {}
double operator()(double x) const {
return f_(x);
}
private:
std::function<double(double)> f_;
};
この実装例は大体うまく行きます。
lまたはrが一時オブジェクトじゃなければ。
ダングリングへの対処法¶
C++では、「一時オブジェクトtmpをconst&の変数xに代入すると、tmpの寿命がxの寿命に延長される」という仕様があります。
しかし、このxを別のconst&の変数yに代入しても、tmpの寿命はxの寿命と同じままです2。
そのため、以下のようなコードはダングリングポインタを発生させます。
では、どうするか？
私が考えた対処法は演算対象の型(LとR)のラッパークラスを作成し、演算対象の型がconst&があるか&&があるかによって、ラッパークラスの実装を切り変えるという方法です。
具体的には、以下の型を作ります。
template <class T>
constexpr bool is_const_v = std::is_const_v<std::remove_reference_t<T>>;
template <class T>
constexpr bool is_const_ref_v = is_const_v<T> && std::is_lvalue_reference_v<T>;
template <class T>
constexpr bool is_rvalue_v = std::is_rvalue_reference_v<T> && (!is_const_v<T>);
template <class T>
constexpr bool is_cref_or_rvalue_v = is_const_ref_v<T> || is_rvalue_v<T>;
template <class T>
struct FilterRvalue;
template <class T>
struct FilterRvalue<T&&> {
using type = T;
static constexpr bool is_rvalue = true;
};
template <class T>
struct FilterRvalue<const T&> {
using type = const T&;
static constexpr bool is_rvalue = false;
};
template <class T_>
requires is_cref_or_rvalue_v<T_>
class RefWrapper final {
using FilterResult = FilterRvalue<T_>;
public:
using T = std::remove_cvref_t<T_>;
using Domain = typename T::Domain;
using Range = typename T::Range;
using Storage = FilterResult::type;
static constexpr bool is_rvalue = FilterResult::is_rvalue;
RefWrapper() = delete;
RefWrapper(const RefWrapper&) = default;
RefWrapper(RefWrapper&&) = default;
RefWrapper& operator=(const RefWrapper&) = default;
RefWrapper& operator=(RefWrapper&&) = default;
~RefWrapper() = default;
RefWrapper(T_&& t) : t_(std::forward<T_>(t)) {}
Range operator()(const Domain& x) const { return t_(x); }
const Storage& read() const
requires(!is_rvalue)
{
return t_;
}
const Storage& read() const
requires(is_rvalue)
{
return t_;
}
const Storage& move() &&
requires(!is_rvalue)
{
return t_;
}
Storage move() &&
requires(is_rvalue)
{
return std::move(t_);
}
private:
Storage t_;
};
大まかに解説すると、const&と&&を判別するコンパイル時定数を作成し、const&ならそのまま、&&ならムーブして値を保持するクラスがRefWrapperです。
値をムーブできるようにmoveメンバ関数を用意しています。
これを先ほどのBinaryExprに組み込むと以下のようになります:
| src/expr_template/example.cpp | |
|---|---|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 | |
実行結果はこちら。
課題¶
ダングリングの問題は対処できました。 では、拡張性についてはどうでしょうか？
例えば、微分したいとしましょう。 数学を学んだ者の端くれとしては関数として実装したい所です。 すると、以下の場合分けが発生します:
BinaryExprが右辺値かどうかLが右辺値かどうかRが右辺値かどうかOpの種類
実際は、BinaryExprがconst&ならば、2と3の場合分けは無視できますし、対称性を使えばコード量は減るでしょう。
それでも、8種類の部分特殊化とFへの微分の実装が必要になってしまいます。
残念ながら、関数として実装するのは大変です。
メンバ関数として実装するのが良いのかもしれませんが、試せてません。
(Eigenの実装を考えるとそう思えますが)
まとめ¶
Expression templatesの概要を述べ、欠点の一つであるダングリングする可能性に対処する方法を示しました。 私の方法では、Expression templatesを受け取る関数を実装するのは大変なので、設計段階でどんなメンバ関数が必要かあらかじめ決めておくと良いのかもしれません。