By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
440,199 Members | 1,458 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 440,199 IT Pros & Developers. It's quick & easy.

Regarding Switch statement

P: n/a
Hi all,

I don't have a copy of C standard at hand and so anyone of you can
help me. I have always wondered how switch statements are so efficient
in jumping to the right case (if any)? Can anybody point me to the
innards of it please?

Sorry if this is OT on clc and more relevant to comp.compilers. I am
confused here too.

TIA
-Prafulla harpanhalli
Nov 14 '05 #1
Share this Question
Share on Google+
17 Replies


P: n/a
On 18 Feb 2004 20:16:46 -0800, pr********@rediffmail.com (prafulla)
wrote in comp.lang.c:
Hi all,

I don't have a copy of C standard at hand and so anyone of you can
help me. I have always wondered how switch statements are so efficient
in jumping to the right case (if any)? Can anybody point me to the
innards of it please?
Who says they are efficient? The C standard does not discuss
efficiency at all, this is a QOI issue. If a C implementation
compiles a strictly conforming program that generates the correct
output, whether it takes 5 seconds, 5 hours, or 5 years is not a
language issue.
Sorry if this is OT on clc and more relevant to comp.compilers. I am
confused here too.
How a compiler implements the "innards" is completely unspecified by
the language and irrelevant here. Possibilities include a series of
"if" "else if" statements, or perhaps a jump table.
TIA
-Prafulla harpanhalli


comp.compilers would be a much better choice for implementation
details.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++
http://www.contrib.andrew.cmu.edu/~a...FAQ-acllc.html
Nov 14 '05 #2

P: n/a
prafulla wrote:

Hi all,

I don't have a copy of C standard at hand and so anyone of you can
help me. I have always wondered how switch statements are so efficient
in jumping to the right case (if any)? Can anybody point me to the
innards of it please?

Sorry if this is OT on clc and more relevant to comp.compilers. I am
confused here too.


This is really an implementation thing, not a language thing. How
a particular C compiler implements switch/case is irrelevent to the
C language itself.

That said...

There are numerous possibilities. Suppose, for example, that your
cases are 0, 1, 2, 3, 4, and 5. The compiler could generate a jump
table (after bounds checking) to each of the 6 possibilities, and
jump directly to the appropriate case. Another possibility, if the
cases are too disparate for a jump table, would be to generate a
binary search through the values. (ie: if less than the median
value, jump to A, else to B. Within A and B, each repeats the
median comparison, until you end up at a simple "is it this value,
and if not, jump to the default case".) You might even combine
these methods, if you have clusters of values within a disparate
group. (ie: 0, 1, 2, 3, 50, 51, 52, 99)

Of course, there's nothing stopping the compiler from generating
the equivalent of a bunch of if/else tests in the order in which
you code the cases.
If you have a specific compiler in mind, see if there is a groups
specifically for that compiler. Otherwise, comp.compilers would be
a good place for general questions regarding possible methods of
optimizing switch/case statements.

--

+---------+----------------------------------+-----------------------------+
| Kenneth | kenbrody at spamcop.net | "The opinions expressed |
| J. | http://www.hvcomputer.com | herein are not necessarily |
| Brody | http://www.fptech.com | those of fP Technologies." |
+---------+----------------------------------+-----------------------------+
Nov 14 '05 #3

P: n/a
prafulla wrote:
Hi all,

I don't have a copy of C standard at hand and so anyone of you can
help me. I have always wondered how switch statements are so efficient
in jumping to the right case (if any)? Can anybody point me to the
innards of it please?

Sorry if this is OT on clc and more relevant to comp.compilers. I am
confused here too.

TIA
-Prafulla harpanhalli


Two popular implementations of a switch statement are:
1. if-elseif-else ladder.
2. table of function pointers (jump table).

You can always implement these yourself, by converting
your switch statement into one of the above. The switch
statement just happens to be a convenient notation for
this programming pardigm (pattern?).

I personally believe that the switch statement is evil
and I prefer using tables of function pointers. I've
seen many abused switch statements (including a greater
evil of nesting them). One problematic issue of tables
of function pointers is that each function must have
the same signature (even if the function doesn't use
all the parameters).

I believe that switch statements are clear to read
when they are small. But like plants and children,
they don't remain small forever. ;-)

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book

Nov 14 '05 #4

P: n/a
Thomas Matthews <Th****************************@sbcglobal.net> writes:
[...]
Two popular implementations of a switch statement are:
1. if-elseif-else ladder.
2. table of function pointers (jump table).

You can always implement these yourself, by converting
your switch statement into one of the above. The switch
statement just happens to be a convenient notation for
this programming pardigm (pattern?).


A C switch statement is not equivalent to an if-elseif-else ladder
*unless* each case ends in a break. If some of the cases fall through
to other cases, a translation will have to use something like gotos.
Then again, an if-elseif-else ladder is implemented using gotos, or
rather machine-level conditional and unconditional branches, but there
can be optimization advantages in using a more structured intermediate
representation -- which a compiler can do in the common case where
each case does end in a break.

If a switch statement is implemented using a jump table, it won't be a
table of function pointers; it will be a table of label pointers.
Standard C doesn't have such a construct <OT>though I think GNU C
does</OT>.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://www.sdsc.edu/~kst>
Schroedinger does Shakespeare: "To be *and* not to be"
Nov 14 '05 #5

P: n/a
Kenneth Brody <ke******@spamcop.net> wrote in message news:<40***************@spamcop.net>...
prafulla wrote:
I have always wondered how switch statements are so efficient
in jumping to the right case (if any)? Can anybody point me to the
innards of it please?
If you have a specific compiler in mind, see if there is a groups
specifically for that compiler....


Easier yet, just look at the compiled code, e.g. with cc -S.

Some compilers are fairly clever at combining different implementation
ideas within one switch.

It might be fun to stage a little experiment here, finding the
cleverest compiled switch (and the worst).

James
Nov 14 '05 #6

P: n/a
nrk
prafulla wrote:
Hi all,

I don't have a copy of C standard at hand and so anyone of you can
help me. I have always wondered how switch statements are so efficient
in jumping to the right case (if any)? Can anybody point me to the
innards of it please?

Please note that there is no guarantee about efficiencies in the C standard.
However, for stylistic reasons, when checking more than 3 if-else if-else
if style conditions, I would pick switch. If you want some insight into
the innards, Chris Torek posted an excellent article on the subject in the
not too distant past. Here it is:

http://www.google.com/gr************...s3.newsguy.com

-nrk.
Sorry if this is OT on clc and more relevant to comp.compilers. I am
confused here too.

TIA
-Prafulla harpanhalli


--
Remove devnull for email
Nov 14 '05 #7

P: n/a
"nrk" <ra*********@devnull.verizon.net> wrote in message
news:_f*******************@nwrddc01.gnilink.net...
Please note that there is no guarantee about efficiencies in the C standard. However, for stylistic reasons, when checking more than 3 if-else if-else
if style conditions, I would pick switch.


Unless you *want* to evaluate the expression each time, for example when it
has a side-effect, changes its value or when it is a different expression
:-)

My boss used to use switch even for a single case. He argued that switch is
faster than if. Now that is what I call strange.
Nov 14 '05 #8

P: n/a
nrk wrote:
.... snip ...
However, for stylistic reasons, when checking more than 3 if-else
if-else if style conditions, I would pick switch.


Please explain how you handle the following with switch:

if (v > 10000) i = 0;
else if (v > 1000 ) i = 3;
else if (v > 100 ) i = 5;
else if (v > 10 ) i = 2;
else if (v > 5 ) i = 1;
else i = 0;

and be prepared to reorganize either column of values at any time,
including the number of cases to be handled.

The above table is closely related to the Bush regimes tax
policies in the US.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Nov 14 '05 #9

P: n/a
CBFalconer <cb********@yahoo.com> wrote:
nrk wrote:
However, for stylistic reasons, when checking more than 3 if-else
if-else if style conditions, I would pick switch.


Please explain how you handle the following with switch:

if (v > 10000) i = 0;
else if (v > 1000 ) i = 3;
else if (v > 100 ) i = 5;
else if (v > 10 ) i = 2;
else if (v > 5 ) i = 1;
else i = 0;

and be prepared to reorganize either column of values at any time,
including the number of cases to be handled.

The above table is closely related to the Bush regimes tax
policies in the US.


v is monthly income in hundreds of dollars, i is income tax in dollars?

Richard
Nov 14 '05 #10

P: n/a
nrk
CBFalconer wrote:
nrk wrote:

... snip ...

However, for stylistic reasons, when checking more than 3 if-else
if-else if style conditions, I would pick switch.


Please explain how you handle the following with switch:

if (v > 10000) i = 0;
else if (v > 1000 ) i = 3;
else if (v > 100 ) i = 5;
else if (v > 10 ) i = 2;
else if (v > 5 ) i = 1;
else i = 0;

and be prepared to reorganize either column of values at any time,
including the number of cases to be handled.

The above table is closely related to the Bush regimes tax
policies in the US.


Try to engage your brain please ;-) I was obviously talking about
situations where a switch would be appropriate. If that wasn't obvious to
you, that's your lookout, not mine.

-nrk.

--
Remove devnull for email
Nov 14 '05 #11

P: n/a
nrk wrote:
CBFalconer wrote:
nrk wrote:

... snip ...

However, for stylistic reasons, when checking more than 3 if-else
if-else if style conditions, I would pick switch.


Please explain how you handle the following with switch:

if (v > 10000) i = 0;
else if (v > 1000 ) i = 3;
else if (v > 100 ) i = 5;
else if (v > 10 ) i = 2;
else if (v > 5 ) i = 1;
else i = 0;

and be prepared to reorganize either column of values at any time,
including the number of cases to be handled.

The above table is closely related to the Bush regimes tax
policies in the US.


Try to engage your brain please ;-) I was obviously talking about
situations where a switch would be appropriate. If that wasn't
obvious to you, that's your lookout, not mine.


Now now, let's not get testy :-) Looking up I distinctly see the
prequisite "more than 3 if else if" clauses. We do tend to
require precision around here, and I have been bitten by it often
enough. Acting like Bushmen is not appropriate.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Nov 14 '05 #12

P: n/a
On Fri, 20 Feb 2004 15:10:00 GMT, nrk
<ra*********@devnull.verizon.net> wrote:
policies in the US.


Try to engage your brain please ;-) I was obviously talking about
situations where a switch would be appropriate. If that wasn't obvious to
you, that's your lookout, not mine.


It's harder to code political statements with switch.

--
Al Balmer
Balmer Consulting
re************************@att.net
Nov 14 '05 #13

P: n/a
nrk
CBFalconer wrote:
nrk wrote:

... snip ...

However, for stylistic reasons, when checking more than 3 if-else
if-else if style conditions, I would pick switch.


Please explain how you handle the following with switch:

if (v > 10000) i = 0;
else if (v > 1000 ) i = 3;
else if (v > 100 ) i = 5;
else if (v > 10 ) i = 2;
else if (v > 5 ) i = 1;
else i = 0;

and be prepared to reorganize either column of values at any time,
including the number of cases to be handled.

The above table is closely related to the Bush regimes tax
policies in the US.


If you must insist on a switch solution to this particular case... then:

static const int vtable[] = { 10000, 1000, 100, 10, 5, };
static const int itable[] = { 0, 3, 5, 2, 1, };
int index = 0, test = 0;

while ( index < sizeof vtable/sizeof vtable[0] ) {
switch ( test ) {
case 1:
i = itable[index-1];
goto end;
case 0:
test = index < sizeof vtable/sizeof vtable[0] &&
(v > vtable[index++]);
break;
}
}
i = 0;
end:
/* use i here */

This just re-inforces the idea that it is probably better to engage the
muscle between the ears than to take statements on style out of context and
try to apply them willy-nilly ;-) At least, you didn't ask me for C&V for
that stylistic statment!

-nrk.
--
Remove devnull for email
Nov 14 '05 #14

P: n/a
nrk
nrk wrote:
CBFalconer wrote:
nrk wrote:
... snip ...

However, for stylistic reasons, when checking more than 3 if-else
if-else if style conditions, I would pick switch.


Please explain how you handle the following with switch:

if (v > 10000) i = 0;
else if (v > 1000 ) i = 3;
else if (v > 100 ) i = 5;
else if (v > 10 ) i = 2;
else if (v > 5 ) i = 1;
else i = 0;

and be prepared to reorganize either column of values at any time,
including the number of cases to be handled.

The above table is closely related to the Bush regimes tax
policies in the US.


If you must insist on a switch solution to this particular case... then:

static const int vtable[] = { 10000, 1000, 100, 10, 5, };
static const int itable[] = { 0, 3, 5, 2, 1, };
int index = 0, test = 0;

while ( index < sizeof vtable/sizeof vtable[0] ) {


Dang it! That's not going to work, is it?
switch ( test ) {
case 1:
i = itable[index-1];
goto end;
case 0:
test = index < sizeof vtable/sizeof vtable[0] &&
(v > vtable[index++]);
break;
}
}
i = 0;
end:
/* use i here */
Let's try again:

static const int vtable[] = { 10000, 1000, 100, 10, 5, };
static const int itable[] = { 0, 3, 5, 2, 1, };
int index = 0, test = 0;

while ( index < sizeof vtable/sizeof vtable[0] ) {
switch ( test ) {
case 1:
i = itable[index];
goto end;
case 0:
test = (v > vtable[index] || (++index, 0));
break;
}
}
i = 0;
end:
/* use i here */

I think there's a lesson somewhere in this for me, but I refuse to learn :-)

-nrk.

This just re-inforces the idea that it is probably better to engage the
muscle between the ears than to take statements on style out of context
and
try to apply them willy-nilly ;-) At least, you didn't ask me for C&V for
that stylistic statment!

-nrk.


--
Remove devnull for email
Nov 14 '05 #15

P: n/a
On Fri, 20 Feb 2004 11:42:44 -0700, in comp.lang.c , Alan Balmer
<al******@att.net> wrote:
On Fri, 20 Feb 2004 15:10:00 GMT, nrk
<ra*********@devnull.verizon.net> wrote:
policies in the US.


Try to engage your brain please ;-) I was obviously talking about
situations where a switch would be appropriate. If that wasn't obvious to
you, that's your lookout, not mine.


It's harder to code political statements with switch.


Wasn't it an american president who said
"walk softly, but carry a big switch?"

:-)

--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.angelfire.com/ms3/bchambless0/welcome_to_clc.html>
----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---
Nov 14 '05 #16

P: n/a
CBFalconer <cb********@yahoo.com> writes:
[...]
Now now, let's not get testy :-) Looking up I distinctly see the
prequisite "more than 3 if else if" clauses. We do tend to
require precision around here, and I have been bitten by it often
enough. Acting like Bushmen is not appropriate.


<OT>
I'm sure you didn't intend that as an ethnic slur. The Bushmen are an
actual ethnic group in southern Africa. (There's been some debate, I
think, about whether "Bushmen" is an appropriate term, but the brief
Googling I just did indicates that it's now generally accepted.)
</OT>

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://www.sdsc.edu/~kst>
Schroedinger does Shakespeare: "To be *and* not to be"
Nov 14 '05 #17

P: n/a
Keith Thompson wrote:
CBFalconer <cb********@yahoo.com> writes:
[...]
Now now, let's not get testy :-) Looking up I distinctly see the
prequisite "more than 3 if else if" clauses. We do tend to
require precision around here, and I have been bitten by it often
enough. Acting like Bushmen is not appropriate.


<OT>
I'm sure you didn't intend that as an ethnic slur. The Bushmen are an
actual ethnic group in southern Africa. (There's been some debate, I
think, about whether "Bushmen" is an appropriate term, but the brief
Googling I just did indicates that it's now generally accepted.)


I didn't, but I did intend it to connote the present US regime in
temporary (we trust) power, who have been known to play fast and
loose with accuracy and precision.
</OT>

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Nov 14 '05 #18

This discussion thread is closed

Replies have been disabled for this discussion.