switch or if?

  • Thread starter Thread starter Dennis Myrén
  • Start date Start date
D

Dennis Myrén

Hi.
I have to ask this question once for all;
Is there a good rule for when to use a switch statement rather than an if
statement?
I know if statements is faster in small tests,
but how many if-elseif's are considered a maximum before it is recommended
to use a switch statement?

Thank you.
 
Dennis,

Well, the IL produced for the two is different. If you have the
following code:

bool b;

if (b)
i = 1;
else
i = 0;

i = (b ? 1 : 0);

The switch statement generates one extra line of IL compared to the if
statement. Whether or not this causes a performance impact, I wouldn't be
able to say (without seeing the native code produced). It could be that the
JIT compiler will optimize out the extra IL step, seeing it as unecessary.

Hope this helps.
 
Dennis Myrén said:
I have to ask this question once for all;
Is there a good rule for when to use a switch statement rather than an if
statement?
I know if statements is faster in small tests,
but how many if-elseif's are considered a maximum before it is recommended
to use a switch statement?
Click to expand...

After seeing your question, I became curious myself, so I did some tests.

I tested two scenarios, dense switches, and sparse switches. With dense
switches, we are selecting from some set of values without skipping any
values in the middle. With sparse switches, we are selecting from values
that may skip around a lot.

In all cases, the machine code generated for switch() will out-perform that
generated for if().

The machine code generated for if() ... else if() ... is a pretty faithful
translation of the source code. There are machine jump instructions for
every value tested against, and they even appear in the same order as your
source code. There are O(n) jump instructions, and it isn't affected by
whether we're doing dense or sparse tests.

The machine code generated for switch() depends on whether we do a dense or
sparse test.

The dense switch() is extremely efficient, doing pointer arithmetic to
compute the destination address of it's *single* jump instruction. This
optimization is probably only possible thanks to the special IL instruction
"switch", which the C# compiler outputs in this situation. Here, we have
O(1) jump instructions.

The sparse switch() is also very efficient, it does a series of comparisons
paired with conditional jump instructions, and only jumps one time, to the
desired case. Here, we also have O(1) jump instructions (that are actually
executed).

In addition to this, the sparse switch does all comparisons and conditional
jumps in one big stretch of machine code, which is really good for CPU
caches. The machine code for if() jumps all over the place to arrive at its
destination, so if you do a lot of work in each if(), there will be a bunch
of stuff to jump over - and therefore the locality of reference goes way
down. That translates to CPU cache misses, which are performance killers.

Another thing to consider with the dense switch() is that IL is expressive
enough to capture the compiler's intent in this situation, so the JIT for
other potential platforms may be able to optimize it even better (though
they'll have a hard time beating O(1)).

Conclusion: switch always out-performs if. That said, when there are a
small number of tests, you may choose if() just for readability if it makes
sense in a particular situation.

I only tested switch on integer types.. not strings. I suspect that
switch() would still outperform if() in this case due to locality of
reference.

Mike
 
Hi Michael
Since you did this test on switch, i though of asking u one question on the same. i read this in one article that better not use switch (C++) if ur case statements exceeds the limit 50 as it wud affect ur application's performance. Can u put some light on this... Bcoz in one of my program, i have used almost 90/100 case statements but that was the need to make it more generic. Any other way to do it. Thanx in advance.
 
I only tested switch on integer types.. not strings. I suspect that
switch() would still outperform if() in this case due to locality of
reference.
Click to expand...

Mike, I saw a post a couple months ago that indicated that switches on
strings use hash tables when there are around 12 or more cases (I
forget the exact number). So that should be much faster than the
equivalent 'if' tests.
 
Thank you for very good answer.


Michael Sparks said:
After seeing your question, I became curious myself, so I did some tests.

I tested two scenarios, dense switches, and sparse switches. With dense
switches, we are selecting from some set of values without skipping any
values in the middle. With sparse switches, we are selecting from values
that may skip around a lot.

In all cases, the machine code generated for switch() will out-perform that
generated for if().

The machine code generated for if() ... else if() ... is a pretty faithful
translation of the source code. There are machine jump instructions for
every value tested against, and they even appear in the same order as your
source code. There are O(n) jump instructions, and it isn't affected by
whether we're doing dense or sparse tests.

The machine code generated for switch() depends on whether we do a dense or
sparse test.

The dense switch() is extremely efficient, doing pointer arithmetic to
compute the destination address of it's *single* jump instruction. This
optimization is probably only possible thanks to the special IL instruction
"switch", which the C# compiler outputs in this situation. Here, we have
O(1) jump instructions.

The sparse switch() is also very efficient, it does a series of comparisons
paired with conditional jump instructions, and only jumps one time, to the
desired case. Here, we also have O(1) jump instructions (that are actually
executed).

In addition to this, the sparse switch does all comparisons and conditional
jumps in one big stretch of machine code, which is really good for CPU
caches. The machine code for if() jumps all over the place to arrive at its
destination, so if you do a lot of work in each if(), there will be a bunch
of stuff to jump over - and therefore the locality of reference goes way
down. That translates to CPU cache misses, which are performance killers.

Another thing to consider with the dense switch() is that IL is expressive
enough to capture the compiler's intent in this situation, so the JIT for
other potential platforms may be able to optimize it even better (though
they'll have a hard time beating O(1)).

Conclusion: switch always out-performs if. That said, when there are a
small number of tests, you may choose if() just for readability if it makes
sense in a particular situation.

I only tested switch on integer types.. not strings. I suspect that
switch() would still outperform if() in this case due to locality of
reference.

Mike
Click to expand...
 
Now I have no idea about the VC++ / C# compiler, but the C compilers I've
seen use a combination of binary trees and jump statements. So if you have a
set of mostly contiguous values, you get a jump table; if you have sparse
values, you get a binary tree, and if you have clumps of contiguous values
you get a binary tree with jump tables at the leaves.
 
Back
Top