{"id":5187,"date":"2017-02-14T18:39:39","date_gmt":"2017-02-14T18:39:39","guid":{"rendered":"https:\/\/www.modernescpp.com\/index.php\/expression-templates\/"},"modified":"2023-06-26T12:22:58","modified_gmt":"2023-06-26T12:22:58","slug":"expression-templates","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/expression-templates\/","title":{"rendered":"Expression Templates"},"content":{"rendered":"

Expression templates are “structures representing a computation at compile-time, which are evaluated only as needed to produce efficient code for the entire computation” (https:\/\/en.wikipedia.org\/wiki\/Expression_templates<\/a>). As needed, now we are at the center of lazy evaluation and the center of this post.<\/p>\n

<\/p>\n

What problem do expression templates solve? Thanks to expression templates, you can eliminate superfluous temporary objects in expressions. What do I mean by superfluous temporary objects? My implementation of the class MyVector.<\/span><\/p>\n

A first naive approach<\/h2>\n

MyVector<\/span> is a simple wrapper for a  std::vector<T>.<\/span> The wrapper has two constructors (lines 12 and 15), knows its length (lines 18 – 20), and supports the reading (lines 23 – 25) and writing (lines 27 – 29) index access.<\/p>\n

 <\/p>\n

<\/p>\n

\n\n\n\n
\n
 1\r\n 2\r\n 3\r\n 4\r\n 5\r\n 6\r\n 7\r\n 8\r\n 9\r\n10\r\n11\r\n12\r\n13\r\n14\r\n15\r\n16\r\n17\r\n18\r\n19\r\n20\r\n21\r\n22\r\n23\r\n24\r\n25\r\n26\r\n27\r\n28\r\n29\r\n30\r\n31\r\n32\r\n33\r\n34\r\n35\r\n36\r\n37\r\n38\r\n39\r\n40\r\n41\r\n42\r\n43\r\n44\r\n45\r\n46\r\n47\r\n48\r\n49\r\n50\r\n51\r\n52\r\n53\r\n54\r\n55\r\n56\r\n57\r\n58\r\n59\r\n60\r\n61\r\n62\r\n63\r\n64\r\n65\r\n66\r\n67\r\n68\r\n69\r\n70\r\n71\r\n72\r\n73\r\n74\r\n75<\/pre>\n<\/td>\n
\n
\/\/ vectorArithmeticOperatorOverloading.cpp<\/span>\r\n\r\n#include <iostream><\/span>\r\n#include <vector><\/span>\r\n\r\ntemplate<\/span><typename<\/span> T>\r\nclass<\/span> MyVector<\/span>{\r\n  std::vector<T> cont;   \r\n\r\npublic:\r\n  \/\/ MyVector with initial size<\/span>\r\n  MyVector(const<\/span> std::size_t<\/span> n) : cont(n){}  \r\n\r\n  \/\/ MyVector with initial size and value<\/span>\r\n  MyVector(const<\/span> std::size_t<\/span> n, const<\/span> double<\/span> initialValue) : cont(n, initialValue){}\r\n  \r\n  \/\/ size of underlying container<\/span>\r\n  std::size_t<\/span> size() const<\/span>{ \r\n    return<\/span> cont.size(); \r\n  }\r\n\r\n  \/\/ index operators<\/span>\r\n  T operator<\/span>[](const<\/span> std::size_t<\/span> i) const<\/span>{ \r\n    return<\/span> cont[i]; \r\n  }\r\n\r\n  T& operator<\/span>[](const<\/span> std::size_t<\/span> i){ \r\n    return<\/span> cont[i]; \r\n  }\r\n\r\n};\r\n\r\n\/\/ function template for the + operator<\/span>\r\ntemplate<\/span><typename<\/span> T> \r\nMyVector<T> operator<\/span>+ (const<\/span> MyVector<T>& a, const<\/span> MyVector<T>& b){\r\n  MyVector<T> result(a.size());\r\n  for<\/span> (std::size_t<\/span> s= 0; s <= a.size(); ++s){\r\n    result[s]= a[s]+b[s];\r\n  }\r\n  return<\/span> result;\r\n}\r\n\r\n\/\/ function template for the * operator<\/span>\r\ntemplate<\/span><typename<\/span> T>\r\nMyVector<T> operator<\/span>* (const<\/span> MyVector<T>& a, const<\/span> MyVector<T>& b){\r\n   MyVector<T> result(a.size());\r\n  for<\/span> (std::size_t<\/span> s= 0; s <= a.size(); ++s){\r\n    result[s]= a[s]*b[s]; \r\n  }\r\n  return<\/span> result;\r\n}\r\n\r\n\/\/ function template for << operator<\/span>\r\ntemplate<\/span><typename<\/span> T>\r\nstd::ostream& operator<\/span><<(std::ostream& os, const<\/span> MyVector<T>& cont){  \r\n  std::cout << std::endl;\r\n  for<\/span> (int<\/span> i=0; i<cont.size(); ++i) {\r\n    os << cont[i] << ' '<\/span>;\r\n  }\r\n  os << std::endl;\r\n  return<\/span> os;\r\n} \r\n\r\nint<\/span> main(){\r\n\r\n  MyVector<double<\/span>> x(10,5.4);\r\n  MyVector<double<\/span>> y(10,10.3);\r\n\r\n  MyVector<double<\/span>> result(10);\r\n  \r\n  result= x+x + y*y;\r\n  \r\n  std::cout << result << std::endl;\r\n  \r\n}\r\n<\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
 <\/p>\n
Thanks to the overloaded + operator (lines 34 – 41), the overloaded  * operator (lines 44 – 51), and the overloaded output operator (lines 54 – 62), the objects x, y<\/span>, and result<\/span> feel like numbers.<\/p>\n
\"vectorArithmeticOperatorOverloading\"<\/p>\n
Why is this implementation naive? The answer is in the expression  result=<\/span> x+x + y*y. <\/span> Three temporary objects are needed to evaluate the expression to hold the result of each arithmetic sub-expression.
<\/span><\/p>\n
 \"Temporaries\"<\/p>\n
How can I get rid of the temporaries? The idea is simple. Instead of performing the vector operations greedy, I lazily create the expression tree for result[i] at compile time.<\/p>\n
Expression templates <\/h2>\n
\"ExpressionTree\"<\/p>\n
There are no temporaries needed for the expression result[i]=<\/span> x[i]+x[i] + y[i]*y[i].  <\/span><\/span>The assignment triggers the evaluation. Sadly, even in this simple usage, the code is not so easy to digest. 
<\/span><\/span><\/p>\n
 <\/p>\n
<\/p>\n
\n\n\n\n
\n
  1\r\n  2\r\n  3\r\n  4\r\n  5\r\n  6\r\n  7\r\n  8\r\n  9\r\n 10\r\n 11\r\n 12\r\n 13\r\n 14\r\n 15\r\n 16\r\n 17\r\n 18\r\n 19\r\n 20\r\n 21\r\n 22\r\n 23\r\n 24\r\n 25\r\n 26\r\n 27\r\n 28\r\n 29\r\n 30\r\n 31\r\n 32\r\n 33\r\n 34\r\n 35\r\n 36\r\n 37\r\n 38\r\n 39\r\n 40\r\n 41\r\n 42\r\n 43\r\n 44\r\n 45\r\n 46\r\n 47\r\n 48\r\n 49\r\n 50\r\n 51\r\n 52\r\n 53\r\n 54\r\n 55\r\n 56\r\n 57\r\n 58\r\n 59\r\n 60\r\n 61\r\n 62\r\n 63\r\n 64\r\n 65\r\n 66\r\n 67\r\n 68\r\n 69\r\n 70\r\n 71\r\n 72\r\n 73\r\n 74\r\n 75\r\n 76\r\n 77\r\n 78\r\n 79\r\n 80\r\n 81\r\n 82\r\n 83\r\n 84\r\n 85\r\n 86\r\n 87\r\n 88\r\n 89\r\n 90\r\n 91\r\n 92\r\n 93\r\n 94\r\n 95\r\n 96\r\n 97\r\n 98\r\n 99\r\n100\r\n101\r\n102\r\n103\r\n104\r\n105\r\n106\r\n107\r\n108\r\n109\r\n110\r\n111\r\n112\r\n113\r\n114\r\n115\r\n116\r\n117\r\n118\r\n119\r\n120\r\n121\r\n122\r\n123\r\n124\r\n125<\/pre>\n<\/td>\n
\n
\/\/ vectorArithmeticExpressionTemplates.cpp<\/span>\r\n\r\n#include <cassert><\/span>\r\n#include <iostream><\/span>\r\n#include <vector><\/span>\r\n\r\ntemplate<\/span><typename<\/span> T, typename<\/span> Cont= std::vector<T> >\r\nclass<\/span> MyVector<\/span>{\r\n  Cont cont;   \r\n\r\npublic:\r\n  \/\/ MyVector with initial size<\/span>\r\n  MyVector(const<\/span> std::size_t<\/span> n) : cont(n){}\r\n\r\n  \/\/ MyVector with initial size and value<\/span>\r\n  MyVector(const<\/span> std::size_t<\/span> n, const<\/span> double<\/span> initialValue) : cont(n, initialValue){}\r\n\r\n  \/\/ Constructor for underlying container<\/span>\r\n  MyVector(const<\/span> Cont& other) : cont(other){}\r\n\r\n  \/\/ assignment operator for MyVector of different type<\/span>\r\n  template<\/span><typename<\/span> T2, typename<\/span> R2>\r\n  MyVector& operator<\/span>=(const<\/span> MyVector<T2, R2>& other){\r\n    assert(size() == other.size());\r\n    for<\/span> (std::size_t<\/span> i = 0; i < cont.size(); ++i) cont[i] = other[i];\r\n    return<\/span> *this<\/span>;\r\n  }\r\n\r\n  \/\/ size of underlying container<\/span>\r\n  std::size_t<\/span> size() const<\/span>{ \r\n    return<\/span> cont.size(); \r\n  }\r\n\r\n  \/\/ index operators<\/span>\r\n  T operator<\/span>[](const<\/span> std::size_t<\/span> i) const<\/span>{ \r\n    return<\/span> cont[i]; \r\n  }\r\n\r\n  T& operator<\/span>[](const<\/span> std::size_t<\/span> i){ \r\n    return<\/span> cont[i]; \r\n  }\r\n\r\n  \/\/ returns the underlying data<\/span>\r\n  const<\/span> Cont& data() const<\/span>{ \r\n    return<\/span> cont; \r\n  }\r\n\r\n  Cont& data(){ \r\n    return<\/span> cont; \r\n  }\r\n};\r\n\r\n\/\/ MyVector + MyVector<\/span>\r\ntemplate<\/span><typename<\/span> T, typename<\/span> Op1 , typename<\/span> Op2>\r\nclass<\/span> MyVectorAdd<\/span>{\r\n  const<\/span> Op1& op1;\r\n  const<\/span> Op2& op2;\r\n\r\npublic:\r\n  MyVectorAdd(const<\/span> Op1& a, const<\/span> Op2& b): op1(a), op2(b){}\r\n\r\n  T operator<\/span>[](const<\/span> std::size_t<\/span> i) const<\/span>{ \r\n    return<\/span> op1[i] + op2[i]; \r\n  }\r\n\r\n  std::size_t<\/span> size() const<\/span>{ \r\n    return<\/span> op1.size(); \r\n  }\r\n};\r\n\r\n\/\/ elementwise MyVector * MyVector<\/span>\r\ntemplate<\/span>< typename<\/span> T, typename<\/span> Op1 , typename<\/span> Op2 >\r\nclass<\/span> MyVectorMul<\/span> {\r\n  const<\/span> Op1& op1;\r\n  const<\/span> Op2& op2;\r\n\r\npublic:\r\n  MyVectorMul(const<\/span> Op1& a, const<\/span> Op2& b ): op1(a), op2(b){}\r\n\r\n  T operator<\/span>[](const<\/span> std::size_t<\/span> i) const<\/span>{ \r\n    return<\/span> op1[i] * op2[i]; \r\n  }\r\n\r\n  std::size_t<\/span> size() const<\/span>{ \r\n    return<\/span> op1.size(); \r\n  }\r\n};\r\n\r\n\/\/ function template for the + operator<\/span>\r\ntemplate<\/span><typename<\/span> T, typename<\/span> R1, typename<\/span> R2>\r\nMyVector<T, MyVectorAdd<T, R1, R2> >\r\noperator<\/span>+ (const<\/span> MyVector<T, R1>& a, const<\/span> MyVector<T, R2>& b){\r\n  return<\/span> MyVector<T, MyVectorAdd<T, R1, R2> >(MyVectorAdd<T, R1, R2 >(a.data(), b.data()));\r\n}\r\n\r\n\/\/ function template for the * operator<\/span>\r\ntemplate<\/span><typename<\/span> T, typename<\/span> R1, typename<\/span> R2>\r\nMyVector<T, MyVectorMul< T, R1, R2> >\r\noperator<\/span>* (const<\/span> MyVector<T, R1>& a, const<\/span> MyVector<T, R2>& b){\r\n   return<\/span> MyVector<T, MyVectorMul<T, R1, R2> >(MyVectorMul<T, R1, R2 >(a.data(), b.data()));\r\n}\r\n\r\n\/\/ function template for < operator<\/span>\r\ntemplate<\/span><typename<\/span> T>\r\nstd::ostream& operator<\/span><<(std::ostream& os, const<\/span> MyVector<T>& cont){  \r\n  std::cout << std::endl;\r\n  for<\/span> (int<\/span> i=0; i<cont.size(); ++i) {\r\n    os << cont[i] << ' '<\/span>;\r\n  }\r\n  os << std::endl;\r\n  return<\/span> os;\r\n} \r\n\r\nint<\/span> main(){\r\n\r\n  MyVector<double<\/span>> x(10,5.4);\r\n  MyVector<double<\/span>> y(10,10.3);\r\n\r\n  MyVector<double<\/span>> result(10);\r\n  \r\n  result= x+x + y*y;\r\n  \r\n  std::cout << result << std::endl;\r\n  \r\n}\r\n<\/pre>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
 <\/p>\n
The key difference between the first naive implementation and this implementation with expression templates is that the overloaded + and + operators return in the case of the expression tree proxy objects. These proxies represent the expression tree (lines 94 and 100). The expression tree is only created but not evaluated. Lazy, of course. The assignment operator (lines 22 – 27) triggers the evaluation of the expression tree that needs no temporaries.<\/p>\n
The result is the same.<\/p>\n
\"vectorArithmeticExpressionTemplates\"<\/p>\n
 <\/p>\n
Suppose you were not able to follow my explanation, no problem. The assembler code of the program vectorArithmeticExpressionTemplates.cpp <\/span>shows the magic.<\/p>\n<\/p>\n
Under the hood<\/h3>\n
Thanks to the compiler explorer on  godbolt.org, <\/a>it’s quite easy to have the assembler instructions.<\/p>\n
 \"godbolt\"<\/p>\n
The expression tree in line 60 is not so beautiful. But with a sharp eye, you can see the structure. For simplicity reasons, I ignored the std::allocator<\/span> in my graphic.<\/p>\n
\"Exression\"<\/p>\n
What’s next?<\/h2>\n
With the next post, I will start the rework of my blog. That means I will rework old posts and write new posts to complete my stories. I  will start in the next post <\/a>with the multithreading features of C++17 and C++20. Here is an overview<\/a> of all my posts.<\/p>\n
 <\/p>\n
 <\/p>\n
 <\/p>\n
 <\/p>\n<\/p>\n
 <\/p>\n
 <\/p>\n
 <\/p>\n
 <\/p>\n
 <\/p>\n
 <\/p>\n
 <\/p>\n
 <\/p>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
Expression templates are “structures representing a computation at compile-time, which are evaluated only as needed to produce efficient code for the entire computation” (https:\/\/en.wikipedia.org\/wiki\/Expression_templates). As needed, now we are at the center of lazy evaluation and the center of this post.<\/p>\n","protected":false},"author":21,"featured_media":5181,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[365],"tags":[424],"class_list":["post-5187","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-functional","tag-expression-templates"],"_links":{"self":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5187","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/users\/21"}],"replies":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/comments?post=5187"}],"version-history":[{"count":1,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5187\/revisions"}],"predecessor-version":[{"id":6887,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/5187\/revisions\/6887"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media\/5181"}],"wp:attachment":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media?parent=5187"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=5187"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=5187"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}