Optimizing a switch statement

[Thomas Matthews]

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

[David Rubin]

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

[Victor Bazarov]

"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

[Julie]

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]();
};

[Andrew Koenig]

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

Why is it better?

[Andrew Koenig]

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

[Greg Comeau]

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?

[Tor Husabø]

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

[Tor Husabø]

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.

[Dietmar Kuehl]

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

[Peter Ammon]

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.

[Thomas Matthews]

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

[Thomas Matthews]

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

[Thomas Matthews]

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

[Thomas Matthews]

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

[Richard Bos]

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

[Thomas Matthews]

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

[Thomas Matthews]

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

[Kevin Bracey]

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: [phone]
182-190 Newmarket Road Fax: [phone]
Cambridge, CB5 8HE, United Kingdom WWW: http://www.tematic.com/

[Andrew Koenig]

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

[Greg Comeau]

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?

[Greg Comeau]

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?

[Claudio Puviani]

"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

[David Rubin]

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

[Derk Gwen]

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.

[Niklas Borson]

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.

[Alan Morgan]

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

[lilburne]

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.

[Mike Wahler]

"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

[EventHelix.com]

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

[mehul raval]

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

[Joona I Palaste]

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

[Thomas Matthews]

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

[Kenneth Brody]

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

[Nick Hounsome]

"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

[CBFalconer]

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!