1

I'm not familiar with the details of how the addition and multiplication operators are defined in C++, and I also don't know what information is or is not available to the compiler to optimize out inefficient orders of operation.

Let's say we have a matrix datatype with an implementation of element-wise multiplication by a scalar (i.e scaling the matrix by a scalar). If we have the following code snippet:

Matrix a;
float b = /* value set at runtime */;
float c = /* value set at runtime */;
a = a * b * c;

If we naively evaluated this expression left-to-right, we would first scale a by b and then scale it by c rather than scaling a by the product of b and c. Is the compiler capable of selecting the latter (more efficient) behavior instead of the former?

AnimatedRNG
  • 1,859
  • 3
  • 26
  • 39
  • The compiler doesn't generally understand the semantics of user-defined functions. It would take an automatic theorem prover to prove that rewriting the expression to `a * c * b` doesn't change its meaning; it's highly unlikely that the compiler would be able to pull it off. – Igor Tandetnik Mar 30 '18 at 23:58
  • I recall hearing a story of some kind of experimental compiler that was able to rewrite `int s = 0; for (int i = 0; i < n; ++i) s += i;` to `s = n*(n+1)/2;` I strongly suspect it was an urban legend. – Igor Tandetnik Mar 31 '18 at 00:02
  • If C++ defines multiplication and addition as operations that must be associative, then I'd assume it's fair game for the compiler to rewrite the expression as `a * (b * c)` or `c * a * b`. Of course, the compiler would have to be able to determine that one of these orderings is more efficient. Again, I don't know much about compiler optimization, so this is just speculation. – AnimatedRNG Mar 31 '18 at 00:06
  • Hmm I just noticed https://stackoverflow.com/questions/6430448/why-doesnt-gcc-optimize-aaaaaa-to-aaaaaa?rq=1 . Still don't know if -fassociative-math would help – AnimatedRNG Mar 31 '18 at 00:08
  • C++ makes certain assumptions about *built-in* operators. User-defined overloaded operators are just functions with funny names; no assumption is made about their behavior. `a * b * c` is merely a shorthand for `operator*(operator*(a, b), c)`; I assume your program defines `operator*(float, Matrix)` and `operator*(Matrix, float)` alonside `class Matrix` – Igor Tandetnik Mar 31 '18 at 00:10

1 Answers1

3

Some experimentation on Godbolt appears to find that recent versions of GCC and Clang generate the same code for a * b * c as it does for (a * b) * c, which is longer than what it generates for a * (b * c), therefore it appears that no, compilers are not smart enough to perform the optimization you're asking about.

You could just parenthesize b * c yourself. A more complicated solution is to have the * operator generate an expression template that will be optimized before evaluation, so even if the user types (a * b) * c your library will rearrange it to a * (b * c) before evaluating it.

Brian Bi
  • 111,498
  • 10
  • 176
  • 312
  • It's not so much that they're not "smart enough". More like they're not that dumb. It would result it different behavior and violate the C++ spec, because floats aren't often exact representations, multiplication is not associative. Even if `a`, `b`, and `c` were all floats with no Matrix involved. – Paul Mar 31 '18 at 00:37
  • @paulpro most compilers have flags to permit associativity on floating point multiplication even if it changes results. – Yakk - Adam Nevraumont Mar 31 '18 at 02:59