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

[David Rubin]

Re: Optimizing a switch statement

Thomas Matthews wrote:[color=blue]
> Hi,
>
> My son is writing a program to move a character. He is
> using the numbers on the keypad to indicate the direction
> of movement:
> 7 8 9
> 4 5 6
> 1 2 3
> Each number has a direction except for '5'. So in
> his switch statement, he omits a case for '5':
> /* char direction; */
> switch (direction)
> {
> case '1':
> move_lower_left ();
> break;
> case '2':
> move_down();
> break;
> case '3':
> move_lower_righ t();
> break;
> case '4':
> move_left();
> break;
> case '6':
> move_right();
> break;
> case '7':
> move_upper_left ();
> break;
> case '8':
> move_up();
> break;
> case '9':
> move_upper_righ t();
> break;
> } /* end switch direction */
>
> The case selectors are not contiguous in the above
> example, since case '5' is omitted (on purpose).
>
> My question is: Would adding a case for '5' reduce
> the code space and execution time for this switch
> statement?[/color]

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

[Victor Bazarov]

Re: Optimizing a switch statement

"Thomas Matthews" <Thomas_Matthew sSpamBotsSuck@s bcglobal.net> wrote...[color=blue]
> My son is writing a program to move a character. He is
> using the numbers on the keypad to indicate the direction
> of movement:
> 7 8 9
> 4 5 6
> 1 2 3
> Each number has a direction except for '5'. So in
> his switch statement, he omits a case for '5':
> /* char direction; */
> switch (direction)
> {
> 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?[/color]

I doubt that. Of course, there _can_ be some _really_ sophisticated
compilers that introduce jump tables, but I've not personally seen one.
[color=blue]
> The logic behind this is that a contigous set of
> case selectors would allow the compiler to create
> a "jump table", where as the above example may
> force the compiler to generate an "if-elseif"
> ladder.[/color]

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]

Re: Optimizing a switch statement

David Rubin wrote:[color=blue]
>
> Thomas Matthews wrote:[color=green]
> > Hi,
> >
> > My son is writing a program to move a character. He is
> > using the numbers on the keypad to indicate the direction
> > of movement:
> > 7 8 9
> > 4 5 6
> > 1 2 3
> > Each number has a direction except for '5'. So in
> > his switch statement, he omits a case for '5':
> > /* char direction; */
> > switch (direction)
> > {
> > case '1':
> > move_lower_left ();
> > break;
> > case '2':
> > move_down();
> > break;
> > case '3':
> > move_lower_righ t();
> > break;
> > case '4':
> > move_left();
> > break;
> > case '6':
> > move_right();
> > break;
> > case '7':
> > move_upper_left ();
> > break;
> > case '8':
> > move_up();
> > break;
> > case '9':
> > move_upper_righ t();
> > break;
> > } /* end switch direction */
> >
> > The case selectors are not contiguous in the above
> > example, since case '5' is omitted (on purpose).
> >
> > My question is: Would adding a case for '5' reduce
> > the code space and execution time for this switch
> > statement?[/color]
>
> 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
>[/color]

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

[Andrew Koenig]

Re: Optimizing a switch statement

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

Why is it better?

[Andrew Koenig]

Re: Optimizing a switch statement


"Victor Bazarov" <v.Abazarov@com Acast.net> wrote in message
news:4Sx1c.4530 43$I06.5117172@ attbi_s01...
[color=blue]
> I doubt that. Of course, there _can_ be some _really_ sophisticated
> compilers that introduce jump tables, but I've not personally seen one.[/color]

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.
[color=blue]
> 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?[/color]

Yes indeed.

[Greg Comeau]

Re: Optimizing a switch statement

In article <4046A691.10509 04@sbcglobal.ne t>,
Thomas Matthews <Thomas_Matthew sSpamBotsSuck@s bcglobal.net> wrote:[color=blue]
>My son is writing a program to move a character. He is
>using the numbers on the keypad to indicate the direction
>of movement:
> 7 8 9
> 4 5 6
> 1 2 3
>Each number has a direction except for '5'. So in
>his switch statement, he omits a case for '5':
>/* char direction; */
> switch (direction)
> {
> 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?[/color]

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

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

Re: Optimizing a switch statement

[color=blue]
> My question is: Would adding a case for '5' reduce
> the code space and execution time for this switch
> statement?
>
> The logic behind this is that a contigous set of
> case selectors would allow the compiler to create
> a "jump table", where as the above example may
> force the compiler to generate an "if-elseif"
> ladder.[/color]

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

Re: Optimizing a switch statement

Tor Husabø wrote:
[color=blue]
>[color=green]
>> My question is: Would adding a case for '5' reduce
>> the code space and execution time for this switch
>> statement?
>>
>> The logic behind this is that a contigous set of
>> case selectors would allow the compiler to create
>> a "jump table", where as the above example may
>> force the compiler to generate an "if-elseif"
>> ladder.[/color]
>
>
> 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[/color]

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

[Dietmar Kuehl]

Re: Optimizing a switch statement

"Andrew Koenig" <ark@acm.org> wrote:[color=blue][color=green]
> > A better solution is to use a lookup table of function pointers:[/color]
>
> Why is it better?[/color]

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:dietmar _kuehl@yahoo.co m> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.co m/>

[Peter Ammon]

Re: Optimizing a switch statement

Thomas Matthews wrote:
[...][color=blue]
> My question is: Would adding a case for '5' reduce
> the code space and execution time for this switch
> statement?
>
> The logic behind this is that a contigous set of
> case selectors would allow the compiler to create
> a "jump table", where as the above example may
> force the compiler to generate an "if-elseif"
> ladder.[/color]

[...]

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]

Re: Optimizing a switch statement

David Rubin wrote:[color=blue]
> Thomas Matthews wrote:
>[color=green]
>> Hi,
>>
>> My son is writing a program to move a character. He is
>> using the numbers on the keypad to indicate the direction
>> of movement:
>> 7 8 9
>> 4 5 6
>> 1 2 3
>> Each number has a direction except for '5'. So in
>> his switch statement, he omits a case for '5':
>> /* char direction; */
>> switch (direction)
>> {
>> case '1':
>> move_lower_left ();
>> break;
>> case '2':
>> move_down();
>> break;
>> case '3':
>> move_lower_righ t();
>> break;
>> case '4':
>> move_left();
>> break;
>> case '6':
>> move_right();
>> break;
>> case '7':
>> move_upper_left ();
>> break;
>> case '8':
>> move_up();
>> break;
>> case '9':
>> move_upper_righ t();
>> break;
>> } /* end switch direction */
>>
>> The case selectors are not contiguous in the above
>> example, since case '5' is omitted (on purpose).
>>
>> My question is: Would adding a case for '5' reduce
>> the code space and execution time for this switch
>> statement?[/color]
>
>
> 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
>[/color]

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

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

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

[Thomas Matthews]

Re: Optimizing a switch statement

Greg Comeau wrote:
[color=blue]
> In article <4046A691.10509 04@sbcglobal.ne t>,
> Thomas Matthews <Thomas_Matthew sSpamBotsSuck@s bcglobal.net> wrote:
>[color=green]
>>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?[/color]
>
>
> Maybe, maybe not.
>
>[color=green]
>>The logic behind this is that a contigous set of
>>case selectors would allow the compiler to create
>>a "jump table", where as the above example may
>>force the compiler to generate an "if-elseif"
>>ladder.[/color]
>
>
> 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.[/color]

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

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

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

[Thomas Matthews]

Re: Optimizing a switch statement

Peter Ammon wrote:
[color=blue]
> Thomas Matthews wrote:
> [...]
>[color=green]
>> My question is: Would adding a case for '5' reduce
>> the code space and execution time for this switch
>> statement?
>>
>> The logic behind this is that a contigous set of
>> case selectors would allow the compiler to create
>> a "jump table", where as the above example may
>> force the compiler to generate an "if-elseif"
>> ladder.[/color]
>
>
> [...]
>
> 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.
>[/color]

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

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

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

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

[Thomas Matthews]

Re: Optimizing a switch statement

Tor Husabø wrote:
[color=blue]
> Tor Husabø wrote:
>[color=green]
>>[color=darkred]
>>> My question is: Would adding a case for '5' reduce
>>> the code space and execution time for this switch
>>> statement?
>>>
>>> The logic behind this is that a contigous set of
>>> case selectors would allow the compiler to create
>>> a "jump table", where as the above example may
>>> force the compiler to generate an "if-elseif"
>>> ladder.[/color]
>>
>>
>>
>> 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[/color]
>
>
> Ouch! Seems word wrap in thunderbird M6 is broken! Sorry 'bout that.[/color]

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

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

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