Optimizing a switch statement

[mehul raval]

Re: Optimizing a switch statement

Thomas Matthews <Thomas_Matthew sSpamBotsSuck@s bcglobal.net> wrote in message news:<4046A691. 1050904@sbcglob al.net>...
hi ,
if i am not mistaken adding a case for 5 wont reduce the code length,
instead it wld become more. also the execution will depend upon the
fact that the jmp addresses are within the same segment or not,ie if
the jmp addr is in another segment it will take more time for the
jmp.also the case values 1,2,... need not be in the ascending order,
thay can be random as they simply pt to a jmp addr and the switch
statemnt will simply check the directn variable value and jmp to the
corr addr.
the order is of significance.
regarding the function ptr thing u can initialize a func ptr like int
(*p[..])(); and then the statement (*p[direction])(); wld do the job
for u.
ofcourse the elements of p[] shld be intialized.
this will save a lot of code space for u also the execution will be
faster.
also on an avg the ifelse statment is also slower then the switch
statment and the ur fucn will not be executed as an ifelse stmnt,
where it continues the search until a match is found.
thats wht i think is the situation, i might be mistaken aswell.
hope it helps.
mehul[color=blue]
> Hi,
>
> My son is writing a program to move a character. He is
> using the numbers on the keypad to indicate the direction
> of movement:
> 7 8 9
> 4 5 6
> 1 2 3
> Each number has a direction except for '5'. So in
> his switch statement, he omits a case for '5':
> /* char direction; */
> switch (direction)
> {
> case '1':
> move_lower_left ();
> break;
> case '2':
> move_down();
> break;
> case '3':
> move_lower_righ t();
> break;
> case '4':
> move_left();
> break;
> case '6':
> move_right();
> break;
> case '7':
> move_upper_left ();
> break;
> case '8':
> move_up();
> break;
> case '9':
> move_upper_righ t();
> break;
> } /* end switch direction */
>
> The case selectors are not contiguous in the above
> example, since case '5' is omitted (on purpose).
>
> My question is: Would adding a case for '5' reduce
> the code space and execution time for this switch
> statement?
>
> The logic behind this is that a contigous set of
> case selectors would allow the compiler to create
> a "jump table", where as the above example may
> force the compiler to generate an "if-elseif"
> ladder.
>
> {I cross posted to the three newsgroups because
> this issue deals with a switch statement which
> exists in both the C and C++ languages. This
> may also be of interest to newbies, like my son.}
>
> --
> 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.l earn.c-c++ faq:
> http://www.raos.demon.uk/acllc-c++/faq.html
> Other sites:
> http://www.josuttis.com -- C++ STL Library book
> http://www.sgi.com/tech/stl -- Standard Template Library[/color]

[Joona I Palaste]

Re: Optimizing a switch statement

mehul raval <mehul.r@aretec hnologies.net> scribbled the following
on comp.lang.c:[color=blue]
> Thomas Matthews <Thomas_Matthew sSpamBotsSuck@s bcglobal.net> wrote in message news:<4046A691. 1050904@sbcglob al.net>...
> hi ,[/color]
Hi,
[color=blue]
> if i am not mistaken adding a case for 5 wont reduce the code length,[/color]
If I am not mistaken adding a case for 5 won't reduce the code length,
[color=blue]
> instead it wld become more. also the execution will depend upon the[/color]
instead it would become longer. Also the execution will depend upon the
[color=blue]
> fact that the jmp addresses are within the same segment or not,ie if[/color]
issue of whether jmp addresses are within the same segment, i.e. if
[color=blue]
> the jmp addr is in another segment it will take more time for the[/color]
the jmp address is in another segment it will take more time for the
[color=blue]
> jmp.also the case values 1,2,... need not be in the ascending order,[/color]
jmp. Also the case values 1, 2, ... need not be in ascending order,
[color=blue]
> thay can be random as they simply pt to a jmp addr and the switch[/color]
they can be random as they simply point to a jmp address and the switch
[color=blue]
> statemnt will simply check the directn variable value and jmp to the[/color]
statement will simply check the direction variable value and jump to the
[color=blue]
> corr addr.[/color]
correct address.
[color=blue]
> the order is of significance.[/color]
The order is of significance.
[color=blue]
> regarding the function ptr thing u can initialize a func ptr like int[/color]
Regarding the function pointer thing you can initialise a function
pointer like int
[color=blue]
> (*p[..])(); and then the statement (*p[direction])(); wld do the job[/color]
(*p[..])(); and then the statement (*p[direction])(); would do the job
[color=blue]
> for u.[/color]
for you.
[color=blue]
> ofcourse the elements of p[] shld be intialized.[/color]
Of course the elements of p[] should be initialised.
[color=blue]
> this will save a lot of code space for u also the execution will be[/color]
This will save a lot of code space for you. Also the execution will be
[color=blue]
> faster.[/color]
faster.
[color=blue]
> also on an avg the ifelse statment is also slower then the switch[/color]
Also on average, the if-else statement is also slower than the switch
[color=blue]
> statment and the ur fucn will not be executed as an ifelse stmnt,[/color]
statement and your function will not be executed as an if-else
statement,
[color=blue]
> where it continues the search until a match is found.[/color]
where it continues the search until a match is found.
[color=blue]
> thats wht i think is the situation, i might be mistaken aswell.[/color]
That's what I think is the situation, I might be mistaken as well.
[color=blue]
> hope it helps.[/color]
Hope it helps.

See? Typos and/or spelling errors found on almost *every* line. The
point is, learn to write *before* you attempt to sound like a 10-year-
old kid who spends all his life playing Quake netmatches and has never
been across the street.

--
/-- Joona Palaste (palaste@cc.hel sinki.fi) ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
"This is a personnel commuter."
- Train driver in Scientific American

[Thomas Matthews]

Re: Optimizing a switch statement

1st off,dont toppost:

http://www.parashift.com/c++-faq-lite/how-to-post.html

mehul raval wrote:[color=blue]
> Thomas Matthews <Thomas_Matthew sSpamBotsSuck@s bcglobal.net> wrote in message news:<4046A691. 1050904@sbcglob al.net>...
> hi ,
> if i am not mistaken adding a case for 5 wont reduce the code length,
> instead it wld become more.[/color]

Pardon me if I try to speak in you dialect of writing or English.
actuly,w/o da or ny cse 4 5 will mke da code len mor cuz u will hav
2 serch da lst 4 da rt key. dis tak mor tym den usng arry uv func ptrs.

[color=blue]
> also the execution will depend upon the
> fact that the jmp addresses are within the same segment or not,ie if
> the jmp addr is in another segment it will take more time for the
> jmp.[/color]

u r asumin dat all pltfms hav segmts.mny dont. da tym uv da jmp is
not relvant cuz u hav ta jmp 4 any case anyway. da issu iz how much
tym it taks 2 find da rit jmp.

[color=blue]
> also the case values 1,2,... need not be in the ascending order,
> thay can be random as they simply pt to a jmp addr and the switch
> statemnt will simply check the directn variable value and jmp to the
> corr addr.
> the order is of significance.[/color]

if da cas valus r not in ascending ordr,dey can be in descending ordr,
but dey mus be ordered; at leest 2 reduse da serch tym.

[color=blue]
> regarding the function ptr thing u can initialize a func ptr like int
> (*p[..])(); and then the statement (*p[direction])(); wld do the job
> for u.[/color]

y bother mking my own func ptr thing when da compilr do it 4 me.

[color=blue]
> ofcourse the elements of p[] shld be intialized.
> this will save a lot of code space for u also the execution will be
> faster.
> also on an avg the ifelse statment is also slower then the switch
> statment and the ur fucn will not be executed as an ifelse stmnt,
> where it continues the search until a match is found.
> thats wht i think is the situation, i might be mistaken aswell.
> hope it helps.
> mehul[/color]

[Language change]
For small quantities of case selectors or when the selectors are
contiguous, the switch statement is faster than a ladder of if-else
statements. As discussed else-thread, the compiler can create an
array of jump instructions or addresses and calculate an index into
that array.

By the way, writing in correct English would be more helpful.
See Joona's crusade in this newsgroup and others.
[color=blue]
>[color=green]
>>Hi,
>>
>>My son is writing a program to move a character. He is
>>using the numbers on the keypad to indicate the direction
>>of movement:
>> 7 8 9
>> 4 5 6
>> 1 2 3
>>Each number has a direction except for '5'. So in
>>his switch statement, he omits a case for '5':
>>/* char direction; */
>> switch (direction)
>> {
>> case '1':
>> move_lower_left ();
>> break;
>> case '2':
>> move_down();
>> break;
>> case '3':
>> move_lower_righ t();
>> break;
>> case '4':
>> move_left();
>> break;
>> case '6':
>> move_right();
>> break;
>> case '7':
>> move_upper_left ();
>> break;
>> case '8':
>> move_up();
>> break;
>> case '9':
>> move_upper_righ t();
>> break;
>> } /* end switch direction */
>>
>>The case selectors are not contiguous in the above
>>example, since case '5' is omitted (on purpose).
>>
>>My question is: Would adding a case for '5' reduce
>>the code space and execution time for this switch
>>statement?
>>
>>The logic behind this is that a contigous set of
>>case selectors would allow the compiler to create
>>a "jump table", where as the above example may
>>force the compiler to generate an "if-elseif"
>>ladder.
>>[/color][/color]


--
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.l earn.c-c++ faq:

http://www.raos.demon.uk/acllc-c++/faq.html

Other sites:
http://www.josuttis.com -- C++ STL Library book

[Kenneth Brody]

Re: Optimizing a switch statement

Thomas Matthews wrote:
[...][color=blue]
> Each number has a direction except for '5'. So in
> his switch statement, he omits a case for '5':
> /* char direction; */
> switch (direction)
> {
> case '1':[/color]
[...'2', '3', '4', '6', '7', and '8', but no '5' ...][color=blue]
> case '9':
> move_upper_righ t();
> break;
> } /* end switch direction */
>
> The case selectors are not contiguous in the above
> example, since case '5' is omitted (on purpose).
>
> My question is: Would adding a case for '5' reduce
> the code space and execution time for this switch
> statement?[/color]

It depends entirely on the compiler.
[color=blue]
> The logic behind this is that a contigous set of
> case selectors would allow the compiler to create
> a "jump table", where as the above example may
> force the compiler to generate an "if-elseif"
> ladder.[/color]

There's nothing stopping a "smart" compiler from recognizing
the gap in the sequence and building a jump table that has a
case '5' that jumps to the default.

There's also nothing stopping a "dumb" compiler from simply
using an if/elseif chain regardless of the contiguous nature
of the cases.

[...]

--

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

[Nick Hounsome]

Re: Optimizing a switch statement


"Thomas Matthews" <Thomas_Matthew sSpamBotsSuck@s bcglobal.net> wrote in
message news:4046A691.1 050904@sbcgloba l.net...[color=blue]
> Hi,
>
> My son is writing a program to move a character. He is
> using the numbers on the keypad to indicate the direction
> of movement:
> 7 8 9
> 4 5 6
> 1 2 3
> Each number has a direction except for '5'. So in
> his switch statement, he omits a case for '5':
> /* char direction; */
> switch (direction)
> {
> case '1':
> move_lower_left ();
> break;
> case '2':
> move_down();
> break;
> case '3':
> move_lower_righ t();
> break;
> case '4':
> move_left();
> break;
> case '6':
> move_right();
> break;
> case '7':
> move_upper_left ();
> break;
> case '8':
> move_up();
> break;
> case '9':
> move_upper_righ t();
> break;
> } /* end switch direction */
>
> The case selectors are not contiguous in the above
> example, since case '5' is omitted (on purpose).
>
> My question is: Would adding a case for '5' reduce
> the code space and execution time for this switch
> statement?
>
> The logic behind this is that a contigous set of
> case selectors would allow the compiler to create
> a "jump table", where as the above example may
> force the compiler to generate an "if-elseif"
> ladder.
>
> {I cross posted to the three newsgroups because
> this issue deals with a switch statement which
> exists in both the C and C++ languages. This
> may also be of interest to newbies, like my son.}
>[/color]

If your son is a newbiie then the best advice is not to try
to optimize anything (except possibly algorithms).

Even if he isn't the overhead of a function call will dwarf any
possible optimization of the switch. - and even if the calls are to inline
methods the input is generated by a user pressing keys! You could
convert all the input to std::string using ostringstream (aplogies
to comp.lang.c readers) and then compare them with a big if..then..else
and it would have no discernable effect on performance!
[color=blue]
> --
> 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.l earn.c-c++ faq:
> http://www.raos.demon.uk/acllc-c++/faq.html
> Other sites:
> http://www.josuttis.com -- C++ STL Library book
> http://www.sgi.com/tech/stl -- Standard Template Library
>[/color]

[CBFalconer]

Re: Optimizing a switch statement

Thomas Matthews wrote:[color=blue]
>
> My son is writing a program to move a character. He is
> using the numbers on the keypad to indicate the direction
> of movement:
> 7 8 9
> 4 5 6
> 1 2 3
> Each number has a direction except for '5'. So in
> his switch statement, he omits a case for '5':
> /* char direction; */
> switch (direction)
> {[/color]
.... snip coding ...[color=blue]
> } /* end switch direction */
>
> The case selectors are not contiguous in the above
> example, since case '5' is omitted (on purpose).
>
> My question is: Would adding a case for '5' reduce
> the code space and execution time for this switch
> statement?
>[/color]
.... snip ...[color=blue]
>
> {I cross posted to the three newsgroups because
> this issue deals with a switch statement which
> exists in both the C and C++ languages. This
> may also be of interest to newbies, like my son.}[/color]

My version, possibly creating less code, but pointless otherwise:

switch (direction) {
case 1: x--;
case 2: y++; break;
case 3: y++;
case 6: x++; break;
case 7: y--;
case 4: x--; break;
case 9: x++;
case 8: y--;
default: break;
}

--
Chuck F (cbfalconer@yah oo.com) (cbfalconer@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!