performance

[Gregory Noulin]

I am looking for differences of cost of an equality test between 2
integers and a multiplication between 2 integers.

Which operation is most costly : multiplication (*) or equality test (==)

 

[lallous]

I am looking for differences of cost of an equality test between 2
integers and a multiplication between 2 integers.

Which operation is most costly : multiplication (*) or equality test (==)

That depends on the CPU Arch. and the code produced by the compiler to do
the comparison or multiplication.

For example, on x86, the comparison might be like this:

if (x == y)

mov ax, x
xor ax, y
jz _yes_equal

And multiplication:

x * y

mov bx, x
mov ax, y
mul bx

So the answer relies on whether "xor" is executed faster than "mul"
As I remember, yes , "xor" is faster.

In most cases the comparison is faster than multiplication.

 

[John Harrison]

I am looking for differences of cost of an equality test between 2
integers and a multiplication between 2 integers.

Which operation is most costly : multiplication (*) or equality test (==)

It depends entirely on your platform. C++ does not specify anything about
the cost of these operations.

Since the two operations do completely different things I can't understand
why you'd want to know which was faster. Please explain.

john

 

[Peter van Merkerk]

(==)

It depends entirely on your platform.

On some platforms it also depends on how predictable the outcome of the
equality test will be. I.e. there no way to answer this question without
going into the specifics.

 

[Gregory Noulin]

It depends entirely on your platform. C++ does not specify anything about
the cost of these operations.

Since the two operations do completely different things I can't understand
why you'd want to know which was faster. Please explain.

john

I have a data set and i have the choice between 2 structures. I have a
computation formula which needs to access to element of data.
On the first hand, i have a direct access to element (but a big big
structure) and in the formula i make useless operations (addition,
multiplication).
On the other hand, i must make a test (==) to access to the good element
(but a smaller structure) and in the formula i don't make any useless
operations.

I just want to know if a test isn't too costly in order to choose the
smaller structure

 

[John Harrison]

I have a data set and i have the choice between 2 structures. I have a
computation formula which needs to access to element of data.
On the first hand, i have a direct access to element (but a big big
structure) and in the formula i make useless operations (addition,
multiplication).
On the other hand, i must make a test (==) to access to the good element
(but a smaller structure) and in the formula i don't make any useless
operations.

I just want to know if a test isn't too costly in order to choose the
smaller structure

I would be surprised if it made any noticeable difference at all. Your
choice should usually be governed by which is easier to understand, more
flexible to change, etc. etc. Efficiency would normally not be a
consideration at all.

So unless you have specific efficiency considerations to meet I'd forget
about it. It's a very common newbie trait to be needlessly concerned about
'efficiency' while ignoring the genuine efficiency issues like writing easy
to understand code. (Apologies if you are not a newbie).

If you really think that this is important, then the only way is to try both
choices and time them. But of course the answers you get will not
necessarily be applicable to any other machine or environment.

john

 

[djrb]

That depends on the CPU Arch. and the code produced by the compiler to do
the comparison or multiplication.

For example, on x86, the comparison might be like this:

if (x == y)

mov ax, x
xor ax, y
jz _yes_equal

And multiplication:

x * y

mov bx, x
mov ax, y
mul bx

So the answer relies on whether "xor" is executed faster than "mul"
As I remember, yes , "xor" is faster.

In most cases the comparison is faster than multiplication.

As far as I know, XOR takes only one clock on x86 compatibles (386 and
higher).
As to MUL, it takes much more clocks to complete (at least 2).

There is a good book on ASM at http://webster.cs.ucr.edu/AoA.html
Another source is at http://www.masm32.com/
MASM32 package contains a lot of help files where the timings of
various asm commands are specified, but, if I am not wrong, the
timings are specified only up to x386.

As for the latest P4 CPU(s), the best source is
http://www.intel.com/design/Pentium/manuals/

I hope this info will help

 

[Rolf Magnus]

On some platforms it also depends on how predictable the outcome of
the equality test will be. I.e. there no way to answer this question
without going into the specifics.

Further, it depends on the size of the integers. If the integer type is
bigger than the maximum integer sizes supported by the CPU, it will be
emulated.

 

[Jack Klein]

I have a data set and i have the choice between 2 structures. I have a
computation formula which needs to access to element of data.
On the first hand, i have a direct access to element (but a big big
structure) and in the formula i make useless operations (addition,
multiplication).
On the other hand, i must make a test (==) to access to the good element
(but a smaller structure) and in the formula i don't make any useless
operations.

I just want to know if a test isn't too costly in order to choose the
smaller structure

No general answer is possible. The C++ language defines how various
things work. It does not specify relative speed or efficiency of
anything. There are processors, unlike the Pentium and others used in
Windows PCs, that can do integer multiplications in a single clock
cycle, just as fast as they can do an integer comparison. In fact
there are some that can do floating point multiplications in a single
clock cycle.

If you absolutely need to know which is faster on your platform
running code generated by your compiler, write some test programs
using both methods and do some timing tests.

Generally the best approach is to write your program using the method
that generates the clearest, most easily read and understood code.
Then, when your program works correctly and only then, if the
performance of the program is not good enough, use a tool like a
profile to find the bottle necks. If and only if this routine is a
significant bottle neck in a too-slow program, experiment with ways to
speed it up.

If you worry about things like this ahead of time, you often wind up
spending a lot of effort on something that only makes a 1/10th of 1%
difference in the speed of the final code.