Regarding Switch statement

[prafulla]

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]

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.

 

[Kenneth Brody]

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]

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]

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

 

[James Dow Allen]

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]

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/[email protected]

-nrk.

 

[Peter Pichler]

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]

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]

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

 

[nrk]

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.

 

[CBFalconer]

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.

 

[Alan Balmer]

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.

 

[nrk]

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.

 

[nrk]

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.

 

[Keith Thompson]

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>

 

[Mark McIntyre]

It's harder to code political statements with switch.

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

 

[CBFalconer]

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