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]

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

 

[Victor Bazarov]

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]

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]

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]

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.

 

[=?ISO-8859-1?Q?Tor_Husab=F8?=]

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

 

[=?ISO-8859-1?Q?Tor_Husab=F8?=]

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]

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

 

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

 

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

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]

Maybe, maybe not.




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]

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

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]

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]

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]

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.




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

 

[Greg Comeau]

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]

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.