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

 

[ksashtekar]

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]

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]

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]

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]

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.

 

[sh.vipin]

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

 

[sh.vipin]

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(breaking 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

 

[James Kuyper]

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.

 

[Keith Thompson]

- 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.

 

[Flash Gordon]

(e-mail address removed) 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.

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

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.

 

[Keith Thompson]

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*.