Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   Regarding Switch statement (http://www.velocityreviews.com/forums/t317423-regarding-switch-statement.html)

prafulla 02-19-2004 04:16 AM

Regarding Switch statement
 
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

Jack Klein 02-19-2004 04:37 AM

Re: Regarding Switch statement
 
On 18 Feb 2004 20:16:46 -0800, prafullakh@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

Kenneth Brody 02-19-2004 03:36 PM

Re: Regarding Switch statement
 
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." |
+---------+----------------------------------+-----------------------------+



Thomas Matthews 02-19-2004 05:18 PM

Re: Regarding Switch statement
 
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


Keith Thompson 02-19-2004 08:58 PM

Re: Regarding Switch statement
 
Thomas Matthews <Thomas_MatthewsSpitsOnSpamBots@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) kst-u@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"

James Dow Allen 02-20-2004 03:41 AM

Re: Regarding Switch statement
 
Kenneth Brody <kenbrody@spamcop.net> wrote in message news:<4034D812.27BE7E85@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

nrk 02-20-2004 05:51 AM

Re: Regarding Switch statement
 
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/groups?as_umsg...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

Peter Pichler 02-20-2004 08:53 AM

Re: Regarding Switch statement
 
"nrk" <ram_nrk2000@devnull.verizon.net> wrote in message
news:_fhZb.52867$1S1.40084@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.



Richard Bos 02-20-2004 11:03 AM

Re: Regarding Switch statement
 
CBFalconer <cbfalconer@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

CBFalconer 02-20-2004 11:33 AM

Re: Regarding Switch statement
 
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 (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!




All times are GMT. The time now is 12:22 PM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.