6

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.

Dmitri Nesteruk
  • 315

2 Answers2

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.

Chris Taylor
  • 28,955
  • Thanks! Is the performance difference a well-known value (say, on a modern-day Quad-core CPU)? – Dmitri Nesteruk Sep 16 '11 at 13:34
  • 1
    But are these two expressions equivalent in floating-point arithmetic? – lhf Sep 16 '11 at 13:38
  • @Dmitri, a rule of thumb is that addition takes 3 units, multiplication 4 units and division 32 units of time (e.g. clock cycles). – Chris Taylor Sep 16 '11 at 13:40
  • @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. – Chris Taylor Sep 16 '11 at 13:42
  • I 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) – Dmitri Nesteruk Sep 16 '11 at 13:53
  • Even then, it might not always be right to optimize out stuff like y/y to 1. – J. M. ain't a mathematician Sep 16 '11 at 14:20
  • Chris: 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... – J. M. ain't a mathematician Sep 16 '11 at 14:22
  • Could be true. It is 'optimised' for speed, not accuracy :) – Chris Taylor Sep 16 '11 at 14:25
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?

lhf
  • 216,483
  • 1
    I 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. – Dmitri Nesteruk Sep 16 '11 at 12:55
  • 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. – lhf Sep 16 '11 at 13:17
  • Okay, 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. – Dmitri Nesteruk Sep 16 '11 at 13:22
  • 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. – lhf Sep 16 '11 at 13:35