Optimizing a switch statement

[Kevin Bracey]

In message <[email protected]>

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.

 

[Andrew Koenig]

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.

 

[Claudio Puviani]

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]

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

 

[Derk Gwen]

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

 

[Niklas Borson]

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]

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

 

[lilburne]

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]

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/RealtimeMantra/Basics/CToAssemblyTranslation3.htm

Sandeep

 

[mehul raval]

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

 

[Joona I Palaste]

mehul raval <[email protected]> scribbled the following

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.

 

[Thomas Matthews]

1st off,dont toppost:
http://www.parashift.com/c++-faq-lite/how-to-post.html

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.


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

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!

 

[CBFalconer]

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