switch vs. if

[Denis Remezov]

Hello all,

Consider the case of an if with many else if clauses vs. a switch with many
cases.

In thinking about how such control constructs would likely be implemented,
it would seem that neither would be superior to the other in terms of
execution speed of the generated code.

Would others agree that this is true for "typical" implementations?

Thanks,
Dave

For some reason I always expected the compilers to optimise a long switch
statement by using binary search. Now, the interesting part is that
gcc 3.3.3 appears to do exactly that (O(log n)), unless the range of values
is compact, in which case it uses a table (O(const)).
The if statement, on the other hand, in my tests was implemented literally,
without any clever optimisation.

For long selection lists the difference can be measurable. Though it comforts
me to think of it as of a potential bonus, I'd pick a switch over if whenever
appropriate regardless of the performance.

Denis

 

[Dave]

Hello all,

Consider the case of an if with many else if clauses vs. a switch with many
cases.

In thinking about how such control constructs would likely be implemented,
it would seem that neither would be superior to the other in terms of
execution speed of the generated code.

Would others agree that this is true for "typical" implementations?

Thanks,
Dave

 

[Victor Bazarov]

Consider the case of an if with many else if clauses vs. a switch with many
cases.

In thinking about how such control constructs would likely be implemented,
it would seem that neither would be superior to the other in terms of
execution speed of the generated code.

Would others agree that this is true for "typical" implementations?

It is probably true. I've never written an optimizing C++ compiler, so
I can't say I know what's involved. But it does seem that a 'switch'
statement with its very direct and straightforward approach would be
actually easier to implement as a table than an 'if' statement. Besides,
the 'switch' cannot really be screwed up by sudden introduction of some
arbitrary expression (during code maintenance, I mean).

V

 

[Jimmy_B]

Consider the case of an if with many else if clauses vs. a switch with many
cases.

In thinking about how such control constructs would likely be implemented,
it would seem that neither would be superior to the other in terms of
execution speed of the generated code.

Would others agree that this is true for "typical" implementations?

No. Any half-decent compiler will reduce a switch statement to a jump
table, which is O(1) to the number of cases (assuming the cases are
sequential). A series of if-else statements will be reduced only by an
exceedingly clever compiler, and if compiled in the usual way will be O(n)
to the number of cases. An if statement will produce code with size
proportional to the number of cases, whereas a switch statement may produce
a very large mostly-empty table if the cases are sparse (depending on your
compiler.)

In fact, a switch statement is conceptually much more like a jump table
than like a series of if-else statements. Consider Duff's Device, for example:
switch(count%8){
case 0: do{ *to = *from++;
case 7: *to = *from++;
case 6: *to = *from++;
case 5: *to = *from++;
case 4: *to = *from++;
case 3: *to = *from++;
case 2: *to = *from++;
case 1: *to = *from++;
}while(--n>0);
}

 

[Mike Wahler]

Hello all,

Consider the case of an if with many else if clauses vs. a switch with many
cases.

In thinking about how such control constructs would likely be implemented,
it would seem that neither would be superior to the other in terms of
execution speed of the generated code.

Would others agree that this is true for "typical" implementations?

I advise not worrying about 'performance', but to write
the code to be as clear and readable as possible. Make
the code maintainable. Programmer time is far more
expensive than computer time.

IMO two or three conditions would probably be best served
with 'if' and 'else', whereas more conditions than than would
probably be most clearly expressed with a 'switch'. And
if the number of conditions becomes excessive, consider
e.g. a table of function pointers (perhaps stored in a
std::map).

Only concern yourself with optimization after you've
empirically proven that the code's performance is
unacceptable. If that is the case, then use a profiler
to find out where the slowdowns really are (they're
frequently not where you'd think). An improvement in
performance is more typically gained by optimizing
the 'higher level' algorithm(s) than messing around
with 'micro-optimizations', which imo is the job of
the compiler.

-Mike

 

[Siemel Naran]

I advise not worrying about 'performance', but to write
the code to be as clear and readable as possible. Make
the code maintainable. Programmer time is far more
expensive than computer time.

Usually, switch case looks better to me, but I've gotten used to both ways.
For complex cases, it's best to use the command pattern, where there are
many objects and each implements a virtual function defined as pure virtual
in the base class.

IMO two or three conditions would probably be best served
with 'if' and 'else', whereas more conditions than than would
probably be most clearly expressed with a 'switch'. And
if the number of conditions becomes excessive, consider
e.g. a table of function pointers (perhaps stored in a
std::map).

Right, or the command pattern.

 

[red floyd]

For some reason I always expected the compilers to optimise a long switch
statement by using binary search. Now, the interesting part is that
gcc 3.3.3 appears to do exactly that (O(log n)), unless the range of values
is compact, in which case it uses a table (O(const)).
The if statement, on the other hand, in my tests was implemented literally,
without any clever optimisation.

For long selection lists the difference can be measurable. Though it comforts
me to think of it as of a potential bonus, I'd pick a switch over if whenever
appropriate regardless of the performance.

Denis

Zilog's old Z8000 compilers took advantage of the instruction set and generated
a jump table even for noncontiguous values.

 

[Bob Hairgrove]

Hello all,

Consider the case of an if with many else if clauses vs. a switch with many
cases.

In thinking about how such control constructs would likely be implemented,
it would seem that neither would be superior to the other in terms of
execution speed of the generated code.

Not true. The switch expression need be evaluated only once, whereas
each if expression must be independently evaluated (or at least enough
of it to return its Boolean result).

Would others agree that this is true for "typical" implementations?

I suppose one could generate an assembly listing from a "typical"
compilation and examine the way the compiler has done it. "Typical"
doesn't necessarily mean anything, does it?

As someone else pointed out, you can usually do away with both if you
have properly designed your classes with virtual functions.

 

[Thomas Matthews]

Hello all,

Consider the case of an if with many else if clauses vs. a switch with many
cases.

In thinking about how such control constructs would likely be implemented,
it would seem that neither would be superior to the other in terms of
execution speed of the generated code.

Would others agree that this is true for "typical" implementations?

Thanks,
Dave

Hmmm, remember the third alternative. (I.e. most of the timer there
is always a third alternative, not just black or white.)

One can also implement a jump table (a table of function pointers),
instead of the above. On benefit to the table drive approach is
that the executable code doesn't need to be retested; the data
is changed not the driver. On the other hand, there are cases
where the table can be used as premature optimization (in which
your wasting programming time for a construct that the compiler
will automatically generate).

I've just learned, the hard way, about converting all switch
statements into function tables. Sometimes, switch statements
can be a lot easier to read than a function table.

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