Hundreds of cases in a switch, optimization?

[He Shiming]

Hi,

I just wrote a function that has over 200 "cases" wrapped in a "switch"
statement. I'm wondering if there are performance issues in such
implementation. Do I need to optimize it some way?

In terms of generated machine code, how does hundreds of cases in a switch
differ from hundreds of if-elses? Do compilers or processors do any
optimization on such structured code? Do I need to worry about the
performance, usually?

Thanks,

 

[Alawna]

there should be no difference between if-elsses and switches in terms
of performance. switches are only easier to read. ie, they produce
identical machine code.
by the way, i am talking from a pascal point of view but it should
also apply to C . Waiting like you for C guys to answer.

 

[He Shiming]

Well, thanks for the information anyway.

 

[Minti]

Hi,

I just wrote a function that has over 200 "cases" wrapped in a "switch"
statement. I'm wondering if there are performance issues in such
implementation. Do I need to optimize it some way?

In terms of generated machine code, how does hundreds of cases in a switch
differ from hundreds of if-elses? Do compilers or processors do any
optimization on such structured code? Do I need to worry about the
performance, usually?

Well, try to write these hundreds of switch statements using if-else's
and see if you have it easy that way.

I have seen a lot of code with 100's of switch statements in many cases
it is just not _possible_ to apply any other strategy. However, as far
as performance is concerned try to keep the cases that you feel are
most likely to occur at the beginning of the switch block.

 

[Christian Bau]

Hi,

I just wrote a function that has over 200 "cases" wrapped in a "switch"
statement. I'm wondering if there are performance issues in such
implementation. Do I need to optimize it some way?

How could I know? Does it run fast enough? Does anyone complain that it
is too slow? Have you measured how long it takes?

In terms of generated machine code, how does hundreds of cases in a switch
differ from hundreds of if-elses? Do compilers or processors do any
optimization on such structured code? Do I need to worry about the
performance, usually?

It is time to read the documentation for your compiler and find out how
to show the assembler code that it produces. Find out, then have a look
at the code.

Since compilers are around over fourty years, there are the following
possibilities:

a. There is no way to do a switch statement of 200 cases faster than
200 if's.
b. It is possible to do a switch statement of 200 cases faster than
200 if's, but compiler writers for the last 40 years have been too
stupid or too lazy to implement it.
c. It's done much faster, and has been done that way for years.

Guess a, b or c.

 

[Walter Roberson]

:there should be no difference between if-elsses and switches in terms
f performance. switches are only easier to read. ie, they produce
:identical machine code.
:by the way, i am talking from a pascal point of view but it should
:also apply to C . Waiting like you for C guys to answer.

When you look at it from a pascal point of view... you are incorrect,
at least in some implementations. I used to work with a Pascal
compiler which would do "finite-difference" methods on the switch
values in order to detect "runs" of labels, and would convert
those runs into table indices. Labels were internally
re-ordered at need.

Whether or not "runs" are used, when the case values are
constants and there are no "fall through" locations
(i.e., each case ends with a 'break' instead of continuing
on to the next label becasue no 'break' was specified),
then the compiler can sort the labels and drop in a binary
search over the values -- finding the right section of
code in log2(N) comparisions instead of N-1 comparisions.

 

[He Shiming]

Well, I'll have to do a performance profile (which is kinda complicated) if
I were to find out about what cases are being accessed most frequently. I
can't tell because there are hundreds of them.

So, is it true that to get to the last "case" of a switch block, the
processor needs to iterate through the whole list every time? If so, I could
split 200 cases into like 5 unit and do a value-comparision before entering
the switch. But is it worth it to do so? (especially when there are 200
cases).

 

[forayer]

Hi,

I just wrote a function that has over 200 "cases" wrapped in a "switch"
statement. I'm wondering if there are performance issues in such
implementation. Do I need to optimize it some way?

to my understandin, switch-cases n if-thens evaluate each expr until a
match is found (if no match is found then 'default' or the last else is
used). one way 2 optimize such irrelevant checkin wud b 2 use an arrays
of funtion ptrs. but of course, ur switch-case expr shud b sumthin like
case 1,case 2..., or it shud b possible to hash the cases to such a
range of numbers.

cheers.

 

[DeltaOne]

Switches cases most often use jump tables and evaluate where as the if
else do not use them. Thus switches may give an illusion of being fast
but its not necessary,the only thing is that compilation may be a bit
fast not the execution. It asically depends on how intelligent the
compiler is. If its a good compiler they may be converted to the same
amount of c code or c++ code what ever.

And if you want ptimiztion then dont rely only on C++ compiler you can
do some on your own by grouping something or even re ordering the
structures.

 

[pete]

If the cases are all consecutive integers,
then you could rewrite it as functions
with an array of function pointers
to just index the correct function in one shot.

 

[Jean-Claude Arbaut]

Le 19/06/2005 11:08, dans
(e-mail address removed), « forayer »

to my understandin, switch-cases n if-thens evaluate each expr until a
match is found (if no match is found then 'default' or the last else is
used). one way 2 optimize such irrelevant checkin wud b 2 use an arrays
of funtion ptrs. but of course, ur switch-case expr shud b sumthin like
case 1,case 2..., or it shud b possible to hash the cases to such a
range of numbers.

cheers.

<OT>
Please avoid "b" "n" "2" "ur" and such things.
They make reading rather inconvenient (at least for a french reader) ;-)
</OT>

 

[forayer]

<OT>
Please avoid "b" "n" "2" "ur" and such things.
They make reading rather inconvenient (at least for a french reader) ;-)
</OT>

i'll keep that in mind from now on, and i do apologize for any
inconvenience caused to anyone. sorry.

cheers,
forayer

 

[Jean-Claude Arbaut]

Le 19/06/2005 13:07, dans
(e-mail address removed), « forayer »

i'll keep that in mind from now on, and i do apologize for any
inconvenience caused to anyone. sorry.

Well, I do apologize for my own english mistakes ;-)

 

[Christian Bau]

Well, try to write these hundreds of switch statements using if-else's
and see if you have it easy that way.

I have seen a lot of code with 100's of switch statements in many cases
it is just not _possible_ to apply any other strategy. However, as far
as performance is concerned try to keep the cases that you feel are
most likely to occur at the beginning of the switch block.

If you are concerned about execution speed, then
Look at the assembler code.
Measure the execution time.
Learn what makes it fast

But only if
Making it faster would actually help somebody.

In my experience, the biggest performance gains can be achieved by
finding the bits in your code that are not just slow but completely
braindamaged slow, and fixing them. Not the kind where you ask "what is
faster: Switch or If", but the kind where you ask yourself "how could
anyone be so stupid to write code that way? "

Learn to find these bits of code and learn to use tools to find them.

 

[CBFalconer]

there should be no difference between if-elsses and switches in
terms of performance. switches are only easier to read. ie, they
produce identical machine code.

Not necessarily so. An if else has to test everything in turn. A
switch (or CASE in Pascal) can (but may not) use a transfer table,
in which case there is no additional overhead to adding cases.

--
Some useful references about C:
<http://www.ungerhu.com/jxh/clc.welcome.txt>
<http://www.eskimo.com/~scs/C-faq/top.html>
<http://benpfaff.org/writings/clc/off-topic.html>
<http://anubis.dkuug.dk/jtc1/sc22/wg14/www/docs/n869/> (C99)
<http://www.dinkumware.com/refxc.html> (C-library}
<http://gcc.gnu.org/onlinedocs/> (GNU docs)

 

[He Shiming]

Oh that's definitely a great idea, I'll try, thanks.

 

[Lawrence Kirby]

Hi,

I just wrote a function that has over 200 "cases" wrapped in a "switch"
statement. I'm wondering if there are performance issues in such
implementation. Do I need to optimize it some way?

If it runs too slowly then you should probably look to optimise it in some
way.

In terms of generated machine code, how does hundreds of cases in a switch
differ from hundreds of if-elses?

However the compiler chooses. Most reasonable compilers will attempt to
optimise switch statement using jump tables or range division (or a
combination) where appropriate. How efeectively that can be done depends
in the case values you are using.

It is also possible for a compiler to optimise a chain of if else
statements (e.g. one that tests a variable against various values) in a
similar way so you can't assume that that would be less efficient.

Do compilers or processors do any
optimization on such structured code? Do I need to worry about the
performance, usually?

It is reasonable to assume that compilers will deal with switch statements
sensibly, and only worry about it, e.g. by looking at the assembly it
produces, if you suspect a compiler isn't doing what you want.

Lawrence

 

[He Shiming]

Alrighty, I got the picture, thanks.

 

[Christian Bau]

Well, I'll have to do a performance profile (which is kinda complicated) if
I were to find out about what cases are being accessed most frequently. I
can't tell because there are hundreds of them.

So, is it true that to get to the last "case" of a switch block, the
processor needs to iterate through the whole list every time? If so, I could
split 200 cases into like 5 unit and do a value-comparision before entering
the switch. But is it worth it to do so? (especially when there are 200
cases).

One more time: Look at the assembler code if it matters.


(And in most compilers that you will ever see it doesn't make the
slightest difference how you arrange your labels. In some especially
clever Java implementation, it may happen that the most common case
executes fastest - no matter where you put it. )

 

[Christian Bau]

to my understandin, switch-cases n if-thens evaluate each expr until a
match is found (if no match is found then 'default' or the last else is
used). one way 2 optimize such irrelevant checkin wud b 2 use an arrays
of funtion ptrs. but of course, ur switch-case expr shud b sumthin like
case 1,case 2..., or it shud b possible to hash the cases to such a
range of numbers.

Did you verify your understanding by measuring the actual speed or
looking at code that was generated? I don't think so.