Thread: Source-to-source speed optimization of C++ arithmetic expressions?

Originally Posted by ccafe

Do you know of any tool that can transform the operations in a C++ arithmetic expression for optimizing it for speed?

Most C++ compilers can optimize expressions automatically for builtins like ints and floats, but if you implement your own type, like a bigint, or your own float format, then the compiler won't be able to rearrange your expressions for speed (in fact, it wouldn't be able to do so unless it knew the time cost for each operator).

Do you know of any C++ source-to-source optimizer capable of doing this?

Thanks!!

How would a compiler possibly go about optimizing such a thing in the first place, much less some "generic" third party library? You can of course do this in C++, but the solution would likely be highly specific to the particular "mathematical type" in question.

But yes, you could simply have all of the operators return "cheap" proxy objects which then could be efficiently "finalized" into some concrete instance.

Originally Posted by Sir Galahad

How would a compiler possibly go about optimizing such a thing in the first place, much less some "generic" third party library? You can of course do this in C++, but the solution would likely be highly specific to the particular "mathematical type" in question.

A compiler's static analysis can handle the low hanging fruit of constant folding, constant propagation, replacing multiplication or division by powers of two with bit shifting, or replacing the common x % 2 == 0 with x & 1 == 0. A compiler could even rearrange expressions so as to allow for non-obvious constant folding and/or to reduce the number/cost of operations. It sounds like the latter is especially what ccafe was looking for with some kind of tool that preprocesses C++ code (so no proxy objects in the code as the result is the optimised C++ source code as if a human had hand-optimised it, hence "source-to-source"), but yeah, I have never heard of anyone attempting to do that in a manner that could handle third party libraries, and ccafe did note that "it wouldn't be able to do so unless it knew the time cost for each operator"... which in a bignum library is probably complicated further by the size of the operands possibly only being known at run time and yet impacting the time cost significantly.

Originally Posted by laserlight

A compiler's static analysis can handle the low hanging fruit of constant folding, constant propagation, replacing multiplication or division by powers of two with bit shifting, or replacing the common x % 2 == 0 with x & 1 == 0. A compiler could even rearrange expressions so as to allow for non-obvious constant folding and/or to reduce the number/cost of operations. It sounds like the latter is especially what ccafe was looking for with some kind of tool that preprocesses C++ code (so no proxy objects in the code as the result is the optimised C++ source code as if a human had hand-optimised it, hence "source-to-source"), but yeah, I have never heard of anyone attempting to do that in a manner that could handle third party libraries, and ccafe did note that "it wouldn't be able to do so unless it knew the time cost for each operator"... which in a bignum library is probably complicated further by the size of the operands possibly only being known at run time and yet impacting the time cost significantly.

That is true, there would be certain things the compiler could do to help optimize things. But as far as being able to determine the exact relationship between all of the different operators, that's going to be highly dependent upon whatever "algebra" you're trying to emulate.

Originally Posted by laserlight

A compiler's static analysis can handle the low hanging fruit of constant folding, constant propagation, replacing multiplication or division by powers of two with bit shifting, or replacing the common x % 2 == 0 with x & 1 == 0. A compiler could even rearrange expressions so as to allow for non-obvious constant folding and/or to reduce the number/cost of operations. It sounds like the latter is especially what ccafe was looking for with some kind of tool that preprocesses C++ code (so no proxy objects in the code as the result is the optimised C++ source code as if a human had hand-optimised it, hence "source-to-source"), but yeah, I have never heard of anyone attempting to do that in a manner that could handle third party libraries, and ccafe did note that "it wouldn't be able to do so unless it knew the time cost for each operator"... which in a bignum library is probably complicated further by the size of the operands possibly only being known at run time and yet impacting the time cost significantly.

The unfortunate thing here is that the C++ standard doesn't provide a way for defining the mathematical properties of operators. Compilers can rearrange expressions, and change operators by faster ones, but only when the source code has been translated into intermediate representation, or into object code. In that moment, the compiler does know the mathematical properties of the operations (an addition taking two integers has well-defined mathematical properties). On the other hand, at source code level, C++ doesn't let you define properties such as commutativity, associativity, etc... (in fact if you create your own class for integers and you define the "+" operator for doing square roots, you are not even violating the standard, because using "+" for additions is recommended but not required by the C++ standard).

In conclusion, static analysis cannot be used for optimizing arithmetic expressions except for expressions that have been translated by earlier compiler stages into intermediate representation or object code.

I wish the C++ standard is enhanced to let you specify the properties guaranteed by your operators. Without this, you cannot for example optimize expressions taking matrices and vectors (well, you can use Mathematica for optimizing them, of course, but it's unfortunate that the compiler cannot do it in the same way it can do it for builtin integers/floats). BTW, this is another reason I could add in the other thread in which I guess I got banned or something, because I can see your reply laserlight, but not the message I posted before your reply.