4 ms·

Interesting, thank you for the detailed answer. Expression templates do look very intriguing and powerful, I wonder what kind of application it enable. Julia h

by ced 10y ago

Interesting, thank you for the detailed answer. Expression templates do look very intriguing and powerful, I wonder what kind of application it enable. Julia has several cool performance-oriented constructs too: generated functions, loop fusion, JIT compilation (like your static if), and immutables (http://julialang.org/blog/2013/03/efficient-aggregates http://julialang.org/blog/2013/03/efficient-aggregates). It has a lot of potential, but then, so do other performance-oriented languages. It'll be interesting to do comparisons in a few years when the dust has settled a bit.

srean 10y ago
> Expression templates do look very intriguing and powerful, I wonder what kind of application it enable. Fast chain of operations on an array was one of the primary motivations. You can take a look at Blitz++, I believe it was the first library to push that idea. But ET is not limited to numerical operations on an array, you could do query optimization, optimization of string concatenation, essentially any application where deforestation of parse trees have the potential to make things faster.
- KKKKkkkk1 10y ago
  Curiously enough, linear algebra is the canonical application for expression templates, and yet if you ask a linear algebra expert, they will tell you that expression templates bring no benefits to 99% of linear algebra computations and make your code complex and bug prone. For examples of how expression templates can screw you up in unexpected ways, see: https://eigen.tuxfamily.org/dox/TopicLazyEvaluation.html https://eigen.tuxfamily.org/dox/TopicLazyEvaluation.html https://eigen.tuxfamily.org/dox/TopicFunctionTakingEigenTypes.html https://eigen.tuxfamily.org/dox/TopicFunctionTakingEigenType... https://eigen.tuxfamily.org/dox/TopicPitfalls.html https://eigen.tuxfamily.org/dox/TopicPitfalls.html
  - cjhanks 10y ago
    It depends on the codebase you are working with. Prior to 'auto' it was difficult to impossible to annotate expressions (thus forcing evaluation on assignment). Many people still believe "more lines of code = more slow", they will have problems. Functional non-template boundaries are also slow... any time you force evaluation you will see slow down. My experience... sometimes I have to pass through multiple reference frames to get to the correct affine transformation. I have three options: manually derive the transform (only works for a finite number of well understood transformations), waste BLAS ops on transform concatenation, or let expression templates fold numerical operations to the solution (often with numerical precision benefits btw).
    - KKKKkkkk1 10y ago
      Can you explain what you're getting at? I've spoken to people who authored expression template libraries and they say that mixing auto with expressions is a worst practice. You're setting yourself up for bugs. See the third link above. As to chaining affine transformations, how is letting the expression-template library evaluate a chain of transformations different from doing so explicitly? Would you agree that the computation boils down to the same flops either way?
      - cjhanks 10y ago
        You claimed there was no benefit to expression templates and I agreed that in C++98 this is true. Auto can introduce complications, I agree... I have a few times experienced the aliasing bugs it introduces, it's tricky and not a panacea. Though 99/100 times it allows me to write the code I mean rather than the the syntax that is necessary. Of course concatenation of transforms explicitly can be equivalent in FLOPS... as long as there are no redundant calls to transcendental functions or vector operations which can be folded for better cache coherency.
      - srean 10y ago
        Yeah 'auto' really messed ET up. The consequences the design would have on ET was not on the committees mind. I guess there was no one there in the committee who was that deep into high performance computing of this kind. > computation boils down to the same flops either way? same number of operations, yes possibly, but that carries almost no weight at all. Write a straight 3 nested for loop for a matrix multiply and then right another one with some thoughts on cache re-use. The latter will beat the former by an order of magnitude if not two. The situation is a bit better now thanks to 'smart enough compilers'.
  - srean 10y ago
    > expression templates bring no benefits to 99% of linear algebra computations If you limit the scope of your statement adequately enough, I would agree. What ET did was to remove the overhead that conventional style C++ brought to OOP matrix libraries. Fortran and C would beat C++ libraries hands down. So ET pulled C++ up to level 0: what a naïve (but verbose) implementation in, say C, would have got you. It is only after this the real stuff begins, optimizing for cache reuse, common subexpression elimination. Nowadays there are more advanced ET libraries that do this. > linear algebra computations To elaborate on this a bit more. We usually encounter two broad kinds of operations. One is of the linear algebraic variety, e.g. mat_vec, mat_mat etc. Here ET by itself wont buy you much. Here it is all about cach re-use. The other kind of operations are those chained operations (some times these are called array operations, as opposed to matrix or linear algebraic operations), it is here that ET will show its strength. A high performance library in C++ would typically use ET for these and fall back to BLAS for the former.

by ced 10y ago

srean 10y ago

> Expression templates do look very intriguing and powerful, I wonder what kind of application it enable. Fast chain of operations on an array was one of the primary motivations. You can take a look at Blitz++, I believe it was the first library to push that idea. But ET is not limited to numerical operations on an array, you could do query optimization, optimization of string concatenation, essentially any application where deforestation of parse trees have the potential to make things faster.

KKKKkkkk1 10y ago
Curiously enough, linear algebra is the canonical application for expression templates, and yet if you ask a linear algebra expert, they will tell you that expression templates bring no benefits to 99% of linear algebra computations and make your code complex and bug prone. For examples of how expression templates can screw you up in unexpected ways, see: https://eigen.tuxfamily.org/dox/TopicLazyEvaluation.html https://eigen.tuxfamily.org/dox/TopicLazyEvaluation.html https://eigen.tuxfamily.org/dox/TopicFunctionTakingEigenTypes.html https://eigen.tuxfamily.org/dox/TopicFunctionTakingEigenType... https://eigen.tuxfamily.org/dox/TopicPitfalls.html https://eigen.tuxfamily.org/dox/TopicPitfalls.html
- cjhanks 10y ago
  It depends on the codebase you are working with. Prior to 'auto' it was difficult to impossible to annotate expressions (thus forcing evaluation on assignment). Many people still believe "more lines of code = more slow", they will have problems. Functional non-template boundaries are also slow... any time you force evaluation you will see slow down. My experience... sometimes I have to pass through multiple reference frames to get to the correct affine transformation. I have three options: manually derive the transform (only works for a finite number of well understood transformations), waste BLAS ops on transform concatenation, or let expression templates fold numerical operations to the solution (often with numerical precision benefits btw).
  - KKKKkkkk1 10y ago
    Can you explain what you're getting at? I've spoken to people who authored expression template libraries and they say that mixing auto with expressions is a worst practice. You're setting yourself up for bugs. See the third link above. As to chaining affine transformations, how is letting the expression-template library evaluate a chain of transformations different from doing so explicitly? Would you agree that the computation boils down to the same flops either way?
    - cjhanks 10y ago
      You claimed there was no benefit to expression templates and I agreed that in C++98 this is true. Auto can introduce complications, I agree... I have a few times experienced the aliasing bugs it introduces, it's tricky and not a panacea. Though 99/100 times it allows me to write the code I mean rather than the the syntax that is necessary. Of course concatenation of transforms explicitly can be equivalent in FLOPS... as long as there are no redundant calls to transcendental functions or vector operations which can be folded for better cache coherency.
    - srean 10y ago
      Yeah 'auto' really messed ET up. The consequences the design would have on ET was not on the committees mind. I guess there was no one there in the committee who was that deep into high performance computing of this kind. > computation boils down to the same flops either way? same number of operations, yes possibly, but that carries almost no weight at all. Write a straight 3 nested for loop for a matrix multiply and then right another one with some thoughts on cache re-use. The latter will beat the former by an order of magnitude if not two. The situation is a bit better now thanks to 'smart enough compilers'.
- srean 10y ago
  > expression templates bring no benefits to 99% of linear algebra computations If you limit the scope of your statement adequately enough, I would agree. What ET did was to remove the overhead that conventional style C++ brought to OOP matrix libraries. Fortran and C would beat C++ libraries hands down. So ET pulled C++ up to level 0: what a naïve (but verbose) implementation in, say C, would have got you. It is only after this the real stuff begins, optimizing for cache reuse, common subexpression elimination. Nowadays there are more advanced ET libraries that do this. > linear algebra computations To elaborate on this a bit more. We usually encounter two broad kinds of operations. One is of the linear algebraic variety, e.g. mat_vec, mat_mat etc. Here ET by itself wont buy you much. Here it is all about cach re-use. The other kind of operations are those chained operations (some times these are called array operations, as opposed to matrix or linear algebraic operations), it is here that ET will show its strength. A high performance library in C++ would typically use ET for these and fall back to BLAS for the former.