I'm writing an app which translates formulae into executable code. I've been experimenting with fairly obvious optimizations such as factoring (reducing number of multiplications) in order to make the code run faster. Can anyone suggest any other performance-related optimizations that could be performed when translating formulae to code? Thanks.
Looking for mathematical optimizations when translating formulae to code
5
$\begingroup$
optimization
-
4Make sure polynomials are always in Horner form. – 2011-09-16
-
2Another one: isolate common subexpressions. For example, if you're optimizing something like $2\cos^3 x-\cos^2 x+1$, the right optimization is to cache the value of the cosine in some temporary variable $u=\cos\,x$, and then rewrite the polynomial in terms of the temporary variable in Horner form: $(2u-1)u^2+1$. – 2011-09-16
-
0@J.M. thanks, subexpression analysis is one of the things I'm already working on – 2011-09-16
2 Answers
2
The code
double x = a / b + c / d;
typically takes about twice as long to execute as the equivalent expression
double x = (a * d + b * c) / (b * d);
because floating point division is very slow whereas addition and multiplication are fast.
As well as that there are the obvious things to do like pre-computing constant values, and replacing
double x = a + 0.0; double y = b * 1.0; double z = c / 1.0;
with the equivalent expressions
double x = a; double y = b; double z = c;
This isn't quite so nonsensical as it may appear: the constants 1.0
and 0.0
might not be the values originally written, but rather the results of some intermediate computation.
You could also optimize pow(x, 2)
to x * x
and the like, although any decent compiler should do this for you.
-
0Thanks! Is the performance difference a well-known value (say, on a modern-day Quad-core CPU)? – 2011-09-16
-
1But are these two expressions equivalent in floating-point arithmetic? – 2011-09-16
-
0@Dmitri, a rule of thumb is that addition takes 3 units, multiplication 4 units and division 32 units of time (e.g. clock cycles). – 2011-09-16
-
0@lhf No (although I don't think that's really a problem - how often do you care about the *exact* floating point representation of your result?). A more serious problem is that if you perform this optimization you might induce an overflow, if any of your intermediate products are larger than the maximum double value supported on your system. – 2011-09-16
-
0I optimize power methods already. As for calculations resulting in multiplication by 1, I think it's really hard to detect those unless I encounter something obvious like `x*(y/y)` – 2011-09-16
-
0Even then, it might not always be right to optimize out stuff like `y/y` to `1`. – 2011-09-16
-
0Chris: Hmm... if `a/b` and `c/d` are both tiny and of opposite sign, somehow it looks that the "optimized" expression is more cancellation-prone than the original one... – 2011-09-16
-
0Could be true. It is 'optimised' for speed, not accuracy :) – 2011-09-16
1
I think you'd better leave such optimizations to the compiler. Or do you have evidence that the compiler cannot do justice to your formulas?
-
1I don't think a compiler can optimize `a*x*x + b*x` to become `x*(a*x + b)` :) and that's just a simple case. – 2011-09-16
-
1@Dmitri, try `gcc -S -O2` on the program `int f(int a, int b, int x) { return a*x*x + b*x; } int g(int a, int b, int x) { return x*(a*x + b); }`. The generated code is the *same*. Using `double` instead of `int` does generate different code but it's probably because the compiler is aware that floating-point arithmetic is not distributive. – 2011-09-16
-
0Okay, so `gcc` can optimize this, but I don't think *every* compiler can do this. I don't think it's correct to rely on the compiler optimizing things for you. – 2011-09-16
-
3@Dmitri, sure, every compiler is gcc but you can bet that optimizing compilers will do a good job. There has been *decades* of research on that. My point is: don't try to outsmart the compiler; you may even force it to generated *worse* code than if you just wrote what you meant. – 2011-09-16