473,587 Members | 2,607 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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_righ t();
break;
case '4':
move_left();
break;
case '6':
move_right();
break;
case '7':
move_upper_left ();
break;
case '8':
move_up();
break;
case '9':
move_upper_righ t();
break;
} /* end switch direction */

The case selectors are not contiguous in the above
example, since case '5' is omitted (on purpose).

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

The logic behind this is that a contigous set of
case selectors would allow the compiler to create
a "jump table", where as the above example may
force the compiler to generate an "if-elseif"
ladder.

{I cross posted to the three newsgroups because
this issue deals with a switch statement which
exists in both the C and C++ languages. This
may also be of interest to newbies, like my son.}

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.l earn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book
http://www.sgi.com/tech/stl -- Standard Template Library

Jul 22 '05 #1
35 8319
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_righ t();
break;
case '4':
move_left();
break;
case '6':
move_right();
break;
case '7':
move_upper_left ();
break;
case '8':
move_up();
break;
case '9':
move_upper_righ t();
break;
} /* end switch direction */

The case selectors are not contiguous in the above
example, since case '5' is omitted (on purpose).

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


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_righ t,
};

and then

int d;
dfunc *f;

while(d=getdire ction()){
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************ *************@s bcglobal.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_righ t();
break;
case '4':
move_left();
break;
case '6':
move_right();
break;
case '7':
move_upper_left ();
break;
case '8':
move_up();
break;
case '9':
move_upper_righ t();
break;
} /* end switch direction */

The case selectors are not contiguous in the above
example, since case '5' is omitted (on purpose).

My question is: Would adding a case for '5' reduce
the code space and execution time for this switch
statement?
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_righ t();
break;
case '4':
move_left();
break;
case '6':
move_right();
break;
case '7':
move_upper_left ();
break;
case '8':
move_up();
break;
case '9':
move_upper_righ t();
break;
} /* end switch direction */

The case selectors are not contiguous in the above
example, since case '5' is omitted (on purpose).

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


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_righ t,
};

and then

int d;
dfunc *f;

while(d=getdire ction()){
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=getdire ction()){
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.********@com Acast.net> wrote in message
news:4Sx1c.4530 43$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.ne t>,
Thomas Matthews <Th************ *************@s bcglobal.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_righ t();
break;
case '4':
move_left();
break;
case '6':
move_right();
break;
case '7':
move_upper_left ();
break;
case '8':
move_up();
break;
case '9':
move_upper_righ t();
break;
} /* end switch direction */

The case selectors are not contiguous in the above
example, since case '5' is omitted (on purpose).

My question is: Would adding a case for '5' reduce
the code space and execution time for this switch
statement?
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 parameterizatio n 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.co m> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.co m/>
Jul 22 '05 #10

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

Similar topics

37
681
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 5 6 1 2 3 Each number has a direction except for '5'. So in his switch statement, he omits a case for '5':
10
2423
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 #define SOURCE_LEN 28
0
7918
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main...
0
8206
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. ...
0
8340
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that...
1
7967
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
0
6621
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then...
1
5713
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes...
0
3840
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in...
1
1452
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
0
1185
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating...

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.