Multiplication Optimization

[walnutmon]

Hey guys, what's the difference in C++ in the speed of the following
two operations:

int x = a * b * c * d * e;

int x = a * f;

Where a, b, c, d, e are integers less that 1000 and f = b * c * d * e

Thanks

 

[Victor Bazarov]

Hey guys, what's the difference in C++ in the speed of the following
two operations:

int x = a * b * c * d * e;

int x = a * f;

Where a, b, c, d, e are integers less that 1000 and f = b * c * d * e

First of all, there is no guarantee that this operation will not overflow.
And if it does overflow, the behaviour is unspecified.

Second, if you do have 'f' precalculated, use it. You will save at least
three multiplications and three memory accesses. Overall, the difference
in speed is *most likely* not significant taken in the context of the whole
program execution.

V

 

[brian tyler]

Well for a start if; b, c, d and e are evenly randomly distributed
integers between 0 and 999, then their average product is going to be
~ 500^4 = 62500000000 >> 4294967296 = 2^32. So on a 32-bit system
"most" of the time you are going to get an overflow error, so even if
the question was well posed it's a moot point.

Brian

 

[walnutmon]

Well for a start if; b, c, d and e are evenly randomly distributed
integers between 0 and 999, then their average product is going to be
~ 500^4 = 62500000000 >> 4294967296 = 2^32. So on a 32-bit system
"most" of the time you are going to get an overflow error, so even if
the question was well posed it's a moot point.

Brian

How much more specific do you want to be, there are two possibilities,
overflow error and not, what if it doesn't overflow? Smart ass.

 

[Alan Johnson]

Hey guys, what's the difference in C++ in the speed of the following
two operations:

int x = a * b * c * d * e;

int x = a * f;

Where a, b, c, d, e are integers less that 1000 and f = b * c * d * e

Thanks

This is impossible to know. Just a few things you'd have to consider:
- does the processor have a multiply instruction
- what is the speed of a memory access relative to a multiply
- is a memory access even necessary or are some of these already in
registers
- can the compiler prove that any of the variables will have a specific
value (e.g. if this was done in a loop and only one variable changed
during the loop), or even have a specific property (e.g. a power of 2).

In general, prefer the things that intuitively seem like less work. In
this case the second instruction. When performance matters, measure it.

 

[Rui Maciel]

How much more specific do you want to be, there are two possibilities,
overflow error and not, what if it doesn't overflow?  Smart ass.

That was a rather rude answer. Are you aware that by posting a question not
only you are in effect begging for a favor but also no one is forced to
help you?


Rui Maciel

 

[walnutmon]

This is impossible to know. Just a few things you'd have to consider:
- does the processor have a multiply instruction
- what is the speed of a memory access relative to a multiply
- is a memory access even necessary or are some of these already in
registers
- can the compiler prove that any of the variables will have a specific
value (e.g. if this was done in a loop and only one variable changed
during the loop), or even have a specific property (e.g. a power of 2).

In general, prefer the things that intuitively seem like less work. In
this case the second instruction. When performance matters, measure it.

That makes sense, what I was actually getting at is this though... I
wasn't holding off, I simply didn't realize it at the time... At
compilation time does C++ optimize such an instruction into the more
simple version that I explicitly stated in the second example?

 

[Andrey Tarasevich]

That makes sense, what I was actually getting at is this though... I
wasn't holding off, I simply didn't realize it at the time... At
compilation time does C++ optimize such an instruction into the more
simple version that I explicitly stated in the second example?

I what you have in your code is explicitly

int x = a * b * c * d * e;

and there's no pre-calculated value for 'b * c * d * e' then the
compiler cannot optimize it into what you started in your second example
simply because it will not achieve anything. There's absolutely no
difference in doing the above, or doing

int f = b * c * d * e;
int x = a * f;

Now, if somewhere earlier you calculated 'f' yourself

int f = b * c * d * e;

and then, later, you calculate 'x' as

int x = a * b * c * d * e;

the compiler could be smart enough to optimize the second into

int x = a * f;

assuming that it it can establish the fact that 'b', 'c', 'd', and 'e'
didn't change between these points.

Also if you do your

int x = a * b * c * d * e;

repeatedly for different values of 'a', but the same values of 'b', 'c',
'd', and 'e', the compiler could be smart enough to pre-calculate 'b * c
* d * e' and use it to calculate 'x' instead of re-calculating the whole
thing every time.

But all this relies on the details you haven't provided. Outside of
those more specific contexts, once again, there's absolutely no
difference between your first and the second variant and, therefore, it
would be strange to expect the compiler to do this as an "optimization".

 

[brian tyler]

How much more specific do you want to be, there are two possibilities,
overflow error and not, what if it doesn't overflow? Smart ass.

I don't think I was being a smart ass, you could quite easily have
tried running some tests yourself to see if there was any difference
between the two calculations. I just thought you were being a bit
lazy, because you hadn't done any work yourself to answer your own
question. My reference to your question not being well posed was that
you hadn't given two algorithms, or code that would compile for
testing.