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,
--
He Shiming
65  6590 
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.
Well, thanks for the information anyway.
--
He Shiming
"Alawna" <O.******@gmail.com> wrote in message
news:11*********************@g49g2000cwa.googlegro ups.com... 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 (NOSPAM) wrote: 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.
--
Imanpreet Singh Arora
In article <d9**********@news.yaako.com>,
"He Shiming" <mailbill(NOSPAM)@21cn.com.nospam> wrote: 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.
In article <11*********************@g49g2000cwa.googlegroups. com>,
Alawna <O.******@gmail.com> wrote:
: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.
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.
--
Feep if you love VT-52's.
He Shiming (NOSPAM) wrote: 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.
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).
--
He Shiming
"Minti" <im*******@gmail.com> wrote in message
news:11**********************@g49g2000cwa.googlegr oups.com...
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.
--
Imanpreet Singh Arora
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.
He Shiming wrote: 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.
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.
--
pete
Le 19/06/2005 11:08, dans 11*********************@f14g2000cwb.googlegroups.c om, «*forayer*»
<th********@hotmail.com> a écrit*: 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>
Jean-Claude Arbaut wrote: <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
Le 19/06/2005 13:07, dans 11**********************@g43g2000cwa.googlegroups. com, «*forayer*»
<th********@hotmail.com> a écrit*:
Jean-Claude Arbaut wrote: <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.
Well, I do apologize for my own english mistakes ;-)
In article <11**********************@g49g2000cwa.googlegroups .com>,
"Minti" <im*******@gmail.com> wrote: He Shiming (NOSPAM) wrote: 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.
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.
On Sun, 19 Jun 2005 13:32:14 +0800, He Shiming wrote: 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
Alawna wrote:
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)
Oh that's definitely a great idea, I'll try, thanks.
--
He Shiming
"pete" <pf*****@mindspring.com> wrote in message
news:42***********@mindspring.com... He Shiming wrote:
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.
--
pete
Alrighty, I got the picture, thanks.
--
He Shiming
"DeltaOne" <sh**********@wipro.com> wrote in message
news:11**********************@o13g2000cwo.googlegr oups.com... 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.
In article <d9**********@news.yaako.com>,
"He Shiming" <mailbill(NOSPAM)@21cn.com.nospam> wrote: 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. )
In article <11*********************@f14g2000cwb.googlegroups. com>,
"forayer" <th********@hotmail.com> wrote: He Shiming (NOSPAM) wrote: 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.
Did you verify your understanding by measuring the actual speed or
looking at code that was generated? I don't think so.
In article <d9**********@news.yaako.com>,
"He Shiming" <mailbill(NOSPAM)@21cn.com.nospam> wrote: Oh that's definitely a great idea, I'll try, thanks.
Please. PLEASE. Think about it for a second.
Compilers have been doing this kind of stuff for decades.
If there were any simple method that you could use to replace your
switch statement and make it faster, then your compiler would use it.
Of course, you are always free to spend a few hours writing functions,
setting up an array of function pointers, and so on and so on and the
next guy who will have to maintain your code will be cursing you. Might
be you, anyway.
In article <d9**********@news.yaako.com>,
He Shiming <mailbill(NOSPAM)@21cn.com.nospam> wrote: 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?
Only you can tell us that! Try it and see if it's fast enough.
Obviously your results will depend on the compiler. When I last
looked at this (about 15 years ago), most compilers would generate a
jump table if the values were consecutive or mostly consecutive, and
perhaps generate several jump tables if there were several ranges of
consecutive values. So try to use consecutive values.
If you need to squeeze every last ounce of speed out of it (if, say,
you are implementing some other language with a virtual machine) there
are a number of things that you might do.
- Put in dummy cases to make the values consecutive.
- Bear in mind that switch is defined to do nothing if none of the
cases match, so even with a consecutive range it has to test against
the maximum and minimum. I once hoped that the use of enum
values would help here, but it doesn't because you can assign
"incorrect" values to an enum. Using an unsigned type starting
at zero will let you avoid the minimum test. If you use all
256 values of an 8-bit type there will be no need to check at all.
- If your portability requirements don't prevent it, you could use
an extension such as gcc's which allows you to assign labels to
variables, so instead of using a switch you can use a goto. You
can also (portably) use a table of function pointers but the overhead
of a function call (including loss of local variables) may be worse
than the switch overhead.
- If all else fails, modify the generated assembly code.
And of course, you should only consider any of this if you really need
to!
-- Richard
Jean-Claude Arbaut wrote: <th********@hotmail.com> a écrit :
.... snip ... 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.
<OT>
Please avoid "b" "n" "2" "ur" and such things.
They make reading rather inconvenient (at least for a french reader)
;-) </OT>
Or to an English reader. Their prime effects are to make the
writer appear childish, and to lessen the probability of anyone
reading his or her output.
--
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" <mailbill(NOSPAM)@21cn.com.nospam> wrote 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?
Does the program run too slowly? Normally we are not too interested in how
fast a program executes until it takes more than about a tenth of a second
to respond, which is perceived by the users as instantaneous. If it takes a
second to respond, it may or may not be worth shaving off a tenth of a
second. If it takes ten minutes to respond, it probably is worth while
reducing that time to nine minutes.
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?
Most compilers will try to generate a jump table for a large switch, which
is likely to be faster than an if .. else ladder. However sometimes you can
optimise. let's say you have a databse of millions of customers and are
doing a switch on the code for a title. Approximately half your customers
will be "Mr", about a third will probably be "Mrs", a lesser number "Miss"
and some "Ms" (depending on the characteristics of your customer base). You
will also have a sprinking of "Dr"s, "Sir"s, and if you are lucky a customer
you very much want to keep with the title "Queen".
Now if we arrange the if .. else ladder with "Mr" as the first condition,
"Mrs" as the second, and "Queen" as the last condition, then about half the
time if will evaluate only a single condition. Only once will it go all the
way down the ladder when it finds the title for the Elizabeth Windsor.
This could easily be faster than a switch, but may not be.
Generally you will only get a few percentage points improvement by this type
of micro-optimisation. This may be worth having, but it is usually the last
thing you should try.
Christian Bau wrote: Did you verify your understanding by measuring the actual speed or
looking at code that was generated? I don't think so.
step-by-step execution in a debugger works for me! and yes, the
switch-cases did jump.
forayer.
On Sun, 19 Jun 2005 13:32:14 +0800, He Shiming wrote: 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?
I got curious about this so I decided to see what one compiler did on one
architecture. I chose the simplest kind of test that would be the most
likely to optimised -- consecutive integers from 0 to N. I wrote a script
that made programs of this form:
#include <stdlib.h>
extern int f(int x, int nc);
void use_if_stmt(int n)
{
int x = 0;
while (n--) {
int v = f(n, <nc>);
if (v == 0) x++;
else if (v == 1) x++;
}
}
void use_switch_stmt(int n)
{
int x = 0;
while (n--) {
int v = f(n, <nc>);
switch (v) {
case 0: x++; break;
case 1: x++; break;
}
}
}
int main(int argc, char **argv)
{
int n = argc > 1 ? strtol(argv[1], NULL, 0) : 10000000;
use_if_stmt(n);
use_switch_stmt(n);
return 0;
}
where the number of cases (and "if" choices) could be varied (<nc> gets
replaced by this value as well). The function f could be one of "low",
"spread", or "high" and the resulting code was linked with the following:
int spread(int n, int nc) { return n % nc; }
int low (int n, int nc) { return 0; }
int high (int n, int nc) { return n + nc; }
to simulate the situation where the value to be matched was always the
first ("low"); evenly spread over the range of choices ("spread"); or
higher than the highest case ("high"). The resulting programs where
compiled both with (gcc -O2) and without optimisation. gprof was used to
compare the running times of the two functions "use_if_stmt" and
"use_switch_stmt". I simply calculated the ration of the "if" time
to the "switch" time, so a result of 1 means that they both took
the same time. A value of 5 means the if version took five times
as long as the switch version.
Without optimisation the results were:
N cases all low spread all high
2 0.8 1.1 0.8
20 0.8 1.7 5.5
200 0.9 8.1 66.4
2000 0.9 112.6 3042.0
almost exactly as I would have guessed. When the value being matched is
the first case, "if" is always faster. With 200 cases and all of the
value off the top of the case range, "if" takes 66 times longer.
What surprised me was the optimised numbers:
N cases all low spread all high
2 1.1 0.9 1.0
20 1.3 0.7 0.9
200 1.2 0.9 1.1
2000 0.8 1.1 1.0
I think that is quite impressive!
gcc (GCC) 3.4.3 on Pentium(R) M processor 1.70GHz
--
Ben.
> 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?
If you know something about the range of values you are testing, you can a
binary search-like approach. Of course this system will not be beaten by a
jump table, and with nowadays pipes, caches and what-not, the misses by the
CPU might even make it less efficient, I haven't tested any of it. But what
I am implying, is something like this:
if ( n < SOMEVALUE )
{
switch ( n )
{
// cases go here
}
}
else
{
switch ( n )
{
// remaining cases go here
}
}
You can introduce multiple levels as desired. Of course this may or may not
be faster for your compiler. And it (may) hurt(s) readability a little bit
also.
And as always with optimizing: make sure it _needs_ to be optimized. If the
particular code is only executed rarely and performance is not an issue
otherwise (like for real-time software), it may not be worth the time and
trouble.
Good luck,
--
Martijn http://www.sereneconcepts.nl
> 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.
Would you care to suggest some? I am always on the look-out for
improvements... (if not in speed and resource consumption, in things like
maintainability).
--
Martijn http://www.sereneconcepts.nl
In article <42***********************@news.xs4all.nl>,
"Martijn" <su*********************@hot-remove-mail.com> wrote: 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.
Would you care to suggest some? I am always on the look-out for
improvements... (if not in speed and resource consumption, in things like
maintainability).
Well, lets see... Your compiler's documentation? Does it come with a
debugger, does that have documentation? Does it come with a profiler?
Does that have any documentation?
In article <11********************@o13g2000cwo.googlegroups.c om>,
"forayer" <th********@hotmail.com> wrote: Christian Bau wrote: Did you verify your understanding by measuring the actual speed or
looking at code that was generated? I don't think so.
step-by-step execution in a debugger works for me! and yes, the
switch-cases did jump.
You are saying you use a compiler that will use 200 consecutive
comparisons and conditional branches for a switch statement with 200
cases?
In article <d9**********@nwrdmz02.dmz.ncs.ea.ibs-infra.bt.com>,
"Malcolm" <re*******@btinternet.com> wrote: Now if we arrange the if .. else ladder with "Mr" as the first condition,
"Mrs" as the second, and "Queen" as the last condition, then about half the
time if will evaluate only a single condition. Only once will it go all the
way down the ladder when it finds the title for the Elizabeth Windsor.
This could easily be faster than a switch, but may not be.
Hi Malcolm,
nowadays with good branch prediction and heavy penalties for incorrect
prediction in many processors, this becomes less significant. Most of
the cost is in _incorrectly predicted_ branches, and in a switch-like
situation, most often there will be exactly one incorrectly predicted
branch, no matter what you do. You can reduce the number of correctly
predicted branches in between, but they are less significant.
Christian Bau wrote: You are saying you use a compiler that will use 200 consecutive
comparisons and conditional branches for a switch statement with 200
cases?
no, i meant that the switch statement _didnt_ use 200 comparisions. it
jumped right to the appropriate case. such jumps do make sense for
switch-case structures, but how well can they be compared to an array
of function pointers (assuming that the cases can be easily indexed)?
"Christian Bau" <ch***********@cbau.freeserve.co.uk> wrote Hi Malcolm,
nowadays with good branch prediction and heavy penalties for incorrect
prediction in many processors, this becomes less significant. Most of
the cost is in _incorrectly predicted_ branches, and in a switch-like
situation, most often there will be exactly one incorrectly predicted
branch, no matter what you do. You can reduce the number of correctly
predicted branches in between, but they are less significant.
That's a good point.
The truth is that I hardly ever do any assembly programming these days, so
you tend to forget what the instruction set is like.
Christian Bau wrote:
In article <d9**********@news.yaako.com>,
"He Shiming" <mailbill(NOSPAM)@21cn.com.nospam> wrote:
Oh that's definitely a great idea, I'll try, thanks.
Please. PLEASE. Think about it for a second.
Compilers have been doing this kind of stuff for decades.
If there were any simple method that you could use to replace your
switch statement and make it faster, then your compiler would use it.
Of course, you are always free to spend a few hours writing functions,
setting up an array of function pointers, and so on and so on and the
next guy who will have to maintain your code will be cursing you.
Might be you, anyway.
Why don't you like an array of function pointers?
--
pete
On 20/06/2005 06:50, forayer wrote: Christian Bau wrote: You are saying you use a compiler that will use 200 consecutive
comparisons and conditional branches for a switch statement with 200
cases?
no, i meant that the switch statement _didnt_ use 200 comparisions. it
jumped right to the appropriate case. such jumps do make sense for
switch-case structures, but how well can they be compared to an array
of function pointers (assuming that the cases can be easily indexed)?
Well, in assembly it probably resembles an array of "jump" pointers...
If you want to emulate that in C, you just create an array of functions,
since computed goto is not available.
On 20/06/2005 10:42, pete wrote: Christian Bau wrote:
In article <d9**********@news.yaako.com>,
"He Shiming" <mailbill(NOSPAM)@21cn.com.nospam> wrote:
Oh that's definitely a great idea, I'll try, thanks.
Please. PLEASE. Think about it for a second.
Compilers have been doing this kind of stuff for decades.
If there were any simple method that you could use to replace your
switch statement and make it faster, then your compiler would use it.
Of course, you are always free to spend a few hours writing functions,
setting up an array of function pointers, and so on and so on and the
next guy who will have to maintain your code will be cursing you.
Might be you, anyway.
Why don't you like an array of function pointers?
Function pointers are perfect, but I'd say "don't try to beat
the compiler unless there is a good reason". If the targeted compiler does
manage switches well, there is no reason IMHO to use function pointers here.
On 20/06/2005 17:21, CBFalconer wrote: Jean-Claude Arbaut wrote:
... snip ...
Well, in assembly it probably resembles an array of "jump"
pointers... If you want to emulate that in C, you just create
an array of functions, since computed goto is not available.
Yes it is. It just happens to be spelled 'switch'.
Not exactly. A switch has almost the same behaviour, but at assembly level,
(on my implementation) it will be translated as jumps, whereas functions
calls are translated as calls. It has some effect on the stack.
At the C level, there are also differences on scope I suppose.
On 20/06/2005 17:46, Jean-Claude Arbaut wrote:
On 20/06/2005 17:21, CBFalconer wrote:
Jean-Claude Arbaut wrote:
... snip ...
Well, in assembly it probably resembles an array of "jump"
pointers... If you want to emulate that in C, you just create
an array of functions, since computed goto is not available.
Yes it is. It just happens to be spelled 'switch'.
Not exactly. A switch has almost the same behaviour, but at assembly level,
(on my implementation) it will be translated as jumps, whereas functions
calls are translated as calls. It has some effect on the stack.
At the C level, there are also differences on scope I suppose.
And you have no guarantee a C compiler is smart enough to use a jump table.
That's not in the standard ;-) However, it is very likely to be smart
enough.
On Mon, 20 Jun 2005 08:42:31 +0000, pete wrote:
.... Why don't you like an array of function pointers?
It is likely that calling a function will have more overhead than
performing a jump.
Lawrence
Lawrence Kirby <lk****@netactive.co.uk> writes: On Mon, 20 Jun 2005 08:42:31 +0000, pete wrote:
...
Why don't you like an array of function pointers?
It is likely that calling a function will have more overhead than
performing a jump.
I wouldn't necessarily disagree with that, but here is a data
point. Performance measurements on x86 (that I've done) show
that the cost of a 'switch()' with a dense case set (256 values,
say) is pretty much neck-and-neck with the cost of calling
through pointer-to-function to do the same thing. Depending on
the specifics, calling through pointer-to-function can be faster
than using 'switch()'.
Of course, that assumes other considerations aren't a factor, and
often they are - sometimes favoring using 'switch()', and
sometimes favoring using a function call.
In article <BE******************************@laposte.net>,
Jean-Claude Arbaut <je****************@laposte.net> wrote: On 20/06/2005 17:46, Jean-Claude Arbaut wrote:
On 20/06/2005 17:21, CBFalconer wrote:
Jean-Claude Arbaut wrote:
... snip ...
Well, in assembly it probably resembles an array of "jump"
pointers... If you want to emulate that in C, you just create
an array of functions, since computed goto is not available.
Yes it is. It just happens to be spelled 'switch'.
Not exactly. A switch has almost the same behaviour, but at assembly level,
(on my implementation) it will be translated as jumps, whereas functions
calls are translated as calls. It has some effect on the stack.
At the C level, there are also differences on scope I suppose.
And you have no guarantee a C compiler is smart enough to use a jump table.
That's not in the standard ;-) However, it is very likely to be smart
enough.
It is also quite likely not to generate a jump table if that is smarter.
The compiler will know how long conditional branches take, how long
branching using a branch table takes, and so on. What if you have
twohundred cases with wildly varying values so you cannot use a jump
table? Some implementations will actually use a hash function in that
case. Or they use if/else arranged in a binary tree.
In article <kf*************@alumnus.caltech.edu>,
Tim Rentsch <tx*@alumnus.caltech.edu> wrote: Lawrence Kirby <lk****@netactive.co.uk> writes:
On Mon, 20 Jun 2005 08:42:31 +0000, pete wrote:
...
Why don't you like an array of function pointers?
It is likely that calling a function will have more overhead than
performing a jump.
I wouldn't necessarily disagree with that, but here is a data
point. Performance measurements on x86 (that I've done) show
that the cost of a 'switch()' with a dense case set (256 values,
say) is pretty much neck-and-neck with the cost of calling
through pointer-to-function to do the same thing. Depending on
the specifics, calling through pointer-to-function can be faster
than using 'switch()'.
If you use an old compiler on a Pentium 4, you might get very slow code
(if the compiler generates a table with offset in the same memory area
as the actual code; the processor basically throws up if you try to read
data and instructions from nearby memory locations).
Of course, that assumes other considerations aren't a factor, and
often they are - sometimes favoring using 'switch()', and
sometimes favoring using a function call.
On 21/06/2005 02:05, Christian Bau wrote: In article <BE******************************@laposte.net>,
Jean-Claude Arbaut <je****************@laposte.net> wrote:
On 20/06/2005 17:46, Jean-Claude Arbaut wrote:
On 20/06/2005 17:21, CBFalconer wrote:
Jean-Claude Arbaut wrote:
>
... snip ...
>
> Well, in assembly it probably resembles an array of "jump"
> pointers... If you want to emulate that in C, you just create
> an array of functions, since computed goto is not available.
Yes it is. It just happens to be spelled 'switch'.
Not exactly. A switch has almost the same behaviour, but at assembly level,
(on my implementation) it will be translated as jumps, whereas functions
calls are translated as calls. It has some effect on the stack.
At the C level, there are also differences on scope I suppose.
And you have no guarantee a C compiler is smart enough to use a jump table.
That's not in the standard ;-) However, it is very likely to be smart
enough.
It is also quite likely not to generate a jump table if that is smarter.
The compiler will know how long conditional branches take, how long
branching using a branch table takes, and so on. What if you have
twohundred cases with wildly varying values so you cannot use a jump
table? Some implementations will actually use a hash function in that
case. Or they use if/else arranged in a binary tree.
Well, actually CBFalconer was talking about computed goto, and I completely
missed the point. He was kind enough not to correct me :-)
Jean-Claude Arbaut <je****************@laposte.net> writes: On 20/06/2005 17:21, CBFalconer wrote:
Jean-Claude Arbaut wrote:
... snip ...
Well, in assembly it probably resembles an array of "jump"
pointers... If you want to emulate that in C, you just create
an array of functions, since computed goto is not available.
Yes it is. It just happens to be spelled 'switch'.
Not exactly. A switch has almost the same behaviour, but at assembly level,
(on my implementation) it will be translated as jumps, whereas functions
calls are translated as calls. It has some effect on the stack.
At the C level, there are also differences on scope I suppose.
I think he meant that a switch statement is essentially the same thing
as a computed goto. (It's a bit more limited (for example you can't
do a backward jump), but that's a good thing.)
--
Keith Thompson (The_Other_Keith) 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.
One way to tackle the problem may be to drill down in a binary search
tree type of manner. For example, Lets say you have cases 0-255. You
could do something like this:
switch (x/100) { /* Check the first digit and drill down. */
case 0:
switch (x/10 - (x/100) * 10) { /* check the second digit. */
case 0:
switch ... /* check the third digit. */
case 1:
... (similar to above)
case 2:
... (similar to above)
... (continue like this through 9)
case 1:
.... (similar to above)
case 2:
.... (similar to above)
default:
/* Error. */
}
So what you are basically doing is checking each digit to find the
value you want. This effectively means that each check on a 0-255 (or
to 999 for that matter) will only involve three checks. The only cases
where a single switch statement will be faster is if the first two
cases were selected most of the time.
In article <11*********************@g14g2000cwa.googlegroups. com> "icub3d" <ic****@gmail.com> writes:
.... So what you are basically doing is checking each digit to find the
value you want. This effectively means that each check on a 0-255 (or
to 999 for that matter) will only involve three checks. The only cases
where a single switch statement will be faster is if the first two
cases were selected most of the time.
Unless the switch is implemented with a jump table.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
"icub3d" <ic****@gmail.com> wrote in message
news:11*********************@g14g2000cwa.googlegro ups.com... One way to tackle the problem may be to drill down in a binary search
tree type of manner. For example, Lets say you have cases 0-255. You
could do something like this:
switch (x/100) { /* Check the first digit and drill down. */
case 0:
switch (x/10 - (x/100) * 10) { /* check the second digit. */
case 0:
switch ... /* check the third digit. */
case 1:
... (similar to above)
case 2:
... (similar to above)
... (continue like this through 9)
case 1:
... (similar to above)
case 2:
... (similar to above)
default:
/* Error. */
}
So what you are basically doing is checking each digit to find the
value you want. This effectively means that each check on a 0-255 (or
to 999 for that matter) will only involve three checks. The only cases
where a single switch statement will be faster is if the first two
cases were selected most of the time.
You are assuming that a single switch statement does multiple checks. I
doubt any implementation does so. So, your "optimization" does three checks
(plus all the math), where as if you just let the compiler do the work,
there is only one.
REH
In article <d9*********@cui1.lmms.lmco.com>, REH <bo***@nowhere.net> wrote: You are assuming that a single switch statement does multiple checks. I
doubt any implementation does so.
I just created a simple test program with four non-consequative
case labels. SGI's "cc" compiler and gcc generated different looking
code for the same program, but at key points, they both did multiple
comparisons and not just against the boundary values. [Oddly, for
both, the first pair of comparisions they did was against the
first case label and then against the second-largest case label -- not
against the largest.]
--
'The short version of what Walter said is "You have asked a question
which has no useful answer, please reconsider the nature of the
problem you wish to solve".' -- Tony Mantler
Unfortunately, we can't determine ahead of time if the compiler will do
this work for us. As Walter suggested, two major compilers don't do
this optimization, so it's hard to assume that many others will.
This thread has been closed and replies have been disabled. Please start a new discussion. | |
