472,325 Members | 1,351 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 472,325 software developers and data experts.

Optimizing a switch statement

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_right();
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_right();
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.learn.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

Jul 22 '05 #1
35 7989
Thomas Matthews wrote:
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_right();
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_right();
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?


A better solution is to use a lookup table of function pointers:

typedef void (*dfunc)(void);
dfunc move[] = {
0,
move_lower_left,
move_down,
/* ... */
move_upper_right,
};

and then

int d;
dfunc *f;

while(d=getdirection()){
if(f=move[d]){
f();
}
};

/david

--
"As a scientist, Throckmorton knew that if he were ever to break wind in
the echo chamber, he would never hear the end of it."

Jul 22 '05 #2
"Thomas Matthews" <Th*************************@sbcglobal.net> wrote...
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_right();
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_right();
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?
I doubt that. Of course, there _can_ be some _really_ sophisticated
compilers that introduce jump tables, but I've not personally seen one.
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.


If the compiler is smart enough to generate a jump table, it should be
smart enough to generate the same jump for '5' as for all other values
(the missing "default" clause), don't you think so?

V
Jul 22 '05 #3
David Rubin wrote:

Thomas Matthews wrote:
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_right();
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_right();
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?


A better solution is to use a lookup table of function pointers:

typedef void (*dfunc)(void);
dfunc move[] = {
0,
move_lower_left,
move_down,
/* ... */
move_upper_right,
};

and then

int d;
dfunc *f;

while(d=getdirection()){
if(f=move[d]){
f();
}
};

/david


That's what I was thinking. But you can even optimize away the if() by
creating a null function for the '5', something like:

void do_nothing(void) { }

dfunc move[] = {
do_nothing,
move_lower_left,
//...

while(d=getdirection()){
move[d]();
};
Jul 22 '05 #4
> A better solution is to use a lookup table of function pointers:

Why is it better?
Jul 22 '05 #5

"Victor Bazarov" <v.********@comAcast.net> wrote in message
news:4Sx1c.453043$I06.5117172@attbi_s01...
I doubt that. Of course, there _can_ be some _really_ sophisticated
compilers that introduce jump tables, but I've not personally seen one.
When is the last time you checked? I have never seen a C or C++ compiler
that *doesn't* generate a jump table for a switch, at least if the values in
the switch are reasonably dense, going back as far as 1977.
If the compiler is smart enough to generate a jump table, it should be
smart enough to generate the same jump for '5' as for all other values
(the missing "default" clause), don't you think so?


Yes indeed.
Jul 22 '05 #6
In article <40**************@sbcglobal.net>,
Thomas Matthews <Th*************************@sbcglobal.net> wrote:
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_right();
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_right();
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?
Maybe, maybe not.
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.


You don't know. And trying to second guess implementations
in this case seems to be programming at the wrong level.
Just to toss more wrenches in, there is also std::map's
and such as well as a good 'ol array of structs you can
build too.
--
Greg Comeau / Comeau C++ 4.3.3, for C++03 core language support
Comeau C/C++ ONLINE ==> http://www.comeaucomputing.com/tryitout
World Class Compilers: Breathtaking C++, Amazing C99, Fabulous C90.
Comeau C/C++ with Dinkumware's Libraries... Have you tried it?
Jul 22 '05 #7
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.


What I like to do when I'm curious about matters like these is to have
the compiler output the assembly code, this can probably be done through
a command line switch. This will give you some clue as to what would
be a common optimalization for this case on your kind of CPU. Trying
different levels of compiler optimizations and looking at the resulting
assembly output can be a good learning experience.

You can also time the program with the different optimization levels to
see what techniques makes the biggest difference.

But this will of course require you to learn some assembly. :)

Learning assembly is a great way to deepen your understanding of
programming anyhow, and would most certainly have given the answer you
were looking for in this case.

Tor
Jul 22 '05 #8
Tor HusabÝ wrote:
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.

What I like to do when I'm curious about matters like these is to have
the compiler output the assembly code, this can probably be done through
a command line switch. This will give you some clue as to what would
be a common optimalization for this case on your kind of CPU. Trying
different levels of compiler optimizations and looking at the resulting
assembly output can be a good learning experience.

You can also time the program with the different optimization levels to
see what techniques makes the biggest difference.

But this will of course require you to learn some assembly. :)

Learning assembly is a great way to deepen your understanding of
programming anyhow, and would most certainly have given the answer you
were looking for in this case.

Tor


Ouch! Seems word wrap in thunderbird M6 is broken! Sorry 'bout that.
Jul 22 '05 #9
"Andrew Koenig" <ar*@acm.org> wrote:
A better solution is to use a lookup table of function pointers:


Why is it better?


But this is obvious! It uses objects (well, at least function pointers
are somewhat similar to objects) and everybody knows that object
orientation is the superiour solution to all problems!

(sorry - I couldn't resist...)

To address the original problem: even if the switch is lamely implemented,
I doubt seriously that this would cause a performance problem. Especially,
in a situation where manual user input is dispatched. On the to other hand,
I would probably implement a move via some parameterization and a table
look-up using just one function for all moves. Of course, this somewhat
depends on what is to be done for the moves...
--
<mailto:di***********@yahoo.com> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>
Jul 22 '05 #10
Thomas Matthews wrote:
[...]
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.


[...]

If there's a performance win for adding the line

case '5': break;

to your code, which doesn't change the meaning, I'd hope an optimizing
compiler could figure that out and do it for you. But the only way to
know is to try.

Compiling with gcc 3.3 with -O4 on Mac OS X, I see that it constructs a
jump table for your case 1, 2, 3, 4, 6, 7, 8, 9. It also does it for
the case 1, 2, 7, 8, 9. It does not, however, do it for the case 1, 2,
8, 9.

It goes without saying, YMMV.

--
Pull out a splinter to reply.
Jul 22 '05 #11
David Rubin wrote:
Thomas Matthews wrote:
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_right();
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_right();
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?

A better solution is to use a lookup table of function pointers:

typedef void (*dfunc)(void);
dfunc move[] = {
0,
move_lower_left,
move_down,
/* ... */
move_upper_right,
};

and then

int d;
dfunc *f;

while(d=getdirection()){
if(f=move[d]){
f();
}
};

/david


The issue isn't about how to better implement a
selection process but about the switch statement.

A switch statement is easier for newbies to understand
than a table of function pointers.

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

Jul 22 '05 #12
Greg Comeau wrote:
In article <40**************@sbcglobal.net>,
Thomas Matthews <Th*************************@sbcglobal.net> wrote:
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_right();
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_right();
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?

Maybe, maybe not.

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.

You don't know. And trying to second guess implementations
in this case seems to be programming at the wrong level.
Just to toss more wrenches in, there is also std::map's
and such as well as a good 'ol array of structs you can
build too.


True, but I was specifically interested in the switch
statement. I didn't know if the compiler's intelligence
would add in a null case to the switch statement to provide
better optimization.

How do you handle it in your compiler?
--
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

Jul 22 '05 #13
Peter Ammon wrote:
Thomas Matthews wrote:
[...]
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.

[...]

If there's a performance win for adding the line

case '5': break;

to your code, which doesn't change the meaning, I'd hope an optimizing
compiler could figure that out and do it for you. But the only way to
know is to try.

Compiling with gcc 3.3 with -O4 on Mac OS X, I see that it constructs a
jump table for your case 1, 2, 3, 4, 6, 7, 8, 9. It also does it for
the case 1, 2, 7, 8, 9. It does not, however, do it for the case 1, 2,
8, 9.

It goes without saying, YMMV.


Thanks for the research.
Perhaps this may have been an issue for news:comp.compilers.

I was wondering if the programmer should provide some information
to help out a compiler, but as others have suggested, outguessing
a compiler is a bad approach.

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

Jul 22 '05 #14
Tor HusabÝ wrote:
Tor HusabÝ wrote:
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.


What I like to do when I'm curious about matters like these is to have
the compiler output the assembly code, this can probably be done
through a command line switch. This will give you some clue as to
what would be a common optimalization for this case on your kind of
CPU. Trying different levels of compiler optimizations and looking at
the resulting assembly output can be a good learning experience.

You can also time the program with the different optimization levels
to see what techniques makes the biggest difference.

But this will of course require you to learn some assembly. :)

Learning assembly is a great way to deepen your understanding of
programming anyhow, and would most certainly have given the answer you
were looking for in this case.

Tor

Ouch! Seems word wrap in thunderbird M6 is broken! Sorry 'bout that.


Well, I know many assembly languages, but I was hoping not to go that
route. I was wondering if the "standard" method for translating
a switch statement would change if one inserted a null statement
to assist the compiler.

But I think I agree with other respondents, in that second guessing
a compiler is a bad approach. Perhaps I should put my optimization
hat on the shelf and put on a different one. :-)

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

Jul 22 '05 #15
Thomas Matthews <Th****************************@sbcglobal.net> wrote:
True, but I was specifically interested in the switch
statement. I didn't know if the compiler's intelligence
would add in a null case to the switch statement to provide
better optimization.


Well, that's the problem, really; there's no such thing as "the"
compiler's intelligence. This compiler may, that compiler may not, and
on that architecture over there it may be a moot point anyway because it
provides function lookup tables in hardware. There's no single answer.

Richard
Jul 22 '05 #16
David Rubin wrote:
Thomas Matthews wrote:
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_right();
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_right();
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?

A better solution is to use a lookup table of function pointers:

typedef void (*dfunc)(void);
dfunc move[] = {
0,
move_lower_left,
move_down,
/* ... */
move_upper_right,
};

and then

int d;
dfunc *f;

while(d=getdirection()){
if(f=move[d]){
f();
}
};

/david


David,

There is no guarantee that the compiler is not translating the
switch statement into a jump table already. Also, a table of
function pointers is more difficult for a newbie, like my son,
to understand.

Given a jump table or a table of function pointers, if the
selectors are contiguous, one can use a mathematical relationship
to access the entries directly rather than searching for them.

If you add the '5' entry as a null entry, you can access the
function pointers as an array:
function_ptr = function_array[direction - '1'];
Which gives O(1) access time. Your solution presents a case
of O(i) time for any index 'i'.

Conversion to a table of function pointers may not be worth
the effort for small cases. I personally only use tables of
function pointers when the selection set is large, non-contiguous,
or subject to change. Menu systems are excellent candidates
for tables. The tables allow one to change the menu without
having to retest the table driver.

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

Jul 22 '05 #17
Andrew Koenig wrote:
"Victor Bazarov" <v.********@comAcast.net> wrote in message
news:4Sx1c.453043$I06.5117172@attbi_s01...

I doubt that. Of course, there _can_ be some _really_ sophisticated
compilers that introduce jump tables, but I've not personally seen one.

When is the last time you checked? I have never seen a C or C++ compiler
that *doesn't* generate a jump table for a switch, at least if the values in
the switch are reasonably dense, going back as far as 1977.

If the compiler is smart enough to generate a jump table, it should be
smart enough to generate the same jump for '5' as for all other values
(the missing "default" clause), don't you think so?

Yes indeed.


Perhaps, I didn't specify my issue correctly.

Let us assume that a switch table is translated using a jump table
(table of function pointers). Then my issue is one of efficiency:

Will adding a null function for case '5' change the optimization from
O(index) to O(1)?

With a non-contiguous set of selectors, one must use a <key, value>
table (key == index value, value == function pointer). The table must
be searched for the key. Worst case, this is O(N) when the key is at
the end of the table.

When the selectors are contiguous (as with the presence of '5'), the
access time can be optimized to O(1) by subtracting an offset from
the index and using the new value to index an array of function
pointers. With my original switch statement, the access becomes:
function_pointer = switch_table[direction - '1'];
{Assuming that '1'..'9' are contiguous in the collation sequence}

So my question is: are compilers smart enough these days to insert
null functions to convert from O(i) {or O(N)} to O(1)?

Also, would a better option be for the programmer to insert a null
function for '5'?

BTW, thanks Victor & Andrew for replying. I know you guys
are busy.

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

Jul 22 '05 #18
In message <EI*******************@newssvr33.news.prodigy.co m>
Thomas Matthews <Th****************************@sbcglobal.net> wrote:
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?


True, but I was specifically interested in the switch
statement. I didn't know if the compiler's intelligence
would add in a null case to the switch statement to provide
better optimization.

How do you handle it in your compiler?


Ours definitely would add in a null case. The code would come out like:

; a1 = direction
SUB a1,a1,#'1' ; reduce a1 to 0-3,5-8 for our cases
CMP a1,#8
ADDLS pc,pc,a1,LSL #2 ; jump into branch table if <= 8
B endofswitch
B case1
B case2
B case3
B case4
B endofswitch
B case6
B case7
B case8
BL move_upper_right ; case 9
endofswitch
; ... following code here
; somewhere else
case1
BL move_lower_left
B endofswitch
case2
BL move_down
B endofswitch
; ... then other cases

Typically it will tend to use a branch table if there are 5 or more cases
and they cover at least half the range of values. They can also be used for
dense parts of an otherwise sparse switch.

I think this sort of behaviour is probably pretty typical among compilers.
I really wouldn't worry about adding fake cases just to create a contiguous
range. But if you are switching on some arbitrary internal constants (enums
or whatever), it is probably best to make those constants small and
contiguous, rather than large and irregular.

Other stunts that may or may not occur might be to spot things like:

switch (x)
{
case 0x100: ...
case 0x200: ...
case 0x300: ...
case 0x400: ...
}

which though sparse, can be reduced to a branch table with a little shifting.
Our compiler does this, but I'm not sure I've ever seen any code it actually
helps :)

I'm currently looking at how best to implement switches on long long
expressions (ie ones bigger than a machine word size). C99 requires this, and
it's a bit of a pain. But I suppose the precedent was already set in that you
could switch on a "long", which may have been bigger than a word in some
architectures.

--
Kevin Bracey, Principal Software Engineer
Tematic Ltd Tel: +44 (0) 1223 503464
182-190 Newmarket Road Fax: +44 (0) 1223 503458
Cambridge, CB5 8HE, United Kingdom WWW: http://www.tematic.com/
Jul 22 '05 #19

"Thomas Matthews" <Th****************************@sbcglobal.net> wrote in
message news:v0*******************@newssvr33.news.prodigy. com...
Will adding a null function for case '5' change the optimization from
O(index) to O(1)?
Not with any compiler I've ever seen. They would all do one of two things:

1) Recognize that the table is nearly dense, so use a jump table with
the case for 5 pointing to the "default:" label, or

2) Create two jump tables and insert one extra test.

It is only when there are huge gaps in the values of the cases that the
typical compiler will abandon the jump-table approach, and even then, the
ones I've seen will use binary searching or hashing to get the execution
time well below the number of keys (at least when there are many of them).
With a non-contiguous set of selectors, one must use a <key, value>
table (key == index value, value == function pointer). The table must
be searched for the key. Worst case, this is O(N) when the key is at
the end of the table.
If you do a linear search, which you don't need to do.
When the selectors are contiguous (as with the presence of '5'), the
access time can be optimized to O(1) by subtracting an offset from
the index and using the new value to index an array of function
pointers.


Of course, calling a function typically takes longer than simply doing a
jump, so if you really care about execution speed to that degree, you are
likely to find that even on a mediocre compiler, a switch will be faster
than indexing a table of function pointers.

If these differences are important to you, there is no getting around having
to measure your compiler and see what it does.
Jul 22 '05 #20
In article <EI*******************@newssvr33.news.prodigy.com> ,
Thomas Matthews <Th**************************@sbcglobal.net> wrote:
Greg Comeau wrote:
In article <40**************@sbcglobal.net>,
Thomas Matthews <Th*************************@sbcglobal.net> wrote:
.....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_right();
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_right();
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?


Maybe, maybe not.
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.


You don't know. And trying to second guess implementations
in this case seems to be programming at the wrong level.
Just to toss more wrenches in, there is also std::map's
and such as well as a good 'ol array of structs you can
build too.


True, but I was specifically interested in the switch
statement. I didn't know if the compiler's intelligence
would add in a null case to the switch statement to provide
better optimization.

How do you handle it in your compiler?


Some will add the 5 for you. It depends upon its algorithms,
how it "weights" such a situation, etc.
--
Greg Comeau / Comeau C++ 4.3.3, for C++03 core language support
Comeau C/C++ ONLINE ==> http://www.comeaucomputing.com/tryitout
World Class Compilers: Breathtaking C++, Amazing C99, Fabulous C90.
Comeau C/C++ with Dinkumware's Libraries... Have you tried it?
Jul 22 '05 #21
In article <1L*******************@newssvr33.news.prodigy.com> ,
Thomas Matthews <Th**************************@sbcglobal.net> wrote:
I was wondering if the programmer should provide some information
to help out a compiler,
Like a pragma.
but as others have suggested, outguessing
a compiler is a bad approach.


Probably. The things is that even if you can provide
results like the other poster did, you don't know if it's
going to do the same thing with another group. Even
if this is an argument for say open source, the thing
is that you don't know if the next release is going to
do it the same way, blah blah.
--
Greg Comeau / Comeau C++ 4.3.3, for C++03 core language support
Comeau C/C++ ONLINE ==> http://www.comeaucomputing.com/tryitout
World Class Compilers: Breathtaking C++, Amazing C99, Fabulous C90.
Comeau C/C++ with Dinkumware's Libraries... Have you tried it?
Jul 22 '05 #22
"Thomas Matthews" <Th*************************@sbcglobal.net> wrote
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_right();
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_right();
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.


Does your son type faster than your computer can execute a switch statement?

Claudio Puviani
Jul 22 '05 #23
Thomas Matthews wrote:
David Rubin wrote:
Thomas Matthews wrote:
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_right();
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_right();
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?
A better solution is to use a lookup table of function pointers:

typedef void (*dfunc)(void);
dfunc move[] = {
0,
move_lower_left,
move_down,
/* ... */
move_upper_right,
};

and then

int d;
dfunc *f;

while(d=getdirection()){
if(f=move[d]){
f();
}
};

/david


David,

There is no guarantee that the compiler is not translating the
switch statement into a jump table already.


This is irrelevent.
Also, a table of
function pointers is more difficult for a newbie, like my son,
to understand.
There is always opportunity to learn new things.
Given a jump table or a table of function pointers, if the
selectors are contiguous, one can use a mathematical relationship
to access the entries directly rather than searching for them.

If you add the '5' entry as a null entry, you can access the
function pointers as an array:
function_ptr = function_array[direction - '1'];
Which gives O(1) access time. Your solution presents a case
of O(i) time for any index 'i'.
This is incorrect. Both the switch statement and the table ought to
yield O(1) access time. The table is accessed as I have shown. You are
implying that there is a linear search.

In any case, one difference might be in the way switch statements are
translated into lower-level instructions. For example, a switch
statement might be broken into a set of "break on equal" instructions:

beq direction, 1, move_lower_left
beq direction, 2, move_down

The basic idea is that you test the first operand for equality with the
second, and then jump to an address or fall through to the next instruction.

The table of function pointers might translate to an addition,
move + d; a dereference, *(move + d); and a function call,
fcall *(move + d).

Although this is all off topic, these are the kinds of
implementation-dependent issues that you have to consider when you ask
questions about micro-optimizations.
Conversion to a table of function pointers may not be worth
the effort for small cases. I personally only use tables of
function pointers when the selection set is large, non-contiguous,
or subject to change. Menu systems are excellent candidates
for tables. The tables allow one to change the menu without
having to retest the table driver.


This is similar what I said elsethread, except tables are actually much
better in terms of memory usage when the selection set (or range) is
contiguous, or if there is a mapping from the range to the set {0,1,2,...}.

Anyway, the main goal you should always have in mind is to keep the code
readable. In the switch statement you presented, the valid choices are
clear. If you added a case for '5' which did nothing, it might be
confusing; I might expect this case to be ignored completely. If you
want to validate your range in the same switch statement, you might want
a case for '5', and a default case which handles a range-error. However,
if you add a case for '5' because about how discontinuities in your
input range affect the speed and size of the program, I'd say you are
going down the wrong path.

/david

--
"As a scientist, Throckmorton knew that if he were ever to break wind in
the echo chamber, he would never hear the end of it."

Jul 22 '05 #24
Julie <ju***@aol.com> wrote:
# David Rubin wrote:
# >
# > Thomas Matthews wrote:
# > > 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; */

# > > My question is: Would adding a case for '5' reduce
# > > the code space and execution time for this switch
# > > statement?

It's a quality of implementation issue that has no general answer. The
implementation might recognise the missing 5 as a junmp to esac and
insert that in a jump table. It might be serially testing each case no
matter what. It might be using a binary tree or hash table. No way to know
in general.

# > A better solution is to use a lookup table of function pointers:

# That's what I was thinking. But you can even optimize away the if() by
# creating a null function for the '5', something like:

If you want fast, you don't want function pointers. The're very hard to
optimise.

--
Derk Gwen http://derkgwen.250free.com/html/index.html
I'm not even supposed to be here today.
Jul 22 '05 #25
di***********@yahoo.com (Dietmar Kuehl) wrote in message news:<5b**************************@posting.google. com>...
"Andrew Koenig" <ar*@acm.org> wrote:
A better solution is to use a lookup table of function pointers:


Why is it better?


But this is obvious! It uses objects (well, at least function pointers
are somewhat similar to objects) and everybody knows that object
orientation is the superiour solution to all problems!

(sorry - I couldn't resist...)

To address the original problem: even if the switch is lamely implemented,
I doubt seriously that this would cause a performance problem. Especially,
in a situation where manual user input is dispatched. On the to other hand,
I would probably implement a move via some parameterization and a table
look-up using just one function for all moves. Of course, this somewhat
depends on what is to be done for the moves...


Yes. I note that the switch statement in the OP called functions with
names like move_lower_left(), move_down(), etc. If the logic is similar
for all eight directions, you might find it makes more sense to have
one function, move(int x, int y), where the parameters represent the
distance to move (postive or negative) along each axis.

If you take this approach, you could process keyboard input by using
a lookup table to get the parameters. Here's an example:

struct Point
{
int x, y;
};

inline const Point& DirectionFromChar(char input)
{
static const Point table[] =
{
{ -1, -1 }, // '1'
{ 0, -1 }, // '2'
{ 1, -1 }, // '3'
{ -1, 0 }, // '4'
{ 0, 0 }, // table[4]
{ 1, 0 }, // '6'
{ -1, 1 }, // '7'
{ 0, 1 }, // '8'
{ 1, 1 }, // '9'
};
const int i = input - '1';
return table[ i >= 0 && i <= 9 ? i : 4 ];
}

With respect to your original question, if you can insert

case '5':
break;

into the source code, what makes you think the compiler
can'd do it for you? I generated an assembly listing from
your code using VC7.1 and found that it did exactly that.

You should think twice about making low-level optimizations
like this. Write your code in a way that makes sense, and
let the compiler do its job. If you try to second-guess the
optimizer, you may actually end up working against it. At
best, you might make your code faster for one version of
your compiler, at the cost of (1) making your code less
readable, and (2) potentially make your code *slower* on
other compilers or future versions. It's almost always
best to write your code in the way that most clearly
expresses your intent.
Jul 22 '05 #26
In article <v0*******************@newssvr33.news.prodigy.com> ,
Thomas Matthews <Th**************************@sbcglobal.net> wrote:
Perhaps, I didn't specify my issue correctly.

Let us assume that a switch table is translated using a jump table
(table of function pointers). Then my issue is one of efficiency:

Will adding a null function for case '5' change the optimization from
O(index) to O(1)?

With a non-contiguous set of selectors, one must use a <key, value>
table (key == index value, value == function pointer). The table must
be searched for the key. Worst case, this is O(N) when the key is at
the end of the table.
Binary search is always an option (and I'm sure some compiler somewhere will
create a hash table if the values get sufficiently sparse). I'd be very
disappointed in a compiler that didn't do better than O(n) in the case you
describe.
When the selectors are contiguous (as with the presence of '5'), the
access time can be optimized to O(1) by subtracting an offset from
the index and using the new value to index an array of function
pointers.


You can do that even if there are gaps. Just have the gaps point to an
empty function. As long as there aren't too many gaps this will be a
perfectly servicable solution.

Any compiler that can't handle this sort of situation with ease probably
can't be relied upon to optimize much of anything.

OTOH, there is a case for putting

case '5':
// No movement
break;

in your code, just to reassure future generations that you didn't forget
anything.

Alan
--
Defendit numerus
Jul 22 '05 #27
Thomas Matthews wrote:

My question is: Would adding a case for '5' reduce
the code space and execution time for this switch
statement?


Hmmmm if I had to rely on this type of optimization to gain
any measurable performance I think I'd give up and go home.

These micro-level optimizations are hardly ever worth the
time even considering. In the rare circumstances that they
are significant to your application then you ought to
examine the assempler output from your given compiler
version and platform. Though such knowledge may be redundant
with the next compiler release.

Jul 22 '05 #28

"Thomas Matthews" <Th****************************@sbcglobal.net> wrote in
message news:tG******************@newssvr33.news.prodigy.c om...
David Rubin wrote:
Thomas Matthews wrote:


The issue isn't about how to better implement a
selection process but about the switch statement.

A switch statement is easier for newbies to understand
than a table of function pointers.


And 'if/else' even easier, typically. It's closer to English.
This is exactly the right point. Readability. Clarity
of expression.

But you were originally asking about 'efficiency' and
'optimization'. Don't worry about that unless measurable
performance fails to meet requirements. Then profile.
Only then consider design or implementation changes.

-Mike
Jul 22 '05 #29
The following article discusses different actions taken by
compilers for switch statement code generation:

http://www.eventhelix.com/RealtimeMa...anslation3.htm

Sandeep
--
http://www.EventHelix.com/EventStudio
EventStudio 2.0 - System Architecture Design CASE Tool
Jul 22 '05 #30
Thomas Matthews <Th*************************@sbcglobal.net> wrote in message news:<40**************@sbcglobal.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
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_right();
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_right();
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.learn.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

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

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 (pa*****@cc.helsinki.fi) ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
"This is a personnel commuter."
- Train driver in Scientific American
Jul 22 '05 #32
1st off,dont toppost:
http://www.parashift.com/c++-faq-lite/how-to-post.html

mehul raval wrote:
Thomas Matthews <Th*************************@sbcglobal.net> wrote in message news:<40**************@sbcglobal.net>...
hi ,
if i am not mistaken adding a case for 5 wont reduce the code length,
instead it wld become more.
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.

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

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

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.
y bother mking my own func ptr thing when da compilr do it 4 me.

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
[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.
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_right();
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_right();
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.

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

Jul 22 '05 #33
Thomas Matthews wrote:
[...]
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': [...'2', '3', '4', '6', '7', and '8', but no '5' ...] case '9':
move_upper_right();
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?
It depends entirely on the compiler.
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.


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

Jul 22 '05 #34

"Thomas Matthews" <Th*************************@sbcglobal.net> wrote in
message news:40**************@sbcglobal.net...
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_right();
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_right();
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.}

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!
--
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
http://www.sgi.com/tech/stl -- Standard Template Library

Jul 22 '05 #35
Thomas Matthews wrote:

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)
{ .... snip coding ... } /* 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?
.... snip ...
{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.}


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 (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Jul 22 '05 #36

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

37
by: Thomas Matthews | last post by:
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 ...
10
by: anon.asdf | last post by:
Here's a reminder of duff's device: /*************************************/ #include <stdio.h> #define STEP 8 #define MAX_LEN STEP*4+1...
0
by: tammygombez | last post by:
Hey fellow JavaFX developers, I'm currently working on a project that involves using a ComboBox in JavaFX, and I've run into a bit of an issue....
0
by: tammygombez | last post by:
Hey everyone! I've been researching gaming laptops lately, and I must say, they can get pretty expensive. However, I've come across some great...
0
better678
by: better678 | last post by:
Question: Discuss your understanding of the Java platform. Is the statement "Java is interpreted" correct? Answer: Java is an object-oriented...
0
by: Kemmylinns12 | last post by:
Blockchain technology has emerged as a transformative force in the business world, offering unprecedented opportunities for innovation and...
0
by: CD Tom | last post by:
This happens in runtime 2013 and 2016. When a report is run and then closed a toolbar shows up and the only way to get it to go away is to right...
0
by: CD Tom | last post by:
This only shows up in access runtime. When a user select a report from my report menu when they close the report they get a menu I've called Add-ins...
0
jalbright99669
by: jalbright99669 | last post by:
Am having a bit of a time with URL Rewrite. I need to incorporate http to https redirect with a reverse proxy. I have the URL Rewrite rules made...
0
by: antdb | last post by:
Ⅰ. Advantage of AntDB: hyper-convergence + streaming processing engine In the overall architecture, a new "hyper-convergence" concept was...
0
by: Matthew3360 | last post by:
Hi there. I have been struggling to find out how to use a variable as my location in my header redirect function. Here is my code. ...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.