switch statement performance
pops
Recently a co-worker of mine started bashing the use of switch
statements in our code. Confused by this, as I had always thought
switch statements were made into very efficient lookup tables by the
compiler, I asked him why. His response was that the compiler will
build a table if the case values are close enough to build the table.
If not he said that the compiler ends up building the object code like
an if/else block.
First is there any truth to this?
Second, how much of a peformance impact does using a switch on a
relatively large number of cases have?
Third, is there any rules of thumb on when/how to know if you have too
much and should begin looking for alternative methods of determining
code execution based on a variable or variable set?
Fourth, what if any are the alternatives?
Thanks,
pops
Ben Pfaff
> Recently a co-worker of mine started bashing the use of switch
> statements in our code. Confused by this, as I had always thought
> switch statements were made into very efficient lookup tables by the
> compiler, I asked him why. His response was that the compiler will
> build a table if the case values are close enough to build the table.
> If not he said that the compiler ends up building the object code like
> an if/else block.
> First is there any truth to this?
>
It depends on your compiler. Your description is pretty much how
GCC works though: dense-enough sets of values are looked up in a
table; otherwise it uses binary search.
> Second, how much of a peformance impact does using a switch on a
> relatively large number of cases have?
Compared to what?
> Third, is there any rules of thumb on when/how to know if you have too
> much and should begin looking for alternative methods of determining
> code execution based on a variable or variable set?
If the code's too slow, consider alternatives. Otherwise, leave
it in.
> Fourth, what if any are the alternatives?
Well, if there's a faster choice than a binary search or a lookup
table, try it.
This is one of those questions which is almost impossible to
answer in the general case. There are just too many variables
(compiler, CPU, operating system, variable type, distribution of
values, ...) to be able to say much that's useful.
--
"This is a wonderful answer.
It's off-topic, it's incorrect, and it doesn't answer the question."
--Richard Heathfield
Alan Morgan
pops <po...@pops.com> wrote:
>Hi all,
>
>Recently a co-worker of mine started bashing the use of switch
>statements in our code. Confused by this, as I had always thought
>switch statements were made into very efficient lookup tables by the
>compiler, I asked him why. His response was that the compiler will
>build a table if the case values are close enough to build the table.
>If not he said that the compiler ends up building the object code like
>an if/else block.
Almost every statement that starts "The compiler does ...." is false.
There are a number of tricks that compilers can do on switch statements
including a lookup table, binary search, hash table, simple if-then-else,
and (it wouldn't surprise me) consulting the entrails of a manticore.
>First is there any truth to this?
>
>Second, how much of a peformance impact does using a switch on a
>relatively large number of cases have?
As opposed to what?
Alan
pops
wrote:
As opposed to building the hash tables, binary search trees, etc on
your own. It seems like the amount of work that would go into
building those things would far outweigh the speed improvement one
could gain coding it yourself in all but the most severe of
conditions.
>
>Alan
Dann Corbit
news:39c13f5f...@news.mdsn1.wi.home.com...
> Hi all,
>
> Recently a co-worker of mine started bashing the use of switch
> statements in our code. Confused by this, as I had always thought
> switch statements were made into very efficient lookup tables by the
> compiler, I asked him why. His response was that the compiler will
> build a table if the case values are close enough to build the table.
> If not he said that the compiler ends up building the object code like
> an if/else block.
>
There might be for some particular compiler. But there are no guarantees.
> Second, how much of a peformance impact does using a switch on a
> relatively large number of cases have?
Microscopic.
> Third, is there any rules of thumb on when/how to know if you have too
> much and should begin looking for alternative methods of determining
> code execution based on a variable or variable set?
First rule of optimization: "Don't do it."
Second rule (for experts only): "Don't do it yet."
Anyone who is asking this question should not be trying to do the things you
describe. And I really, really mean it.
> Fourth, what if any are the alternatives?
There are an infinite number of alternatives.
That is neither here nor there.
Write the code that is clear and communicates your purpose most accurately.
Trying tweaky little things to get speedups is beyond amateurish -- it's
just plain stupid.
--
C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
"The C-FAQ Book" ISBN 0-201-84519-9
C.A.P. Newsgroup http://www.dejanews.com/~c_a_p
C.A.P. FAQ: ftp://38.168.214.175/pub/Chess%20Analysis%20Project%20FAQ.htm
pops
<dco...@solutionsiq.com> wrote:
>"pops" <po...@pops.com> wrote in message
>news:39c13f5f...@news.mdsn1.wi.home.com...
>> Hi all,
>>
>> Recently a co-worker of mine started bashing the use of switch
>> statements in our code. Confused by this, as I had always thought
>> switch statements were made into very efficient lookup tables by the
>> compiler, I asked him why. His response was that the compiler will
>> build a table if the case values are close enough to build the table.
>> If not he said that the compiler ends up building the object code like
>> an if/else block.
>>
>> First is there any truth to this?
>
>There might be for some particular compiler. But there are no guarantees.
>
>> Second, how much of a peformance impact does using a switch on a
>> relatively large number of cases have?
>
>Microscopic.
>
>> Third, is there any rules of thumb on when/how to know if you have too
>> much and should begin looking for alternative methods of determining
>> code execution based on a variable or variable set?
>
>First rule of optimization: "Don't do it."
>Second rule (for experts only): "Don't do it yet."
>
>Anyone who is asking this question should not be trying to do the things you
>describe. And I really, really mean it.
Thanks for the post. I have personally always followed the two rules
above which is why I decided to ask here to see if my knowledge on the
subject was either accurate or outdated.
I've always gone with the saying "You can't be the compiler at it's
own game" ie. Don't try building things that try to do things more
efficiently than the compiler would.
>
>> Fourth, what if any are the alternatives?
>
>There are an infinite number of alternatives.
>
>That is neither here nor there.
>Write the code that is clear and communicates your purpose most accurately.
>Trying tweaky little things to get speedups is beyond amateurish -- it's
>just plain stupid.
I agree. I was trolling for ammo to knock down my co-workers
argument. He's pushing this philosophy onto other developers and I
think it's insane. =-)
pops
"You can't beat the compiler at it's own game"
Now if only I could type, spell and use grammar correctly.
Ben Pfaff
> On Thu, 14 Sep 2000 21:58:32 GMT, po...@pops.com (pops) wrote:
> >I've always gone with the saying "You can't be the compiler at it's
> >own game" ie. Don't try building things that try to do things more
> >efficiently than the compiler would.
>
> "You can't beat the compiler at it's own game"
No. "You can't beat the compiler at its own game."
--
"I ran it on my DeathStation 9000 and demons flew out of my nose." --Kaz
Gunnar Andersson
On Thu, 14 Sep 2000, Dann Corbit wrote:
> That is neither here nor there.
> Write the code that is clear and communicates your purpose most accurately.
> Trying tweaky little things to get speedups is beyond amateurish -- it's
> just plain stupid.
Would you also post this message on the Computer Chess Board at ICDchess,
Dann? :)
/ Gunnar
Christian Bau
<Pine.SUN.3.91N2x.10009...@byse.nada.kth.se>, Gunnar
Andersson <gun...@nada.kth.se> wrote:
Amateurs try tweaky little things to save nanoseconds.
Professionals save microseconds :-)
Tor Rustad
> On Thu, 14 Sep 2000 14:44:41 -0700, "Dann Corbit"
> <dco...@solutionsiq.com> wrote:
<snip>
> >First rule of optimization: "Don't do it."
> >Second rule (for experts only): "Don't do it yet."
There are other important rules aswell, one is
Third rule: Don't do it, unless you really know what you are doing.
> >That is neither here nor there.
> >Write the code that is clear and communicates your purpose most accurately.
> >Trying tweaky little things to get speedups is beyond amateurish -- it's
> >just plain stupid.
>
> I agree. I was trolling for ammo to knock down my co-workers
> argument. He's pushing this philosophy onto other developers and I
> think it's insane. =-)
Well, there is more ammo in c.l.c, read the thread "Optimization for speed
question", which BTW received many posts this week.
--
Tor
glen herrmannsfeldt
(snip regarding efficiency of switch statements)
>>> Third, is there any rules of thumb on when/how to know if you have too
>>> much and should begin looking for alternative methods of determining
>>> code execution based on a variable or variable set?
>>
>>First rule of optimization: "Don't do it."
>>Second rule (for experts only): "Don't do it yet."
While these are probably true, one should try to avoid obviously
unoptimal coding techniques. If one doesn't know how fast something
is, it is hard to avoid. I found out not so long ago about how slow
strncpy can be. I used to use it for copying strings into buffers
what I didn't want to overflow. I happened to have a 1000000 character
buffer and a loop copying small strings into it. I didn't realize at
the time that strncpy fills out the rest of the buffer with '\0' all
the way to the end. My program was running thousands of times slower
than it needed to because of this small feature.
In another I was using strcat in a loop to accumulate a long string
in a buffer. The time for such a loop is quadratic in input size,
and again I was filling a 1000000 character buffer. Again it may
have changed the run time by a factor of 1000.
In both these cases the obvious algorithm might be 1000 times slower
than a slightly different, slightly less obvious algorithm.
>>Anyone who is asking this question should not be trying to do the things you
>>describe. And I really, really mean it.
I disagree. If he didn't ask he wouldn't know that it didn't matter.
I hope that compilers generate either a jump table or binary search,
but some may generate a linear search. If the switch has thousands of
cases and his compiler generates a linear search, it should probably
be changed, if speed is at all important.
>Thanks for the post. I have personally always followed the two rules
>above which is why I decided to ask here to see if my knowledge on the
>subject was either accurate or outdated.
>I've always gone with the saying "You can't be the compiler at it's
>own game" ie. Don't try building things that try to do things more
>efficiently than the compiler would.
This is true if you do things that the compiler writers expected.
They may not expect 1000 case switch statements, and may not code
for them efficiently. If you profile the code, find where it is
spending most of the time, and then decide if it makes sense. If
not, question the compiled code.
-- glen