Alternate to switch case statement

[Satya]

Hi everyone,

This is the first time iam posting excuse me if iam making any
mistake. My question is iam using a switch case statement in which i
have around 100 case statements to compare. so just curious to find
out is it effective to use this method?? or is there is any other
alternative method present so that execution time and code size can be
reduced??

Thanks in advance.

Regards,
Satya

[Gordon Burditt]

Re: Alternate to switch case statement

>This is the first time iam posting excuse me if iam making any

>mistake. My question is iam using a switch case statement in which i
>have around 100 case statements to compare. so just curious to find
>out is it effective to use this method?? or is there is any other
>alternative method present so that execution time and code size can be
>reduced??

Make up your mind: which do you want to reduce, execution time or code
size? Usually, you reduce one at the expense of the other.

With that many cases, the compiler might use a binary search approach
which is equivalent to a big nested bunch of if/else. It can probably
do this with a maximum of 7 comparisons. Or, if the case values are
consecutive or nearly so, it could use a branch table, which might be
equivalent to the execution time of about 3 comparisons.

The compiler does not know the relative frequency of the case values
it will encounter. If you do, you might manage to beat its code
on average by checking the most common values first. Your code will be
messy and you should leave behind detailed notes on what you were
optimizing for should someone have to add or delete cases.

[ksashtekar@gmail.com]

Re: Alternate to switch case statement

On Sep 11, 8:18 am, Satya <mailtodsre...@ gmail.comwrote:

Hi everyone,
>
This is the first time iam posting excuse me if iam making any
mistake. My question is iam using a switch case statement in which i
have around 100 case statements to compare. so just curious to find
out is it effective to use this method?? or is there is any other
alternative method present so that execution time and code size can be
reduced??
>
Thanks in advance.
>
Regards,
Satya

I think the best option for fastest execution would be to make an
array of pointers pointing to functions for each case.
Your can then index into this array and thus call the corresponding
function directly.

Kaustubh

[sh.vipin@gmail.com]

Re: Alternate to switch case statement

>iam using a switch case statement in which i

have around 100 case statements to compare.

it means that you have 100 constant values to compare against one
variable. In such cases, if else statement itself are converted
to switch statements if possible. but it should be confirmed from the
compiler group. comp.lang.gcc/g++ are two options

Also, are all the conditions exclusive i.e. are you putting
break statement in all the 100 cases or there are some fall through
also.
in both the cases it will be good to organize the code in a better way
yourself.

for example the following code

switch(i){
case 1: /* some code */ break;
case 2: /* some code */ break;
case 3: /* some code */ breask;
case 4: /* some code */ breask;
..
..
..
..
case 100: /* some code */ breask;


}

can be broken into
following tree to have less comparisons.

if(i <10){
switch(i){
case 1:
case 2:
..
..
}

}else if (i < 30){
switch(i){
case 10:
case 11:
..
..
case 29:
}
}else if (i < 50){
}else if (i<70){
}else{
switch(i){
case 70:
case 71:
..
..
case 100:
}
}



check if compiler does that automatically for you. you can do it in
two ways
1. go and ask in some compiler group comp.lang.gcc
2. check the assembly code generated in such case using gcc -S option

-- vIpIn

[boB]

Re: Alternate to switch case statement

On Wed, 10 Sep 2008 20:18:32 -0700 (PDT), Satya
<mailtodsreddy@ gmail.comwrote:

>Hi everyone,
>
>This is the first time iam posting excuse me if iam making any
>mistake. My question is iam using a switch case statement in which i
>have around 100 case statements to compare. so just curious to find
>out is it effective to use this method?? or is there is any other
>alternative method present so that execution time and code size can be
>reduced??
>
>Thanks in advance.
>
>Regards,
>Satya

This is where I would consider using a function pointer or a lookup
table to get to the function.
boB

[Flash Gordon]

Re: Alternate to switch case statement

ksashtekar@gmai l.com wrote, On 11/09/08 06:17:

On Sep 11, 8:18 am, Satya <mailtodsre...@ gmail.comwrote:

>Hi everyone,
>>
>This is the first time iam posting excuse me if iam making any
>mistake. My question is iam using a switch case statement in which i
>have around 100 case statements to compare. so just curious to find
>out is it effective to use this method?? or is there is any other
>alternative method present so that execution time and code size can be
>reduced??

<snip>

I think the best option for fastest execution would be to make an
array of pointers pointing to functions for each case.
Your can then index into this array and thus call the corresponding
function directly.

There is absolutely no guarantee that this will be faster. You don't
know what processor the OP is using, what compiler, how expensive
function calls are, how expensive a branch table is (which the compiler
could use) or anything else that would tell you.

To the OP, write the code to be clear (probably a switch), get it right,
then if you have performance problems *measure* to see if this is where
the problem is, then start looking at how to optimise it. However,
remember that using a switch is pretty common so you compiler probably
has a number of interesting strategies to optimise them when you enable
its optimiser.
--
Flash Gordon

[Flash Gordon]

Re: Alternate to switch case statement

sh.vipin@gmail. com wrote, On 11/09/08 07:00:

>iam using a switch case statement in which i
>have around 100 case statements to compare.

<snip>

check if compiler does that automatically for you. you can do it in
two ways
1. go and ask in some compiler group comp.lang.gcc
2. check the assembly code generated in such case using gcc -S option

What makes you think the OP is using gcc? What makes you think that
other compilers work the same was as gcc or use the same options? There
are a number of other compilers.

Your advice to check if the compiler is doing the optimising is,
however, good advice. Compiler writers have spent a lot of effort on
optimisers.
--
Flash Gordon

[sh.vipin@gmail.com]

Re: Alternate to switch case statement

This is where I would consider using a function pointer or a lookup
table to get to the function.
boB

well it's a good solution but again depends on the range of constants
what if "i" was not from 1 to 100 but had some random values in
between 1 and 30000

in my opinion array of pointers to function , if at all gives
advantage (considering code in every case is big enough to make sense
to add additional function calls + variables on which it has to work
are manageable to pass as arguments ), gives only when constants are
in some range else you will have sparse entires in array table

--
vIpIn

[sh.vipin@gmail.com]

Re: Alternate to switch case statement

What makes you think the OP is using gcc? What makes you think that
other compilers work the same was as gcc or use the same options? There
are a number of other compilers.

may be my language has been little ambiguous there. All, I wanted to
say was
- Check in general compilers group if they do such
optimizations(b reaking case statements in Binary Search tree kind of
structure) automatically.
- You may also think of looking for Assembly output of compiler you
are using

- In case you opt for "gcc" as compiler , group for query is
comp.lang.c and gcc -S option dumps the assembly output. By default
there is no optimization in gcc so use -O3 option for checking
optimizatio being done

I am not aware of how to do it with Visual Studio 2005 or Intel
compilers but there must be some ways definitely

--
vIpIn

[James Kuyper]

Re: Alternate to switch case statement

boB wrote:

On Wed, 10 Sep 2008 20:18:32 -0700 (PDT), Satya
<mailtodsreddy@ gmail.comwrote:
>

>Hi everyone,
>>
>This is the first time iam posting excuse me if iam making any
>mistake. My question is iam using a switch case statement in which i
>have around 100 case statements to compare. so just curious to find
>out is it effective to use this method?? or is there is any other
>alternative method present so that execution time and code size can be
>reduced??
>>
>Thanks in advance.
>>
>Regards,
>Satya

>
This is where I would consider using a function pointer or a lookup
table to get to the function.

It depends upon the compiler whether or not this is even worthwhile. I
remember reading the documentation about "switch" for some compiler
(it's probably the one I use most frequently, but I'm not sure).
According to that documentation, the compiler selects which one of three
different strategies to use, depending upon the number of case
statements and the range of values involved. One of the strategies was
equivalent to a long string of if-else statements. Another strategy was
equivalent to using a lookup table. The third one would use the argument
of switch to calculate the address of the instruction it should jump to
next.

Don't waste your time worrying about optimizations your compiler can do
for you. Concentrate on the ones it can't handle correctly without your
help.

[christian.bau]

Re: Alternate to switch case statement

On Sep 11, 4:18 am, Satya <mailtodsre...@ gmail.comwrote:

This is the first time iam posting excuse me if iam making any
mistake. My question is iam using a switch case statement in which i
have around 100 case statements to compare. so just curious to find
out is it effective to use this method?? or is there is any other
alternative method present so that execution time and code size can be
reduced??

It is very, very likely that the people who wrote the compiler that
you are using spent a lot of time to produce the best possible code
for switch statements. The compiler will look at the switch statement,
make a list of all the different case values that you are using, and
use different strategies depending on what these values look like. It
will also take into account how your processor works and what
execution time different kinds of code take; if your compiler has a
setting that lets you choose between fastest possible code and
smallest possible code then it will take that into account as well. So
a switch statement will give you the best possible code for that
task.

Someone else advised you to use an array of function pointers. Well,
that will make your source code a lot bigger and more complicated
(unless you had a switch statement where every case was handled by a
function call with identical parameters and nothing else). And if this
method was indeed faster, then the compiler writer would know it and
produce that kind of code for you. You are always best off if you
write code that uses no tricks but does exactly what you want to do in
the simplest possible way, just the same plain old code that everyone
else uses, so the compiler can find patterns in your code that the
compiler writers know and can optimize these patterns.

[Keith Thompson]

Re: Alternate to switch case statement

sh.vipin@gmail. com writes:
[...]

- In case you opt for "gcc" as compiler , group for query is
comp.lang.c and gcc -S option dumps the assembly output. By default
there is no optimization in gcc so use -O3 option for checking
optimizatio being done

[...]

No, the correct newsgroup for gcc is gnu.gcc.help. This group,
comp.lang.c, discusses the language (cue the trolls whining that they
can discuss anything they want anywhere they like). And
comp.lang.gcc, which you mentioned earlier, doesn't exist.

--
Keith Thompson (The_Other_Keit h) kst-u@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Keith Thompson]

Re: Alternate to switch case statement

sh.vipin@gmail. com writes:

>>iam using a switch case statement in which i
>have around 100 case statements to compare.

>
it means that you have 100 constant values to compare against one
variable. In such cases, if else statement itself are converted
to switch statements if possible. but it should be confirmed from the
compiler group. comp.lang.gcc/g++ are two options
>
Also, are all the conditions exclusive i.e. are you putting
break statement in all the 100 cases or there are some fall through
also.
in both the cases it will be good to organize the code in a better way
yourself.
>
for example the following code
>
switch(i){
case 1: /* some code */ break;
case 2: /* some code */ break;
case 3: /* some code */ breask;
case 4: /* some code */ breask;
.
.
.
.
case 100: /* some code */ breask;
>
>
}
>
can be broken into
following tree to have less comparisons.
>
if(i <10){
switch(i){
case 1:
case 2:
.
.
}

[...]

}else if (i < 50){

[...]

}
}

[...]

You're assuming that the generated code for the simple 100-case switch
statement performs up to 100 comparisons. A switch statement,
particularly when the values are tightly bunched, is typically
implemented as a jump table; the value of the expression is checked to
see whether it's within the range, and then used as an index for
something like a "computed goto".

Breaking up the switch statement into a sequence of if/else statements
and subsidiary switch statements is very likely to make the generated
code bigger and slower, and is certain to make it more difficult to
read and maintain.

Premature optimization is the root of all evil. Write code that's
clear, straightforward , and correct. As you're writing it, keep
efficiency concerns in mind, but don't obsess about them; for example,
don't use a if/else chain when a switch will do the job, and don't use
a O(N**2) algorithm when an O(N) algorithm is available. And don't
worry about low-level micro-optimizations; optimizing compilers are
good at handling those for you.

If the resulting code is fast enough, you're done. If it isn't,
measure it, figure out where the bottlenecks are, and consider doing a
few ugly micro-optimizations *if necessary*.

--
Keith Thompson (The_Other_Keit h) kst-u@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[Flash Gordon]

Re: Alternate to switch case statement

sh.vipin@gmail. com wrote, On 11/09/08 11:01:

Please leave in the attribution lines for quoted material, i.e. the bit
that says who wrote what such as the line above.

>What makes you think the OP is using gcc? What makes you think that
>other compilers work the same was as gcc or use the same options? There
>are a number of other compilers.

>
may be my language has been little ambiguous there. All, I wanted to
say was

<snip reasonable stuff>

I am not aware of how to do it with Visual Studio 2005 or Intel
compilers but there must be some ways definitely

I am pretty sure that most compilers provide a way, but far too many
compilers exist for me to be certain about all of them.

To me your post read as if you were assuming all the world is gcc, but I
appreciate that this was not how you intended it.
--
Flash Gordon