switch and if..else same at assemby code ?

[hasadh]

Hi,

is the assemly code for if..else and switch statements similar. I
would like to know if switch also uses value comparison for each case
internally or does it
jump to the case directly at the assembly level ?

for a performance critical application is it better to to use switch
case or
accomplish the same using fn pointers ?
please advice.

Thanks for your time.
prakash

 

[Richard Tobin]

is the assemly code for if..else and switch statements similar. I
would like to know if switch also uses value comparison for each case
internally or does it jump to the case directly at the assembly level ?

It depends on the implementation. Quite likely it will compile to a jump
table if all (or most) of the values are contiguous, and use conditionals
if they aren't. Even a jump table will probably have to compare the
control variable against the range of values, unless you use all the values
allowed by the type (e.g. 256 cases switching on an 8-bit char).

for a performance critical application is it better to to use switch
case or accomplish the same using fn pointers ?

Again, it depends on your implementation and what you're doing. If
you don't have lots of state to pass around, function pointers are
quite natural, but for something like a virtual machine it will often
be faster to use a big switch, or perhaps a non-standard extension (in
particular, the ability to assign labels to a variable).

-- Richard

 

[lallous]

Hello

is the assemly code for if..else and switch statements similar.

Not all the time. Depends on the compiler and the switch values.

I would like to know if switch also uses value comparison for each case
internally or does it
jump to the case directly at the assembly level ?

In most cases, the compiler generates a switch jump table.
Basically comprised of two tables: values table and code offset table.
That is faster than if/else statments.

You will better understand this if you take debug your own sample program
that uses switch statement.

However, if the switch values are not in some sort of sequence the compiler
might generate an ASM code that looks like a serie if/else.

I am referring to code I've seen generated by C compilers on Intel x86
machines.

for a performance critical application is it better to to use switch
case or
accomplish the same using fn pointers ?

Even if you use function pointers, you would have to write a code that maps
a given value to a given index in the function pointers table.
Somehow similar to compiler's generated code.

please advice.

You'ld better ask this question again in comp.lang.asm.x86 or alt.lang.asm

Hope that helps,
Elias

 

[jacob navia]

Hi,

is the assemly code for if..else and switch statements similar. I
would like to know if switch also uses value comparison for each case
internally or does it
jump to the case directly at the assembly level ?

for a performance critical application is it better to to use switch
case or
accomplish the same using fn pointers ?
please advice.

Thanks for your time.
prakash

There is a balance between generating huge jump tables
or generating too many if/else constructs when implementing
a switch statement in assembly code.

In the lcc-win32 compiler this is determined by a "density" parameter,
that starts with a default value of 0.5.

The user can control this parameter using a
#pragma density
construct.

This allows you to force the compiler to generate
jump tables even if the switch case values aren't contiguous. In
a time critical place of the application you can trade space for speed
by forcing the compiler to build a jump table using
#pragma density(0).

If you want to minimize data space usage you can turn all
switch statements into a series of if/else statements by setting
#pragma density(1.0)

References

 

[Thomas Matthews]

Hi,

is the assemly code for if..else and switch statements similar. I
would like to know if switch also uses value comparison for each case
internally or does it
jump to the case directly at the assembly level ?

Depends on the processor and the compiler writer.

Some processors have specialized instructions for jump tables. Some
processors can conditionally execute instructions. Since there is no
uniform assembly language, there is a lot of dependency on the processor
type.

There is also a lot of variance left for the compiler writer. Some
compilers can optimize an if-else-if ladder better than using a jump
table. Some may automatically convert a switch statement into a jump
table. Others may allow leeway through the use of compiler switches.

The best that you can do is to have the compiler(s) that you use print
the suspect code in assembly language. Print it out for every
optimization setting. Choose the compiler switches that generate the
best assembly language.

for a performance critical application is it better to to use switch
case or accomplish the same using fn pointers ?
please advice.

Depends on where the bottleneck is.
Have you profiled the code?

Here are my suggestions:
1. Use switch or an if-else ladder depending on what makes the
program more readable.

2. Worry about correctness before optimizing.

3. Profile the code to find out where the bottlenecks are.
Profile more than once. Many programs operating behavior
depends on other programs that are executing concurrently.

4. Don't second guess the compiler. Print out the assembly language
to find out how the compiler optimized the code. Use this as
a basis for any optimizing.

5. Every situation is different. One part of the code may be
more efficient using if-else ladders. Another code may be
more efficient using switches. The coding guidelines of a
software house may mandate switch statement over if-else
(even over efficieny).

6. If you believe a jump table is more appropriate, you can always
create one using the C language.

7. If your to the point of recoding a module for efficiency,
consider writing that module in assembly.

8. Don't optimize unless absolutely necessary. You are wasting
time and money tweaking the code. There are always risks of
problems popping up every time the code is altered. Even
though the changes you make in your function don't explicitly
change the rest of the program, chances are that some other
function may be effected (such as code or constants being
moved so they aren't aligned anymore).


--
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.comeaucomputing.com/learn/faq/
Other sites:
http://www.josuttis.com -- C++ STL Library book

 

[SM Ryan]

# is the assemly code for if..else and switch statements similar. I
# would like to know if switch also uses value comparison for each case
# internally or does it
# jump to the case directly at the assembly level ?

Implementation dependent. Both can be translated into 'if (predicate) goto label;'
and for all we know that might be exactly what the compiler does so that its code
generator sees no difference.

# for a performance critical application is it better to to use switch
# case or
# accomplish the same using fn pointers ?

In general there's no way to predict whether if or switch will be faster. Nor even
function calls. But for most implementations, function calls which cannot be inlined
and even more so function pointers will be slower. But even in this there can be
exceptions. Usually function calls and pointers impede analysis by optimisers and
break code locality for caches and vm.

 

[kal]

In most cases, the compiler generates a switch jump table.
Basically comprised of two tables: values table and code offset table.
That is faster than if/else statments.

It is not necessarily faster. It could be slower if the
values are few and discontinuous.

 

[Christian Bau]

Hi,

is the assemly code for if..else and switch statements similar. I
would like to know if switch also uses value comparison for each case
internally or does it
jump to the case directly at the assembly level ?

for a performance critical application is it better to to use switch
case or
accomplish the same using fn pointers ?
please advice.

If the application is performance critical, then you should just try
different approaches and measure how long each one takes.

What you want to do is called "micro-optimisation" and will rarely lead
to faster code. If you want fast code, start by writing your code so
that it is as readable as possible and as easy to maintain as possible.
That way you will arrive at working, bug-free code earlier. Only then,
when you have code that actually works, can you find out what is
performance critical - if you try to decide about that before your code
is working, you are only guessing and most likely you will be wrong, and
waste your time by trying to make code faster that doesn't need to be
made faster.

Another hint: How many cycles does a Pentium 4 running at 3000 MHz take
to read a single byte from uncached memory? I recommend you try to find
the answer and then think about it for a while.

 

[Derrick Coetzee]

for a performance critical application is it better to to use switch
case or accomplish the same using fn pointers ?

If you're using a modern optimizing compiler, then it will be very
careful to pick the best way of compiling a switch, in order to maximize
efficiency while not producing an excessively large jump table. Use
switches and depend on the compiler to do the best thing; generally it
is whether you think it is or not. Following are some of the techniques
it uses - if you must optimize, don't try to optimize any switch in your
own code until you've established for sure that it's a bottleneck with
profiling tools.

First of all, whenever the number of cases is small, meaning less than
20 or so, the code produced will almost always mimick that produced by
simple if-else branching, because this is the fastest way. Jump tables
do not benefit speed in such cases because of the time needed to load
from the table, and this includes almost all switch statements written
by hand in typical programs.

In another simple case, where the cases of the switch fill or nearly
fill a large enough contiguous range (like 1 through 50 except 13 and
27), a simple jump table would be generated. The compiler uses a density
heuristic to evaluate how "filled" the range is.

If there are a large number of values, say 200, spread widely across a
very large range, say the entire range of a 32-bit integer, then the
jump table solution is no good. A good solution in this case is to hash
the value being switched on to an index between 0 and 199, jump to the
address at this index in the jump table, and then resolve collisions, if
any, inside the case handler with if-else branching. If the compiler can
generate a perfect hash function, this is even better, as no collision
resolution is necessary. This case doesn't appear much in practice, and
so compilers don't usually deal with it. If you have a switch like this
in your code, you may want to write a preprocessing tool to emit code
which switches on the hash, has contiguous case labels, and does
collision resolution appropriately.

Finally, there's a common scheme that conditionals with jump tables: it
identifies a small number of dense ranges among the cases, decides which
range the value is in using if-else branching, then uses a jump table
within the range. This would be useful if your cases were, for example,
'0' through '9' and 'a' through 'z'. This one isn't always implemented
by compilers. If yours doesn't do it, write a separate switch statement
for each dense range of cases, and choose between them with if-else.
This has the same effect.

 

[Derrick Coetzee]

Some small corrections:

If there are a large number of values, say 200, spread widely [ . . . ]
hash the value being switched on to an index between 0 and 199, [ . . . ]

This is if you're using a perfect hash. If you're using a less perfect
hash, you probably want the jump table size to be about 25-50% bigger
than the number of values (to reduce collisions).

Finally, there's a common scheme that conditionals with jump tables [ . . . ]

Meant: Finally, there's a common scheme that *combines* conditionals
with jump tables

 

[hasadh]

Thanks for your inputs.
I use sequential case values in switch. Compile using gcc in linux.
any compiler options/switches to make switch..case efficient instead
of assembly code similar to if..else


Thanks,
prakash

 

[Bob Jenkins]

Some small corrections:

If there are a large number of values, say 200, spread widely [ . . . ]
hash the value being switched on to an index between 0 and 199, [ . . . ]

This is if you're using a perfect hash. If you're using a less perfect
hash, you probably want the jump table size to be about 25-50% bigger
than the number of values (to reduce collisions).

I've got perfect hash code at
http://burtleburtle.net/bob/hash/perfect.html . Use -md (or -mh for
hex). The hash it generates for {2837, 3727 111, 203, 927, 542, 863,
666, 79, 44, 65, 63, 76, 17, 11, 39, 5, 7, 1, 709, 2978, 278, 57}
produces each value in 0..22 once. The generated code for the hash
function looks like

ub1 tab[] = {15,0,13,13,0,24,31,7,7,18,7,0,31,27,26,1};

ub4 phash(val)
ub4 val;
{
ub4 a, b, rsl;
val += 0x95188cc5;

val += (val << 8);
val ^= (val >> 4);
b = (val >> 3) & 0xf;
a = (val + (val << 12)) >> 28;
rsl = (a^tab);
return rsl;
}