The performance of all kinds of C operations

[mrby]

Hi,

Does anyone know of any link which describes the (relative)
performance of all kinds of C operations? e.g: how fast is "add"
comparing with "multiplication " on a typical machine.

Thanks!

--
B. Y.

[Eric Sosman]

we******@gmail. com wrote:

Eric Sosman wrote:

we******@gmai l.com wrote:

Eric Sosman wrote:

we******@gm ail.com wrote:

>sp****@gma il.com wrote:
>
>>I didn't read your whole page but had a look at the table in the
>>section "Strictly for beginners". Can you explain why would
>>"x = y << 3" be faster than "x = y * 8" ? [...]
>
>It depends on your compiler. However, the assumption is that you
>aren't in control of the quality of your compiler, and hence, it may
>not perform the relevant transformation for you. Certainly for some
>compiler s it may make no difference. [...]

Thought exercise #1: For what `y' are the expressions
`y * 8' and `y << 3' *not* equivalent?

Whatever dude, the real world operates in 2s complement.

Well, you've spotted one of the non-equivalences.
Care to try for any of the others?

No -- why would I do that?

Um, er, to throw back the night of ignorance with the
brilliant lamp of learning?

--
Eric Sosman
es*****@acm-dot-org.invalid

[Nick Keighley]

we******@gmail. com wrote:

Nick Keighley wrote:

we******@gmail. com wrote:

Eric Sosman wrote:
> we******@gmail. com wrote:
> > sp****@gmail.co m wrote: > >>I didn't read your whole page but had a look at the table in the
> >>section "Strictly for beginners". Can you explain why would
> >>"x = y << 3" be faster than "x = y * 8" ? [...]

I was using a compiler in the '80s that was smart enough to replace * 8
with << 3. Stuff like this in the source just obscures the intent.

Explain how it obscures the intent.

obviously we are not on the same wavelength. If I want to multiply by 8
I write *8. Why would I do anything else? (unless measurement showed
<<3 was faster *and* this line of code needed to be faster).

What about *10 would you replace that with two shifts and an add?

Well its not a page about C pedantry, so that sort of mind set didn't
make it into my thinking when I wrote it. [It's] for beginners who care
about real programming, not beginners who want to turn into C pedants.

perhaps the page should have been labelled,
"For Beginners Who Never Want To Aspire To Excellence",
then

Do you issue these "excellence " badges yourself?

sure, my fees are very reasonable
:-)
--
Nick Keighley

A ruby trembled. Two tourmaline nets failed to rectify the laser beam.
A diamond noted the error. Both the error and the correction went into
the general computer.
Corwainer Smith "The Dead Lady of Clown Town"

[websnarf]

Nick Keighley wrote:

we******@gmail. com wrote:

Nick Keighley wrote:

we******@gmail. com wrote:
> Eric Sosman wrote:
> > we******@gmail. com wrote:
> > > sp****@gmail.co m wrote:
> > >>I didn't read your whole page but had a look at the table in the
> > >>section "Strictly for beginners". Can you explain why would
> > >>"x = y << 3" be faster than "x = y * 8" ? [...]

I was using a compiler in the '80s that was smart enough to replace * 8
with << 3. Stuff like this in the source just obscures the intent.
Explain how it obscures the intent.

obviously we are not on the same wavelength. If I want to multiply by 8
I write *8. Why would I do anything else? (unless measurement showed
<<3 was faster *and* this line of code needed to be faster).

If shifting by 3 is the *same* as multiplying by 8, then how is
shifting by 8 "doing something else" other than multiplying by 8? Tell
me, why do you think C includes a << operation?
What about *10 would you replace that with two shifts and an add?

That's a different question. Doing so involves a dependency chain of
operations, and there are alternative platform specific tricks for
this. So it doesn't belong in the "beginners section".

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

[CBFalconer]

Nick Keighley wrote:

we******@gmail. com wrote:

Nick Keighley wrote:
.... snip ...

I was using a compiler in the '80s that was smart enough to
replace * 8 with << 3. Stuff like this in the source just obscures the intent.

Explain how it obscures the intent.

obviously we are not on the same wavelength. If I want to multiply
by 8 I write *8. Why would I do anything else? (unless measurement
showed <<3 was faster *and* this line of code needed to be faster).

What about *10 would you replace that with two shifts and an add?

In general, replacing an understandable "multiply by 8" with an
obscure phrase meaning "bodily shift the (defined elsewhere) bits
of the value to the left 3 places resulting in possibly undefined
results", would be considered obscuring. In fact many would
consider it extremely sloppy programming. To do so requires
several things:

1. Proof that it improves performance on this system.
2. Proof that it will be valid for all possible operands.
3. Proof that the performance improvement (1) is significant.

otherwise the decision to make any such transformations is much
better left to the compiler optimizer.
From the standard, 6.5.7

[#4] The result of E1 << E2 is E1 left-shifted E2 bit
positions; vacated bits are filled with zeros. If E1 has an
unsigned type, the value of the result is E1*2^E2, reduced
modulo one more than the maximum value representable in the
result type. If E1 has a signed type and nonnegative value,
and E1*2^E2 is representable in the result type then that is
the resulting value; otherwise, the behavior is undefined.

--
"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews

[Keith Thompson]

we******@gmail. com writes:

Nick Keighley wrote:

we******@gmail. com wrote:

> Nick Keighley wrote:
> > we******@gmail. com wrote:
> > > Eric Sosman wrote:
> > > > we******@gmail. com wrote:
> > > > > sp****@gmail.co m wrote:
> > > > >>I didn't read your whole page but had a look at the table in the
> > > > >>section "Strictly for beginners". Can you explain why would
> > > > >>"x = y << 3" be faster than "x = y * 8" ? [...]
> >
> > I was using a compiler in the '80s that was smart enough to replace * 8
> > with << 3. Stuff like this in the source just obscures the intent.
>
> Explain how it obscures the intent.

obviously we are not on the same wavelength. If I want to multiply by 8
I write *8. Why would I do anything else? (unless measurement showed
<<3 was faster *and* this line of code needed to be faster).

If shifting by 3 is the *same* as multiplying by 8, then how is
shifting by 8 "doing something else" other than multiplying by 8? Tell
me, why do you think C includes a << operation?

For bitwise shifting, of course. Why do you think C includes a "*"
operation? Even if they happen to be mathematically equivalent in
certain cases, they're *conceptually* very different.

If I want something to be 8 times as big, I'll multiply it by 8.
(Tomorrow I might decide I want it to be 9 times as big.)

If I want to shift the bits of an object left by 3 positions I'll use
"<< 3". If shifting is really what I want to do here, I might decide
tomorrow that I want to shift by 4 bits; it's unlikely I'll decide I
want to multiply by 9.

I'll use the multiplication if it expresses what I want to do. If a
shift happens to be more efficient, I'll trust the compile to generate
a shift instruction -- or not to if it can't prove that it's really
equivalent, or if a multiplication is just as fast as a shift.

What if y is negative? (Answer: undefined behavior.) What if y is
floating-point? (Answer: you can't apply "<<" to floating-point
values.)

Finally, even assuming that y is unsigned or positive, what happens if
I replace this:
x = y * 8 + z;
by this:
x = y << 3 + z;
? The answer depends on the relative precedence of the "*", "+", and
"<<" operators. I don't know about you, but I had to look it up; even
if you have all the operator precedences memorized, the next person
who reads your code probably hasn't.

Now, please explain how
x = y << 3;
is *better* than
x = y * 8;
particularly for beginners. (Answer: it isn't.)

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Ian Collins]

we******@gmail. com wrote:

Nick Keighley wrote:

we******@gmai l.com wrote:

Nick Keighley wrote:

we******@gm ail.com wrote:

>Eric Sosman wrote:
>
>>we******@ gmail.com wrote:
>>
>>>sp****@g mail.com wrote:
>>>
>>>>I didn't read your whole page but had a look at the table in the
>>>>secti on "Strictly for beginners". Can you explain why would
>>>>"x = y << 3" be faster than "x = y * 8" ? [...]

I was using a compiler in the '80s that was smart enough to replace * 8
with << 3. Stuff like this in the source just obscures the intent.

Explain how it obscures the intent.

obviously we are not on the same wavelength. If I want to multiply by 8
I write *8. Why would I do anything else? (unless measurement showed
<<3 was faster *and* this line of code needed to be faster).

If shifting by 3 is the *same* as multiplying by 8, then how is
shifting by 8 "doing something else" other than multiplying by 8? Tell
me, why do you think C includes a << operation?

To left shift?

Can you name a compiler that won't optimise a multiply by power of 2 to
a shift?

Unnecessary optimisation is even worse than premature optimisation.

--
Ian Collins.

[jacob navia]

Keith Thompson a écrit :

we******@gmail. com writes:

Nick Keighley wrote:

we******@gma il.com wrote:

Nick Keighley wrote:

>we******@g mail.com wrote:
>
>>Eric Sosman wrote:
>>
>>>we****** @gmail.com wrote:
>>>
>>>>sp****@ gmail.com wrote:
>>>>
>>>>>I didn't read your whole page but had a look at the table in the
>>>>>sectio n "Strictly for beginners". Can you explain why would
>>>>>"x = y << 3" be faster than "x = y * 8" ? [...]
>
>I was using a compiler in the '80s that was smart enough to replace * 8
>with << 3. Stuff like this in the source just obscures the intent.

Explain how it obscures the intent.

obviously we are not on the same wavelength. If I want to multiply by 8
I write *8. Why would I do anything else? (unless measurement showed
<<3 was faster *and* this line of code needed to be faster).

If shifting by 3 is the *same* as multiplying by 8, then how is
shifting by 8 "doing something else" other than multiplying by 8? Tell
me, why do you think C includes a << operation?

For bitwise shifting, of course. Why do you think C includes a "*"
operation? Even if they happen to be mathematically equivalent in
certain cases, they're *conceptually* very different.

If I want something to be 8 times as big, I'll multiply it by 8.
(Tomorrow I might decide I want it to be 9 times as big.)

If I want to shift the bits of an object left by 3 positions I'll use
"<< 3". If shifting is really what I want to do here, I might decide
tomorrow that I want to shift by 4 bits; it's unlikely I'll decide I
want to multiply by 9.

I'll use the multiplication if it expresses what I want to do. If a
shift happens to be more efficient, I'll trust the compile to generate
a shift instruction -- or not to if it can't prove that it's really
equivalent, or if a multiplication is just as fast as a shift.

What if y is negative? (Answer: undefined behavior.) What if y is
floating-point? (Answer: you can't apply "<<" to floating-point
values.)

Finally, even assuming that y is unsigned or positive, what happens if
I replace this:
x = y * 8 + z;
by this:
x = y << 3 + z;
? The answer depends on the relative precedence of the "*", "+", and
"<<" operators. I don't know about you, but I had to look it up; even
if you have all the operator precedences memorized, the next person
who reads your code probably hasn't.

Now, please explain how
x = y << 3;
is *better* than
x = y * 8;
particularly for beginners. (Answer: it isn't.)

I agree with Mr Thomson here.

1) In modern Pentium processors, the (very clever) Intel designers
took the barrel shifter (that was there since the 8086) away.
This means that a <<= 3 is SLOWER than a *= 8.

Modern processors are highly complex beasts, and unless you
study the subject matter you risk to do the wrong decisions.

2) All C compilers will do the optimization a *= 8; with a shift
if a is unsigned, AND the processor warrants it. Lcc-win32
does this always since I was too lazy to modify the compiler
to follow that brain-dead Intel decision. After measuring
the actual code I could not find any difference even after
several billion tries, so I think... well forget it :-)

3) Most of this micro optimizations will not speed up a program.
A better algorithm, and above all a better DATA LAYOUT will
improve the program.

In modern workstation processors, the speed of main memory is VERY
slow compared to the speed of the processor, almost a factor of
20 or so. So you risk to do a lot of wait states when waiting for
memory to bring the data into the L1 cache. Optimizing data layout
so that locality of access is preserved (i.e. maintaining the data
in the L1 cache) is MUCH more important than caring about shifting
data or multiplying by 8. Those "optimizati on" are from the days
of the PDP11 or the 80286 maybe, but not in the modern processors
of today.

jacob

[websnarf]

jacob navia wrote:

I agree with Mr Thomson here.

1) In modern Pentium processors, the (very clever) Intel designers
took the barrel shifter (that was there since the 8086) away.
This means that a <<= 3 is SLOWER than a *= 8.
You mean the abortifact called the Pentium 4? First of all, its not
*SLOWER*, its about the same speed (the hardware operations I mean).
Second of all, the Pentium 4 is now officially obsolete, and the "slow
shifter" decision has been recinded. The new Israeli designed cores
from Intel have gone back to fast shifting. Implicit in my standing
behind my recommendation of continuing to use left shift instead of
multiplication when you can was a prediction that this would happen.
(It appears, I was right.) And finally, what do you say about AMD's
Opteron cores? They include 3 parallel single cycle integer shifters.
Modern processors are highly complex beasts, and unless you
study the subject matter you risk to do the wrong decisions.
You know who you are talking to right?
2) All C compilers will do the optimization a *= 8; with a shift
if a is unsigned, AND the processor warrants it. Lcc-win32
does this always since I was too lazy to modify the compiler
to follow that brain-dead Intel decision. After measuring
the actual code I could not find any difference even after
several billion tries, so I think... well forget it :-)
On the P4? Like I said, the reason why you measured no difference, is
because there is no difference. However, for Opterons, its still 0.33
- 1.0 clocks versus 3 clocks.
3) Most of this micro optimizations will not speed up a program.
A better algorithm, and above all a better DATA LAYOUT will
improve the program.
This sounds like a blanket statement, that is inherently inconsistent.
Once you *have* this better algorithm, are you still sure that
micro-optimizations wont work? This is a classic line typically spoken
by people who are actually bad at both strategies.
In modern workstation processors, the speed of main memory is VERY
slow compared to the speed of the processor, almost a factor of
20 or so.
First of all, you have to normalize your apples versus oranges
comparison, and second of all the current factor is more like 200.
However, CPU caches and caching strategies have also gotten a lot
better.
[...] So you risk to do a lot of wait states when waiting for
memory to bring the data into the L1 cache. Optimizing data layout
so that locality of access is preserved (i.e. maintaining the data
in the L1 cache) is MUCH more important than caring about shifting
data or multiplying by 8. Those "optimizati on" are from the days
of the PDP11 or the 80286 maybe, but not in the modern processors
of today.

Perhaps the days in which the *average* programmer was capable of
seeing the difference have gone. However, the benefits and
opportunities have not gone away.

Real time speech recognition and translation is still quite taxing on
processor, as is real time facial recognition and simpler things like
video compression. For a directory of very large jpeg images
Microsoft's image view is unable to keep up with holding down the left
arrow key. You still think optimization is unimportant?

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

[websnarf]

Keith Thompson wrote:

we******@gmail. com writes:

Nick Keighley wrote:

we******@gmail. com wrote:
> Nick Keighley wrote:
> > we******@gmail. com wrote:
> > > Eric Sosman wrote:
> > > > we******@gmail. com wrote:
> > > > > sp****@gmail.co m wrote:
> > > > >>I didn't read your whole page but had a look at the table in the
> > > > >>section "Strictly for beginners". Can you explain why would
> > > > >>"x = y << 3" be faster than "x = y * 8" ? [...]
> >
> > I was using a compiler in the '80s that was smart enough to replace * 8
> > with << 3. Stuff like this in the source just obscures the intent.
>
> Explain how it obscures the intent.

obviously we are not on the same wavelength. If I want to multiply by 8
I write *8. Why would I do anything else? (unless measurement showed
<<3 was faster *and* this line of code needed to be faster).
If shifting by 3 is the *same* as multiplying by 8, then how is
shifting by 8 "doing something else" other than multiplying by 8? Tell
me, why do you think C includes a << operation?

For bitwise shifting, of course. Why do you think C includes a "*"
operation? Even if they happen to be mathematically equivalent in
certain cases, they're *conceptually* very different.

Ignoring pedantry -- no they are *NOT*. This is like your belief that
a == 0 is conceptually different from 0 == a. If they are the same,
then they are the same. They don't gain a difference, conceptual or
otherwise, because they have a syntactical difference.
If I want something to be 8 times as big, I'll multiply it by 8.
(Tomorrow I might decide I want it to be 9 times as big.)

If I want to shift the bits of an object left by 3 positions I'll use
"<< 3".
So if I want to get a tan, should I sit out in the sun or should I go
to a tanning machine? Afterall its a *TAN* -- shouldn't I *USE* the
sun? But the tanning machine *ALSO* gives me a tan ... how do I
decide?

If you see this:

(x << c) * 8, or (x * 8) << c, or (x * 8) & 3

Does your decision still make as much sense?

If the tanning salon is around the corner and I live in Seattle, then
doesn't that help me decide?

Now, if I am concerned about performance, and I know that some
compilers might not catch the *8 -> << 3 transformation, then doesn't
*that* say something about the decision I make?
[...] If shifting is really what I want to do here, I might decide
tomorrow that I want to shift by 4 bits; it's unlikely I'll decide I
want to multiply by 9.

I'll use the multiplication if it expresses what I want to do. If a
shift happens to be more efficient, I'll trust the compile to generate
a shift instruction -- or not to if it can't prove that it's really
equivalent, or if a multiplication is just as fast as a shift.

What if y is negative? (Answer: undefined behavior.)
Not on a serious machine. That the standard chooses to take this
position is not surprising, but not really relevant either. Here's a
challenge for you: Name 3 platforms with a total install base > 1000
independent machines where this is an issue.
[...] What if y is floating-point? (Answer: you can't apply "<<" to floating-point
values.)
Or what if y is a string? That's pretty deep.
Finally, even assuming that y is unsigned or positive, what happens if
I replace this:
x = y * 8 + z;
by this:
x = y << 3 + z;
? The answer depends on the relative precedence of the "*", "+", and
"<<" operators. I don't know about you, but I had to look it up;
That's because you left off the parentheses. C's order of precidence
is stupid, and leaving off the parentheses should be a violation of
every coding guideline in existence. You can't use ioccc techniques to
defend your inability to see an equivalence.
[...] even
if you have all the operator precedences memorized, the next person
who reads your code probably hasn't.

Now, please explain how
x = y << 3;
is *better* than
x = y * 8;
particularly for beginners. (Answer: it isn't.)

Why would I do that? You're not about to pull a CBF here, and drag my
platform-dependent not-C language focused webpages into here and claim
I am teaching C with them are you?

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

[jacob navia]

we******@gmail. com a écrit :

jacob navia wrote:

I agree with Mr Thomson here.

1) In modern Pentium processors, the (very clever) Intel designers
took the barrel shifter (that was there since the 8086) away.
This means that a <<= 3 is SLOWER than a *= 8.

You mean the abortifact called the Pentium 4? First of all, its not
*SLOWER*, its about the same speed (the hardware operations I mean).
Second of all, the Pentium 4 is now officially obsolete, and the "slow
shifter" decision has been recinded.

I thought it would arrive anyway, so it is good news.

The new Israeli designed cores
from Intel have gone back to fast shifting. Implicit in my standing
behind my recommendation of continuing to use left shift instead of
multiplication when you can was a prediction that this would happen.
(It appears, I was right.) And finally, what do you say about AMD's
Opteron cores? They include 3 parallel single cycle integer shifters.

Modern processors are highly complex beasts, and unless you
study the subject matter you risk to do the wrong decisions.

You know who you are talking to right?

Excuse me sir. Should I speak to you as "your holiness" maybe ? :-)

2) All C compilers will do the optimization a *= 8; with a shift
if a is unsigned, AND the processor warrants it. Lcc-win32
does this always since I was too lazy to modify the compiler
to follow that brain-dead Intel decision. After measuring
the actual code I could not find any difference even after
several billion tries, so I think... well forget it :-)

On the P4? Like I said, the reason why you measured no difference, is
because there is no difference. However, for Opterons, its still 0.33
- 1.0 clocks versus 3 clocks.

3) Most of this micro optimizations will not speed up a program.
A better algorithm, and above all a better DATA LAYOUT will
improve the program.

This sounds like a blanket statement, that is inherently inconsistent.
Once you *have* this better algorithm, are you still sure that
micro-optimizations wont work? This is a classic line typically spoken
by people who are actually bad at both strategies.

Thanks a lot for this compliment your holiness...

But may I add a small (final) comment?

You have the bad habit (that many people here share with you, relax)
of always expressing your views in the most polemic form, so your
"opponents" (that actually are people that maybe disagree with you
in some detail point, nothing more) are depicted as ignorants,
stupid know nothing folks.

Let it be, as Lennon would say. You need this form of discussion,
it is good for your ego... Let it be.

Personally, I respect people and their views, so it is impossible
for me to communicate correctly with someone that has this
"I am always the best" attitude. Sorry.