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

  1. #1
    Registered User
    Join Date
    Apr 2020
    Posts
    18

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

    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!!

  2. #2
    Registered User Sir Galahad's Avatar
    Join Date
    Nov 2016
    Location
    The Round Table
    Posts
    174
    Quote Originally Posted by ccafe View Post
    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.
    Last edited by Sir Galahad; 04-19-2020 at 03:51 AM.
    The power of null.

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,994
    Quote 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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Registered User Sir Galahad's Avatar
    Join Date
    Nov 2016
    Location
    The Round Table
    Posts
    174
    Quote Originally Posted by laserlight View Post
    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.
    The power of null.

  5. #5
    Registered User
    Join Date
    Apr 2020
    Posts
    18
    Quote Originally Posted by laserlight View Post
    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.
    Last edited by ccafe; 04-19-2020 at 09:56 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. variable declarations and arithmetic expressions
    By r3zaneo in forum C Programming
    Replies: 3
    Last Post: 10-21-2012, 01:36 PM
  2. Stacks and arithmetic expressions
    By +Azazel+ in forum C Programming
    Replies: 11
    Last Post: 10-23-2007, 02:48 AM
  3. Open Source / Semi Open source game idea. Help needed
    By CaptainPatent in forum Projects and Job Recruitment
    Replies: 10
    Last Post: 05-16-2007, 10:44 AM
  4. speed/optimization concerns
    By confuted in forum C++ Programming
    Replies: 5
    Last Post: 04-01-2003, 12:29 AM
  5. Replies: 1
    Last Post: 11-19-2001, 04:45 PM

Tags for this Thread