{"id":6319,"date":"2022-03-08T07:06:21","date_gmt":"2022-03-08T07:06:21","guid":{"rendered":"https:\/\/www.modernescpp.com\/index.php\/avoiding-temporaries-with-expression-templates\/"},"modified":"2023-06-26T09:11:32","modified_gmt":"2023-06-26T09:11:32","slug":"avoiding-temporaries-with-expression-templates","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/avoiding-temporaries-with-expression-templates\/","title":{"rendered":"Avoiding Temporaries with Expression Templates"},"content":{"rendered":"<p>Expression templates are typically used in linear algebra and are&nbsp; &#8220;structures representing a computation at compile-time, which are evaluated only as needed to produce efficient code for the entire computation&#8221; (<a href=\"https:\/\/en.wikipedia.org\/wiki\/Expression_templates\">https:\/\/en.wikipedia.org\/wiki\/Expression_templates<\/a>). In other words, expression templates are only evaluated when needed.&nbsp;<\/p>\n<p><!--more--><\/p>\n<p>&nbsp;<img loading=\"lazy\" decoding=\"async\" class=\" size-full wp-image-6318\" src=\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2022\/03\/ExpressionTemplates.jpg\" alt=\"ExpressionTemplates\" width=\"650\" height=\"403\" style=\"display: block; margin-left: auto; margin-right: auto;\" srcset=\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2022\/03\/ExpressionTemplates.jpg 913w, https:\/\/www.modernescpp.com\/wp-content\/uploads\/2022\/03\/ExpressionTemplates-300x186.jpg 300w, https:\/\/www.modernescpp.com\/wp-content\/uploads\/2022\/03\/ExpressionTemplates-768x476.jpg 768w\" sizes=\"auto, (max-width: 650px) 100vw, 650px\" \/><\/p>\n<p>I provide you with this post only the critical ideas of expression templates. To use them, you should study further content, such as<\/p>\n<ul>\n<li>C++ Templates: The Complete Guide by David Vandervoorde, Nicolai M. Josuttis, and Douglas Gregor (<a href=\"http:\/\/www.tmplbook.com\/\">http:\/\/www.tmplbook.com\/<\/a>)<\/li>\n<li>Boost Basic Linear Algebra Library (<a href=\"https:\/\/www.boost.org\/doc\/libs\/1_59_0\/libs\/numeric\/ublas\/doc\/index.html\">https:\/\/www.boost.org\/doc\/libs\/1_59_0\/libs\/numeric\/ublas\/doc\/index.html<\/a>)<\/li>\n<li>Expression Templates Revisited by Klaus Iglberger (<a href=\"https:\/\/www.youtube.com\/watch?v=hfn0BVOegac\">https:\/\/www.youtube.com\/watch?v=hfn0BVOegac<\/a>). Klaus&#8217;s talk demystifies many performance-related myths about expression templates.<\/li>\n<\/ul>\n<p>What problem do expression templates solve? Thanks to expression templates, you can get rid of superfluous temporary objects in expressions. What do I mean by superfluous temporary objects? My implementation of the class <span style=\"font-family: courier new,courier;\">MyVector.<\/span><\/p>\n<h2>A first naive Approach<\/h2>\n<p><span style=\"font-family: courier new,courier;\">MyVector<\/span> is a simple wrapper for a&nbsp; <span style=\"font-family: courier new,courier;\">std::vector&lt;T&gt;.<\/span> The wrapper has two constructors (lines 1 and 2), knows its length (line 3), and supports the reading (line 4) and writing (line 4) by index.<\/p>\n<p>&nbsp;<\/p>\n<p><!-- HTML generated using hilite.me --><\/p>\n<div style=\"background: #f0f3f3; overflow: auto; width: auto; gray;border-width: .1em .1em .1em .8em;\">\n<pre style=\"margin: 0px; line-height: 125%;\"><span style=\"color: #0099ff; font-style: italic;\">\/\/ vectorArithmeticOperatorOverloading.cpp<\/span>\r\n\r\n<span style=\"color: #009999;\">#include &lt;iostream&gt;<\/span>\r\n<span style=\"color: #009999;\">#include &lt;vector&gt;<\/span>\r\n\r\n<span style=\"color: #006699; font-weight: bold;\">template<\/span><span style=\"color: #555555;\">&lt;<\/span><span style=\"color: #006699; font-weight: bold;\">typename<\/span> T<span style=\"color: #555555;\">&gt;<\/span>\r\n<span style=\"color: #006699; font-weight: bold;\">class<\/span> <span style=\"color: #00aa88; font-weight: bold;\">MyVector<\/span>{\r\n  std<span style=\"color: #555555;\">::<\/span>vector<span style=\"color: #555555;\">&lt;<\/span>T<span style=\"color: #555555;\">&gt;<\/span> cont;   \r\n\r\n<span style=\"color: #9999ff;\">public:<\/span>\r\n  <span style=\"color: #0099ff; font-style: italic;\">\/\/ MyVector with initial size<\/span>\r\n  MyVector(<span style=\"color: #006699; font-weight: bold;\">const<\/span> std<span style=\"color: #555555;\">::<\/span><span style=\"color: #007788; font-weight: bold;\">size_t<\/span> n) <span style=\"color: #555555;\">:<\/span> cont(n){}                                          <em><span style=\"color: #0099ff;\"> \/\/ (1)<\/span><\/em>\r\n\r\n  <span style=\"color: #0099ff; font-style: italic;\">\/\/ MyVector with initial size and value<\/span>\r\n  MyVector(<span style=\"color: #006699; font-weight: bold;\">const<\/span> std<span style=\"color: #555555;\">::<\/span><span style=\"color: #007788; font-weight: bold;\">size_t<\/span> n, <span style=\"color: #006699; font-weight: bold;\">const<\/span> <span style=\"color: #007788; font-weight: bold;\">double<\/span> initialValue) <span style=\"color: #555555;\">:<\/span> cont(n, initialValue){} <em><span style=\"color: #0099ff;\"> \/\/ (2)<\/span><\/em>\r\n  \r\n  <span style=\"color: #0099ff; font-style: italic;\">\/\/ size of underlying container<\/span>\r\n  std<span style=\"color: #555555;\">::<\/span><span style=\"color: #007788; font-weight: bold;\">size_t<\/span> size() <span style=\"color: #006699; font-weight: bold;\">const<\/span>{                                                          <em><span style=\"color: #0099ff;\"> \/\/ (3)<\/span><\/em>\r\n    <span style=\"color: #006699; font-weight: bold;\">return<\/span> cont.size(); \r\n  }\r\n\r\n  <span style=\"color: #0099ff; font-style: italic;\">\/\/ index operators<\/span>\r\n  T <span style=\"color: #006699; font-weight: bold;\">operator<\/span>[](<span style=\"color: #006699; font-weight: bold;\">const<\/span> std<span style=\"color: #555555;\">::<\/span><span style=\"color: #007788; font-weight: bold;\">size_t<\/span> i) <span style=\"color: #006699; font-weight: bold;\">const<\/span>{                                           <em><span style=\"color: #0099ff;\"> \/\/ (4)<\/span><\/em>\r\n    <span style=\"color: #006699; font-weight: bold;\">return<\/span> cont[i]; \r\n  }\r\n\r\n  T<span style=\"color: #555555;\">&amp;<\/span> <span style=\"color: #006699; font-weight: bold;\">operator<\/span>[](<span style=\"color: #006699; font-weight: bold;\">const<\/span> std<span style=\"color: #555555;\">::<\/span><span style=\"color: #007788; font-weight: bold;\">size_t<\/span> i){                                                <span style=\"color: #0099ff;\"><em> \/\/ (5)<\/em><\/span>\r\n    <span style=\"color: #006699; font-weight: bold;\">return<\/span> cont[i]; \r\n  }\r\n\r\n};\r\n\r\n<span style=\"color: #0099ff; font-style: italic;\">\/\/ function template for the + operator<\/span>\r\n<span style=\"color: #006699; font-weight: bold;\">template<\/span><span style=\"color: #555555;\">&lt;<\/span><span style=\"color: #006699; font-weight: bold;\">typename<\/span> T<span style=\"color: #555555;\">&gt;<\/span> \r\nMyVector<span style=\"color: #555555;\">&lt;<\/span>T<span style=\"color: #555555;\">&gt;<\/span> <span style=\"color: #006699; font-weight: bold;\">operator<\/span><span style=\"color: #555555;\">+<\/span> (<span style=\"color: #006699; font-weight: bold;\">const<\/span> MyVector<span style=\"color: #555555;\">&lt;<\/span>T<span style=\"color: #555555;\">&gt;&amp;<\/span> a, <span style=\"color: #006699; font-weight: bold;\">const<\/span> MyVector<span style=\"color: #555555;\">&lt;<\/span>T<span style=\"color: #555555;\">&gt;&amp;<\/span> b){                  <em><span style=\"color: #0099ff;\"> \/\/ (6)<\/span><\/em>\r\n  MyVector<span style=\"color: #555555;\">&lt;<\/span>T<span style=\"color: #555555;\">&gt;<\/span> result(a.size());\r\n  <span style=\"color: #006699; font-weight: bold;\">for<\/span> (std<span style=\"color: #555555;\">::<\/span><span style=\"color: #007788; font-weight: bold;\">size_t<\/span> s <span style=\"color: #555555;\">=<\/span> <span style=\"color: #ff6600;\">0<\/span>; s <span style=\"color: #555555;\">&lt;=<\/span> a.size(); <span style=\"color: #555555;\">++<\/span>s){\r\n    result[s] <span style=\"color: #555555;\">=<\/span> a[s] <span style=\"color: #555555;\">+<\/span> b[s];\r\n  }\r\n  <span style=\"color: #006699; font-weight: bold;\">return<\/span> result;\r\n}\r\n\r\n<span style=\"color: #0099ff; font-style: italic;\">\/\/ function template for the * operator<\/span>\r\n<span style=\"color: #006699; font-weight: bold;\">template<\/span><span style=\"color: #555555;\">&lt;<\/span><span style=\"color: #006699; font-weight: bold;\">typename<\/span> T<span style=\"color: #555555;\">&gt;<\/span>\r\nMyVector<span style=\"color: #555555;\">&lt;<\/span>T<span style=\"color: #555555;\">&gt;<\/span> <span style=\"color: #006699; font-weight: bold;\">operator<\/span><span style=\"color: #555555;\">*<\/span> (<span style=\"color: #006699; font-weight: bold;\">const<\/span> MyVector<span style=\"color: #555555;\">&lt;<\/span>T<span style=\"color: #555555;\">&gt;&amp;<\/span> a, <span style=\"color: #006699; font-weight: bold;\">const<\/span> MyVector<span style=\"color: #555555;\">&lt;<\/span>T<span style=\"color: #555555;\">&gt;&amp;<\/span> b){                  <em><span style=\"color: #0099ff;\">\/\/ (7)<\/span><\/em>\r\n   MyVector<span style=\"color: #555555;\">&lt;<\/span>T<span style=\"color: #555555;\">&gt;<\/span> result(a.size());\r\n  <span style=\"color: #006699; font-weight: bold;\">for<\/span> (std<span style=\"color: #555555;\">::<\/span><span style=\"color: #007788; font-weight: bold;\">size_t<\/span> s <span style=\"color: #555555;\">=<\/span> <span style=\"color: #ff6600;\">0<\/span>; s <span style=\"color: #555555;\">&lt;=<\/span> a.size(); <span style=\"color: #555555;\">++<\/span>s){\r\n    result[s] <span style=\"color: #555555;\">=<\/span> a[s] <span style=\"color: #555555;\">*<\/span> b[s]; \r\n  }\r\n  <span style=\"color: #006699; font-weight: bold;\">return<\/span> result;\r\n}\r\n\r\n<span style=\"color: #0099ff; font-style: italic;\">\/\/ function template for &lt;&lt; operator<\/span>\r\n<span style=\"color: #006699; font-weight: bold;\">template<\/span><span style=\"color: #555555;\">&lt;<\/span><span style=\"color: #006699; font-weight: bold;\">typename<\/span> T<span style=\"color: #555555;\">&gt;<\/span>\r\nstd<span style=\"color: #555555;\">::<\/span>ostream<span style=\"color: #555555;\">&amp;<\/span> <span style=\"color: #006699; font-weight: bold;\">operator<\/span><span style=\"color: #555555;\">&lt;&lt;<\/span>(std<span style=\"color: #555555;\">::<\/span>ostream<span style=\"color: #555555;\">&amp;<\/span> os, <span style=\"color: #006699; font-weight: bold;\">const<\/span> MyVector<span style=\"color: #555555;\">&lt;<\/span>T<span style=\"color: #555555;\">&gt;&amp;<\/span> cont){                 <em><span style=\"color: #0099ff;\">\/\/ (8)<\/span><\/em>\r\n  std<span style=\"color: #555555;\">::<\/span>cout <span style=\"color: #555555;\">&lt;&lt;<\/span> <span style=\"color: #cc3300;\">'\\n'<\/span>;\r\n  <span style=\"color: #006699; font-weight: bold;\">for<\/span> (<span style=\"color: #007788; font-weight: bold;\">int<\/span> i <span style=\"color: #555555;\">= <\/span><span style=\"color: #ff6600;\">0<\/span>; i <span style=\"color: #555555;\">&lt;<\/span> cont.size(); <span style=\"color: #555555;\">++<\/span>i) {\r\n    os <span style=\"color: #555555;\">&lt;&lt;<\/span> cont[i] <span style=\"color: #555555;\">&lt;&lt;<\/span> <span style=\"color: #cc3300;\">' '<\/span>;\r\n  }\r\n  os <span style=\"color: #555555;\">&lt;&lt;<\/span> <span style=\"color: #cc3300;\">'\\n'<\/span>;\r\n  <span style=\"color: #006699; font-weight: bold;\">return<\/span> os;\r\n} \r\n\r\n<span style=\"color: #007788; font-weight: bold;\">int<\/span> main(){\r\n\r\n  MyVector<span style=\"color: #555555;\">&lt;<\/span><span style=\"color: #007788; font-weight: bold;\">double<\/span><span style=\"color: #555555;\">&gt;<\/span> x(<span style=\"color: #ff6600;\">10<\/span>, <span style=\"color: #ff6600;\">5.4<\/span>);\r\n  MyVector<span style=\"color: #555555;\">&lt;<\/span><span style=\"color: #007788; font-weight: bold;\">double<\/span><span style=\"color: #555555;\">&gt;<\/span> y(<span style=\"color: #ff6600;\">10<\/span>, <span style=\"color: #ff6600;\">10.3<\/span>);\r\n\r\n  MyVector<span style=\"color: #555555;\">&lt;<\/span><span style=\"color: #007788; font-weight: bold;\">double<\/span><span style=\"color: #555555;\">&gt;<\/span> result(<span style=\"color: #ff6600;\">10<\/span>);\r\n  \r\n  result <span style=\"color: #555555;\">=<\/span> x <span style=\"color: #555555;\">+<\/span> x <span style=\"color: #555555;\">+<\/span> y <span style=\"color: #555555;\">*<\/span> y;\r\n  \r\n  std<span style=\"color: #555555;\">::<\/span>cout <span style=\"color: #555555;\">&lt;&lt;<\/span> result <span style=\"color: #555555;\">&lt;&lt;<\/span> <span style=\"color: #cc3300;\">'\\n'<\/span>;\r\n  \r\n}\r\n<\/pre>\n<\/div>\n<p>&nbsp;<\/p>\n<p>Thanks to the overloaded + operator (line 6), the overloaded&nbsp; * operator (line 7), and the overloaded output operator (line 8) the objects <span style=\"font-family: courier new,courier;\">x, y,<\/span> and <span style=\"font-family: courier new,courier;\">result<\/span> behave like numbers.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\" size-full wp-image-5181\" src=\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2017\/02\/vectorArithmeticOperatorOverloading.png\" alt=\"vectorArithmeticOperatorOverloading\" width=\"600\" height=\"175\" style=\"display: block; margin-left: auto; margin-right: auto;\" \/><\/p>\n<p>Why is this implementation naive? The answer is in the expression <span style=\"font-family: courier new,courier;\">result =<\/span> <span style=\"font-family: courier new,courier;\">x + x + y * y.&nbsp;<\/span> To evaluate the expression, three temporary objects are needed to hold the result of each arithmetic expression.<span style=\"font-family: courier new,courier;\"><br \/><\/span><\/p>\n<p>&nbsp;<img loading=\"lazy\" decoding=\"async\" class=\" size-full wp-image-5182\" src=\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2017\/02\/Temporaries.png\" alt=\"Temporaries\" width=\"400\" height=\"263\" style=\"margin: 15px auto; display: block;\" srcset=\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2017\/02\/Temporaries.png 487w, https:\/\/www.modernescpp.com\/wp-content\/uploads\/2017\/02\/Temporaries-300x197.png 300w\" sizes=\"auto, (max-width: 400px) 100vw, 400px\" \/><\/p>\n<p>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<code> result[i]<\/code> at compile time. Lazy evaluation means that an expression is only evaluated when needed.&nbsp;<\/p>\n<\/p>\n<h2>Expression templates&nbsp;<\/h2>\n<p><img loading=\"lazy\" decoding=\"async\" class=\" size-full wp-image-5183\" src=\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2017\/02\/ExpressionTree.png\" alt=\"ExpressionTree\" width=\"400\" height=\"207\" style=\"margin: 15px auto; display: block;\" srcset=\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2017\/02\/ExpressionTree.png 780w, https:\/\/www.modernescpp.com\/wp-content\/uploads\/2017\/02\/ExpressionTree-300x155.png 300w, https:\/\/www.modernescpp.com\/wp-content\/uploads\/2017\/02\/ExpressionTree-768x396.png 768w\" sizes=\"auto, (max-width: 400px) 100vw, 400px\" \/><\/p>\n<p>There are no temporaries needed for the expression <span style=\"font-family: courier new,courier;\">result[i] =<\/span>&nbsp; <span style=\"font-family: courier new,courier;\">x[i] + x[i] + y[i] * y[i]<span style=\"font-family: arial,helvetica,sans-serif;\">.&nbsp; <\/span><\/span>The assignment triggers the evaluation. Sadly, the code is, even in this simple usage, not so easy to digest. <span style=\"font-family: courier new,courier;\"><span style=\"font-family: arial,helvetica,sans-serif;\"><br \/><\/span><\/span><\/p>\n<p>&nbsp;<\/p>\n<p><!-- HTML generated using hilite.me --><\/p>\n<div style=\"background: #f0f3f3; overflow: auto; width: auto; gray;border-width: .1em .1em .1em .8em;\">\n<pre style=\"margin: 0px; line-height: 125%;\"><span style=\"color: #0099ff; font-style: italic;\">\/\/ vectorArithmeticExpressionTemplates.cpp<\/span>\r\n\r\n<span style=\"color: #009999;\">#include &lt;cassert&gt;<\/span>\r\n<span style=\"color: #009999;\">#include &lt;iostream&gt;<\/span>\r\n<span style=\"color: #009999;\">#include &lt;vector&gt;<\/span>\r\n\r\n<span style=\"color: #006699; font-weight: bold;\">template<\/span><span style=\"color: #555555;\">&lt;<\/span><span style=\"color: #006699; font-weight: bold;\">typename<\/span> T, <span style=\"color: #006699; font-weight: bold;\">typename<\/span> Cont<span style=\"color: #555555;\">=<\/span> std<span style=\"color: #555555;\">::<\/span>vector<span style=\"color: #555555;\">&lt;<\/span>T<span style=\"color: #555555;\">&gt;<\/span> <span style=\"color: #555555;\">&gt;<\/span>\r\n<span style=\"color: #006699; font-weight: bold;\">class<\/span> <span style=\"color: #00aa88; font-weight: bold;\">MyVector<\/span>{\r\n  Cont cont;   \r\n\r\n<span style=\"color: #9999ff;\">public:<\/span>\r\n  <span style=\"color: #0099ff; font-style: italic;\">\/\/ MyVector with initial size<\/span>\r\n  MyVector(<span style=\"color: #006699; font-weight: bold;\">const<\/span> std<span style=\"color: #555555;\">::<\/span><span style=\"color: #007788; font-weight: bold;\">size_t<\/span> n) <span style=\"color: #555555;\">:<\/span> cont(n){}\r\n\r\n  <span style=\"color: #0099ff; font-style: italic;\">\/\/ MyVector with initial size and value<\/span>\r\n  MyVector(<span style=\"color: #006699; font-weight: bold;\">const<\/span> std<span style=\"color: #555555;\">::<\/span><span style=\"color: #007788; font-weight: bold;\">size_t<\/span> n, <span style=\"color: #006699; font-weight: bold;\">const<\/span> <span style=\"color: #007788; font-weight: bold;\">double<\/span> initialValue) <span style=\"color: #555555;\">:<\/span> cont(n, initialValue){}\r\n\r\n  <span style=\"color: #0099ff; font-style: italic;\">\/\/ Constructor for underlying container<\/span>\r\n  MyVector(<span style=\"color: #006699; font-weight: bold;\">const<\/span> Cont<span style=\"color: #555555;\">&amp;<\/span> other) <span style=\"color: #555555;\">:<\/span> cont(other){}\r\n\r\n  <span style=\"color: #0099ff; font-style: italic;\">\/\/ assignment operator for MyVector of different type<\/span>\r\n  <span style=\"color: #006699; font-weight: bold;\">template<\/span><span style=\"color: #555555;\">&lt;<\/span><span style=\"color: #006699; font-weight: bold;\">typename<\/span> T2, <span style=\"color: #006699; font-weight: bold;\">typename<\/span> R2<span style=\"color: #555555;\">&gt;                                      <span style=\"color: #0099ff; font-style: italic;\">\/\/ (3)<\/span><\/span>\r\n  MyVector<span style=\"color: #555555;\">&amp;<\/span> <span style=\"color: #006699; font-weight: bold;\">operator<\/span><span style=\"color: #555555;\">=<\/span>(<span style=\"color: #006699; font-weight: bold;\">const<\/span> MyVector<span style=\"color: #555555;\">&lt;<\/span>T2, R2<span style=\"color: #555555;\">&gt;&amp;<\/span> other){\r\n    assert(size() <span style=\"color: #555555;\">==<\/span> other.size());\r\n    <span style=\"color: #006699; font-weight: bold;\">for<\/span> (std<span style=\"color: #555555;\">::<\/span><span style=\"color: #007788; font-weight: bold;\">size_t<\/span> i <span style=\"color: #555555;\">=<\/span> <span style=\"color: #ff6600;\">0<\/span>; i <span style=\"color: #555555;\">&lt;<\/span> cont.size(); <span style=\"color: #555555;\">++<\/span>i) cont[i] <span style=\"color: #555555;\">=<\/span> other[i];\r\n    <span style=\"color: #006699; font-weight: bold;\">return<\/span> <span style=\"color: #555555;\">*<\/span><span style=\"color: #006699; font-weight: bold;\">this<\/span>;\r\n  }\r\n\r\n  <span style=\"color: #0099ff; font-style: italic;\">\/\/ size of underlying container<\/span>\r\n  std<span style=\"color: #555555;\">::<\/span><span style=\"color: #007788; font-weight: bold;\">size_t<\/span> size() <span style=\"color: #006699; font-weight: bold;\">const<\/span>{ \r\n    <span style=\"color: #006699; font-weight: bold;\">return<\/span> cont.size(); \r\n  }\r\n\r\n  <span style=\"color: #0099ff; font-style: italic;\">\/\/ index operators<\/span>\r\n  T <span style=\"color: #006699; font-weight: bold;\">operator<\/span>[](<span style=\"color: #006699; font-weight: bold;\">const<\/span> std<span style=\"color: #555555;\">::<\/span><span style=\"color: #007788; font-weight: bold;\">size_t<\/span> i) <span style=\"color: #006699; font-weight: bold;\">const<\/span>{ \r\n    <span style=\"color: #006699; font-weight: bold;\">return<\/span> cont[i]; \r\n  }\r\n\r\n  T<span style=\"color: #555555;\">&amp;<\/span> <span style=\"color: #006699; font-weight: bold;\">operator<\/span>[](<span style=\"color: #006699; font-weight: bold;\">const<\/span> std<span style=\"color: #555555;\">::<\/span><span style=\"color: #007788; font-weight: bold;\">size_t<\/span> i){ \r\n    <span style=\"color: #006699; font-weight: bold;\">return<\/span> cont[i]; \r\n  }\r\n\r\n  <span style=\"color: #0099ff; font-style: italic;\">\/\/ returns the underlying data<\/span>\r\n  <span style=\"color: #006699; font-weight: bold;\">const<\/span> Cont<span style=\"color: #555555;\">&amp;<\/span> data() <span style=\"color: #006699; font-weight: bold;\">const<\/span>{ \r\n    <span style=\"color: #006699; font-weight: bold;\">return<\/span> cont; \r\n  }\r\n\r\n  Cont<span style=\"color: #555555;\">&amp;<\/span> data(){ \r\n    <span style=\"color: #006699; font-weight: bold;\">return<\/span> cont; \r\n  }\r\n};\r\n\r\n<span style=\"color: #0099ff; font-style: italic;\">\/\/ MyVector + MyVector<\/span>\r\n<span style=\"color: #006699; font-weight: bold;\">template<\/span><span style=\"color: #555555;\">&lt;<\/span><span style=\"color: #006699; font-weight: bold;\">typename<\/span> T, <span style=\"color: #006699; font-weight: bold;\">typename<\/span> Op1 , <span style=\"color: #006699; font-weight: bold;\">typename<\/span> Op2<span style=\"color: #555555;\">&gt;<\/span>\r\n<span style=\"color: #006699; font-weight: bold;\">class<\/span> <span style=\"color: #00aa88; font-weight: bold;\">MyVectorAdd<\/span>{\r\n  <span style=\"color: #006699; font-weight: bold;\">const<\/span> Op1<span style=\"color: #555555;\">&amp;<\/span> op1;\r\n  <span style=\"color: #006699; font-weight: bold;\">const<\/span> Op2<span style=\"color: #555555;\">&amp;<\/span> op2;\r\n\r\n<span style=\"color: #9999ff;\">public:<\/span>\r\n  MyVectorAdd(<span style=\"color: #006699; font-weight: bold;\">const<\/span> Op1<span style=\"color: #555555;\">&amp;<\/span> a, <span style=\"color: #006699; font-weight: bold;\">const<\/span> Op2<span style=\"color: #555555;\">&amp;<\/span> b)<span style=\"color: #555555;\">:<\/span> op1(a), op2(b){}\r\n\r\n  T <span style=\"color: #006699; font-weight: bold;\">operator<\/span>[](<span style=\"color: #006699; font-weight: bold;\">const<\/span> std<span style=\"color: #555555;\">::<\/span><span style=\"color: #007788; font-weight: bold;\">size_t<\/span> i) <span style=\"color: #006699; font-weight: bold;\">const<\/span>{ \r\n    <span style=\"color: #006699; font-weight: bold;\">return<\/span> op1[i] <span style=\"color: #555555;\">+<\/span> op2[i]; \r\n  }\r\n\r\n  std<span style=\"color: #555555;\">::<\/span><span style=\"color: #007788; font-weight: bold;\">size_t<\/span> size() <span style=\"color: #006699; font-weight: bold;\">const<\/span>{ \r\n    <span style=\"color: #006699; font-weight: bold;\">return<\/span> op1.size(); \r\n  }\r\n};\r\n\r\n<span style=\"color: #0099ff; font-style: italic;\">\/\/ elementwise MyVector * MyVector<\/span>\r\n<span style=\"color: #006699; font-weight: bold;\">template<\/span><span style=\"color: #555555;\">&lt;<\/span> <span style=\"color: #006699; font-weight: bold;\">typename<\/span> T, <span style=\"color: #006699; font-weight: bold;\">typename<\/span> Op1 , <span style=\"color: #006699; font-weight: bold;\">typename<\/span> Op2 <span style=\"color: #555555;\">&gt;<\/span>\r\n<span style=\"color: #006699; font-weight: bold;\">class<\/span> <span style=\"color: #00aa88; font-weight: bold;\">MyVectorMul<\/span> {\r\n  <span style=\"color: #006699; font-weight: bold;\">const<\/span> Op1<span style=\"color: #555555;\">&amp;<\/span> op1;\r\n  <span style=\"color: #006699; font-weight: bold;\">const<\/span> Op2<span style=\"color: #555555;\">&amp;<\/span> op2;\r\n\r\n<span style=\"color: #9999ff;\">public:<\/span>\r\n  MyVectorMul(<span style=\"color: #006699; font-weight: bold;\">const<\/span> Op1<span style=\"color: #555555;\">&amp;<\/span> a, <span style=\"color: #006699; font-weight: bold;\">const<\/span> Op2<span style=\"color: #555555;\">&amp;<\/span> b )<span style=\"color: #555555;\">:<\/span> op1(a), op2(b){}\r\n\r\n  T <span style=\"color: #006699; font-weight: bold;\">operator<\/span>[](<span style=\"color: #006699; font-weight: bold;\">const<\/span> std<span style=\"color: #555555;\">::<\/span><span style=\"color: #007788; font-weight: bold;\">size_t<\/span> i) <span style=\"color: #006699; font-weight: bold;\">const<\/span>{ \r\n    <span style=\"color: #006699; font-weight: bold;\">return<\/span> op1[i] <span style=\"color: #555555;\">*<\/span> op2[i]; \r\n  }\r\n\r\n  std<span style=\"color: #555555;\">::<\/span><span style=\"color: #007788; font-weight: bold;\">size_t<\/span> size() <span style=\"color: #006699; font-weight: bold;\">const<\/span>{ \r\n    <span style=\"color: #006699; font-weight: bold;\">return<\/span> op1.size(); \r\n  }\r\n};\r\n\r\n<span style=\"color: #0099ff; font-style: italic;\">\/\/ function template for the + operator<\/span>\r\n<span style=\"color: #006699; font-weight: bold;\">template<\/span><span style=\"color: #555555;\">&lt;<\/span><span style=\"color: #006699; font-weight: bold;\">typename<\/span> T, <span style=\"color: #006699; font-weight: bold;\">typename<\/span> R1, <span style=\"color: #006699; font-weight: bold;\">typename<\/span> R2<span style=\"color: #555555;\">&gt;<\/span>\r\nMyVector<span style=\"color: #555555;\">&lt;<\/span>T, MyVectorAdd<span style=\"color: #555555;\">&lt;<\/span>T, R1, R2<span style=\"color: #555555;\">&gt;<\/span> <span style=\"color: #555555;\">&gt;<\/span>\r\n<span style=\"color: #006699; font-weight: bold;\">operator<\/span><span style=\"color: #555555;\">+<\/span> (<span style=\"color: #006699; font-weight: bold;\">const<\/span> MyVector<span style=\"color: #555555;\">&lt;<\/span>T, R1<span style=\"color: #555555;\">&gt;&amp;<\/span> a, <span style=\"color: #006699; font-weight: bold;\">const<\/span> MyVector<span style=\"color: #555555;\">&lt;<\/span>T, R2<span style=\"color: #555555;\">&gt;&amp;<\/span> b){\r\n  <span style=\"color: #006699; font-weight: bold;\">return<\/span> MyVector<span style=\"color: #555555;\">&lt;<\/span>T, MyVectorAdd<span style=\"color: #555555;\">&lt;<\/span>T, R1, R2<span style=\"color: #555555;\">&gt;<\/span> <span style=\"color: #555555;\">&gt;<\/span>(MyVectorAdd<span style=\"color: #555555;\">&lt;<\/span>T, R1, R2 <span style=\"color: #555555;\">&gt;<\/span>(a.data(), b.data()));   <em><span style=\"color: #0099ff;\">\/\/ (1)\r\n}<\/span><\/em>\r\n\r\n<span style=\"color: #0099ff; font-style: italic;\">\/\/ function template for the * operator<\/span>\r\n<span style=\"color: #006699; font-weight: bold;\">template<\/span><span style=\"color: #555555;\">&lt;<\/span><span style=\"color: #006699; font-weight: bold;\">typename<\/span> T, <span style=\"color: #006699; font-weight: bold;\">typename<\/span> R1, <span style=\"color: #006699; font-weight: bold;\">typename<\/span> R2<span style=\"color: #555555;\">&gt;<\/span>\r\nMyVector<span style=\"color: #555555;\">&lt;<\/span>T, MyVectorMul<span style=\"color: #555555;\">&lt;<\/span> T, R1, R2<span style=\"color: #555555;\">&gt;<\/span> <span style=\"color: #555555;\">&gt;<\/span>\r\n<span style=\"color: #006699; font-weight: bold;\">operator<\/span><span style=\"color: #555555;\">*<\/span> (<span style=\"color: #006699; font-weight: bold;\">const<\/span> MyVector<span style=\"color: #555555;\">&lt;<\/span>T, R1<span style=\"color: #555555;\">&gt;&amp;<\/span> a, <span style=\"color: #006699; font-weight: bold;\">const<\/span> MyVector<span style=\"color: #555555;\">&lt;<\/span>T, R2<span style=\"color: #555555;\">&gt;&amp;<\/span> b){\r\n   <span style=\"color: #006699; font-weight: bold;\">return<\/span> MyVector<span style=\"color: #555555;\">&lt;<\/span>T, MyVectorMul<span style=\"color: #555555;\">&lt;<\/span>T, R1, R2<span style=\"color: #555555;\">&gt;<\/span> <span style=\"color: #555555;\">&gt;<\/span>(MyVectorMul<span style=\"color: #555555;\">&lt;<\/span>T, R1, R2 <span style=\"color: #555555;\">&gt;<\/span>(a.data(), b.data()));  <em><span style=\"color: #0099ff;\">\/\/ (2)<\/span><\/em>\r\n}\r\n\r\n<span style=\"color: #0099ff; font-style: italic;\">\/\/ function template for &lt; operator<\/span>\r\n<span style=\"color: #006699; font-weight: bold;\">template<\/span><span style=\"color: #555555;\">&lt;<\/span><span style=\"color: #006699; font-weight: bold;\">typename<\/span> T<span style=\"color: #555555;\">&gt;<\/span>\r\nstd<span style=\"color: #555555;\">::<\/span>ostream<span style=\"color: #555555;\">&amp;<\/span> <span style=\"color: #006699; font-weight: bold;\">operator<\/span><span style=\"color: #555555;\">&lt;&lt;<\/span>(std<span style=\"color: #555555;\">::<\/span>ostream<span style=\"color: #555555;\">&amp;<\/span> os, <span style=\"color: #006699; font-weight: bold;\">const<\/span> MyVector<span style=\"color: #555555;\">&lt;<\/span>T<span style=\"color: #555555;\">&gt;&amp;<\/span> cont){  \r\n  std<span style=\"color: #555555;\">::<\/span>cout <span style=\"color: #555555;\">&lt;&lt;<\/span> <span style=\"color: #cc3300;\">'\\n'<\/span>;\r\n  <span style=\"color: #006699; font-weight: bold;\">for<\/span> (<span style=\"color: #007788; font-weight: bold;\">int<\/span> i <span style=\"color: #555555;\">=<\/span> <span style=\"color: #ff6600;\">0<\/span>; i <span style=\"color: #555555;\">&lt;<\/span> cont.size(); <span style=\"color: #555555;\">++<\/span>i) {\r\n    os <span style=\"color: #555555;\">&lt;&lt;<\/span> cont[i] <span style=\"color: #555555;\">&lt;&lt;<\/span> <span style=\"color: #cc3300;\">' '<\/span>;\r\n  }\r\n  os <span style=\"color: #555555;\">&lt;&lt;<\/span> <span style=\"color: #cc3300;\">'\\n'<\/span>;\r\n  <span style=\"color: #006699; font-weight: bold;\">return<\/span> os;\r\n} \r\n\r\n<span style=\"color: #007788; font-weight: bold;\">int<\/span> main(){\r\n\r\n  MyVector<span style=\"color: #555555;\">&lt;<\/span><span style=\"color: #007788; font-weight: bold;\">double<\/span><span style=\"color: #555555;\">&gt;<\/span> x(<span style=\"color: #ff6600;\">10<\/span>,<span style=\"color: #ff6600;\">5.4<\/span>);\r\n  MyVector<span style=\"color: #555555;\">&lt;<\/span><span style=\"color: #007788; font-weight: bold;\">double<\/span><span style=\"color: #555555;\">&gt;<\/span> y(<span style=\"color: #ff6600;\">10<\/span>,<span style=\"color: #ff6600;\">10.3<\/span>);\r\n\r\n  MyVector<span style=\"color: #555555;\">&lt;<\/span><span style=\"color: #007788; font-weight: bold;\">double<\/span><span style=\"color: #555555;\">&gt;<\/span> result(<span style=\"color: #ff6600;\">10<\/span>);\r\n  \r\n  result<span style=\"color: #555555;\">=<\/span> x <span style=\"color: #555555;\">+<\/span> x <span style=\"color: #555555;\">+<\/span> y <span style=\"color: #555555;\">*<\/span> y;                                                        \r\n  \r\n  std<span style=\"color: #555555;\">::<\/span>cout <span style=\"color: #555555;\">&lt;&lt;<\/span> result <span style=\"color: #555555;\">&lt;&lt;<\/span> <span style=\"color: #cc3300;\">'\\n'<\/span>;\r\n  \r\n}\r\n<\/pre>\n<\/div>\n<p>&nbsp;<\/p>\n<p>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 trees (lines 1 and 2). The expression trees are only created but not evaluated. Lazy, of course. The assignment operator (line 3) triggers the evaluation of the expression tree that needs no temporaries.<\/p>\n<p>The result is the same.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\" size-full wp-image-5184\" src=\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2017\/02\/vectorArithmeticExpressionTemplates.png\" alt=\"vectorArithmeticExpressionTemplates\" width=\"600\" height=\"175\" style=\"display: block; margin-left: auto; margin-right: auto;\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>Thanks to the compiler explorer, I can visualize the magic of the program <span style=\"font-family: courier new,courier;\">vectorArithmeticExpressionTemplates.cpp<\/span>.<\/p>\n<h3>Under the hood<\/h3>\n<p>Here are the essential assembler instructions for the final assignment in the main function: <code>result<span style=\"color: #555555;\">=<\/span> x <span style=\"color: #555555;\">+<\/span> x <span style=\"color: #555555;\">+<\/span> y <span style=\"color: #555555;\">*<\/span> y<\/code>.<\/p>\n<p>&nbsp;<img loading=\"lazy\" decoding=\"async\" class=\" size-full wp-image-5185\" src=\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2017\/02\/godbolt.png\" alt=\"godbolt\" width=\"650\" height=\"163\" style=\"margin: 15px auto; display: block;\" srcset=\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2017\/02\/godbolt.png 921w, https:\/\/www.modernescpp.com\/wp-content\/uploads\/2017\/02\/godbolt-300x75.png 300w, https:\/\/www.modernescpp.com\/wp-content\/uploads\/2017\/02\/godbolt-768x193.png 768w\" sizes=\"auto, (max-width: 650px) 100vw, 650px\" \/><\/p>\n<p>The expression tree in the assembler snippet looks scary, but you can see the structure with a sharp eye. For simplicity reasons, I ignored <span style=\"font-family: courier new,courier;\">std::allocator<\/span> in my graphic.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\" size-full wp-image-5186\" src=\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2017\/02\/Exression.png\" alt=\"Exression\" width=\"600\" height=\"286\" style=\"margin: 15px auto; display: block;\" srcset=\"https:\/\/www.modernescpp.com\/wp-content\/uploads\/2017\/02\/Exression.png 1254w, https:\/\/www.modernescpp.com\/wp-content\/uploads\/2017\/02\/Exression-300x143.png 300w, https:\/\/www.modernescpp.com\/wp-content\/uploads\/2017\/02\/Exression-1024x488.png 1024w, https:\/\/www.modernescpp.com\/wp-content\/uploads\/2017\/02\/Exression-768x366.png 768w\" sizes=\"auto, (max-width: 600px) 100vw, 600px\" \/><\/p>\n<h2>What&#8217;s next?<\/h2>\n<p>A policy is a generic function or class whose behavior can be configured. Let me introduce them in my next post.<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Expression templates are typically used in linear algebra and are&nbsp; &#8220;structures representing a computation at compile-time, which are evaluated only as needed to produce efficient code for the entire computation&#8221; (https:\/\/en.wikipedia.org\/wiki\/Expression_templates). In other words, expression templates are only evaluated when needed.&nbsp;<\/p>\n","protected":false},"author":21,"featured_media":6318,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[376],"tags":[424],"class_list":["post-6319","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-templates","tag-expression-templates"],"_links":{"self":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/6319","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=6319"}],"version-history":[{"count":1,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/6319\/revisions"}],"predecessor-version":[{"id":6678,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/6319\/revisions\/6678"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media\/6318"}],"wp:attachment":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media?parent=6319"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=6319"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=6319"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}