式テンプレートで一時変数を避ける

式テンプレートは通常、線形代数で使用され、「コンパイル時の計算を表す構造体であり、計算全体の効率的なコードを生成するために必要な場合にのみ評価されます」(https://en.wikipedia.org/wiki/Expression_templates )。つまり、式テンプレートは必要な場合にのみ評価されます。

この投稿では、式テンプレートの重要なアイデアのみを提供します。それらを使用するには、次のようなコンテンツをさらに学習する必要があります

  • C++ テンプレート:David Vandervoorde、Nicolai M. Josuttis、Douglas Gregor による完全ガイド (http://www.tmplbook.com/)
  • Boost 基本線形代数ライブラリ (https://www.boost.org/doc/libs/1_59_0/libs/numeric/ublas/doc/index.html)
  • Klaus Iglberger (https://www.youtube.com/watch?v=hfn0BVOegac) による表現テンプレートの再検討。クラウスの講演は、表現テンプレートに関する多くのパフォーマンス関連の誤解を解き明かします。

式テンプレートはどのような問題を解決しますか?式テンプレートのおかげで、式内の余分な一時オブジェクトを取り除くことができます。余分な一時オブジェクトとはどういう意味ですか?クラス MyVector の私の実装。

最初の素朴なアプローチ

MyVector は、std::vector の単純なラッパーです。ラッパーには 2 つのコンストラクターがあり (1 行目と 2 行目)、その長さを認識し (3 行目)、インデックスによる読み取り (4 行目) と書き込み (4 行目) をサポートします。

// vectorArithmeticOperatorOverloading.cpp

#include <iostream>
#include <vector>

template<typename T>
class MyVector{
 std::vector<T> cont; 

public:
 // MyVector with initial size
 MyVector(const std::size_t n) : cont(n){}  // (1)

 // MyVector with initial size and value
 MyVector(const std::size_t n, const double initialValue) : cont(n, initialValue){}  // (2)
 
 // size of underlying container
 std::size_t size() const{  // (3)
 return cont.size(); 
 }

 // index operators
 T operator[](const std::size_t i) const{  // (4)
 return cont[i]; 
 }

 T& operator[](const std::size_t i){  // (5)
 return cont[i]; 
 }

};

// function template for the + operator
template<typename T> 
MyVector<T> operator+ (const MyVector<T>& a, const MyVector<T>& b){  // (6)
 MyVector<T> result(a.size());
 for (std::size_t s = 0; s <= a.size(); ++s){
 result[s] = a[s] + b[s];
 }
 return result;
}

// function template for the * operator
template<typename T>
MyVector<T> operator* (const MyVector<T>& a, const MyVector<T>& b){ // (7)
 MyVector<T> result(a.size());
 for (std::size_t s = 0; s <= a.size(); ++s){
 result[s] = a[s] * b[s]; 
 }
 return result;
}

// function template for << operator
template<typename T>
std::ostream& operator<<(std::ostream& os, const MyVector<T>& cont){ // (8)
 std::cout << '\n';
 for (int i = 0; i < cont.size(); ++i) {
 os << cont[i] << ' ';
 }
 os << '\n';
 return os;
} 

int main(){

 MyVector<double> x(10, 5.4);
 MyVector<double> y(10, 10.3);

 MyVector<double> result(10);
 
 result = x + x + y * y;
 
 std::cout << result << '\n';
 
}

オーバーロードされた + 演算子 (6 行目)、オーバーロードされた * 演算子 (7 行目)、およびオーバーロードされた出力演算子 (8 行目) のおかげで、オブジェクト x、y、および結果は数値のように動作します。

なぜこの実装は素朴なのですか?答えは、result =x + x + y * y という式にあります。式を評価するには、各算術式の結果を保持するために 3 つの一時オブジェクトが必要です。

どうすれば一時的なものを取り除くことができますか?考え方は単純です。ベクトル演算を貪欲に実行する代わりに、コンパイル時に result[i] の式ツリーを遅延して作成します。遅延評価とは、式が必要な場合にのみ評価されることを意味します。

式テンプレート

式 result[i] =x[i] + x[i] + y[i] * y[i] の一時的な必要はありません。割り当てによって評価がトリガーされます。悲しいことに、コードはこの単純な使い方であっても、消化するのは簡単ではありません。

// vectorArithmeticExpressionTemplates.cpp

#include <cassert>
#include <iostream>
#include <vector>

template<typename T, typename Cont= std::vector<T> >
class MyVector{
 Cont cont; 

public:
 // MyVector with initial size
 MyVector(const std::size_t n) : cont(n){}

 // MyVector with initial size and value
 MyVector(const std::size_t n, const double initialValue) : cont(n, initialValue){}

 // Constructor for underlying container
 MyVector(const Cont& other) : cont(other){}

 // assignment operator for MyVector of different type
 template<typename T2, typename R2> // (3)
 MyVector& operator=(const MyVector<T2, R2>& other){
 assert(size() == other.size());
 for (std::size_t i = 0; i < cont.size(); ++i) cont[i] = other[i];
 return *this;
 }

 // size of underlying container
 std::size_t size() const{ 
 return cont.size(); 
 }

 // index operators
 T operator[](const std::size_t i) const{ 
 return cont[i]; 
 }

 T& operator[](const std::size_t i){ 
 return cont[i]; 
 }

 // returns the underlying data
 const Cont& data() const{ 
 return cont; 
 }

 Cont& data(){ 
 return cont; 
 }
};

// MyVector + MyVector
template<typename T, typename Op1 , typename Op2>
class MyVectorAdd{
 const Op1& op1;
 const Op2& op2;

public:
 MyVectorAdd(const Op1& a, const Op2& b): op1(a), op2(b){}

 T operator[](const std::size_t i) const{ 
 return op1[i] + op2[i]; 
 }

 std::size_t size() const{ 
 return op1.size(); 
 }
};

// elementwise MyVector * MyVector
template< typename T, typename Op1 , typename Op2 >
class MyVectorMul {
 const Op1& op1;
 const Op2& op2;

public:
 MyVectorMul(const Op1& a, const Op2& b ): op1(a), op2(b){}

 T operator[](const std::size_t i) const{ 
 return op1[i] * op2[i]; 
 }

 std::size_t size() const{ 
 return op1.size(); 
 }
};

// function template for the + operator
template<typename T, typename R1, typename R2>
MyVector<T, MyVectorAdd<T, R1, R2> >
operator+ (const MyVector<T, R1>& a, const MyVector<T, R2>& b){
 return MyVector<T, MyVectorAdd<T, R1, R2> >(MyVectorAdd<T, R1, R2 >(a.data(), b.data())); // (1)
}

// function template for the * operator
template<typename T, typename R1, typename R2>
MyVector<T, MyVectorMul< T, R1, R2> >
operator* (const MyVector<T, R1>& a, const MyVector<T, R2>& b){
 return MyVector<T, MyVectorMul<T, R1, R2> >(MyVectorMul<T, R1, R2 >(a.data(), b.data())); // (2)
}

// function template for < operator
template<typename T>
std::ostream& operator<<(std::ostream& os, const MyVector<T>& cont){ 
 std::cout << '\n';
 for (int i = 0; i < cont.size(); ++i) {
 os << cont[i] << ' ';
 }
 os << '\n';
 return os;
} 

int main(){

 MyVector<double> x(10,5.4);
 MyVector<double> y(10,10.3);

 MyVector<double> result(10);
 
 result= x + x + y * y; 
 
 std::cout << result << '\n';
 
}

最初の単純な実装と式テンプレートを使用したこの実装の主な違いは、式ツリー プロキシ オブジェクトの場合、オーバーロードされた + 演算子と + 演算子が返されることです。これらのプロキシは式ツリーを表します (1 行目と 2 行目)。式ツリーは作成されるだけで評価されません。もちろん、怠け者です。代入演算子 (3 行目) は、一時変数を必要としない式ツリーの評価をトリガーします。

結果は同じです。

コンパイラ エクスプローラのおかげで、プログラム vectorArithmeticExpressionTemplates.cpp の魔法を視覚化できます。

ボンネットの下

main 関数での最終代入に必要なアセンブラー命令は次のとおりです:result= x + x + y * y .

アセンブラ スニペットの式ツリー ロックはかなり怖いですが、鋭い目で構造を確認できます。簡単にするために、図では std::allocator を無視しました。

次は?

ポリシーは、動作を構成できる汎用関数またはクラスです。次回の投稿で紹介させてください。