If vs. Switch Speed

Question

Switch statements are typically faster than equivalent if-else-if statements (as e.g. descibed in this article) due to compiler optimizations.

How does this optimization actually work? Does anyone have a good explanation?

Answer 1

The compiler can build jump tables where applicable. For example, when you use the reflector to look at the code produced, you will see that for huge switches on strings, the compiler will actually generate code that uses a hash table to dispatch these. The hash table uses the strings as keys and delegates to the case codes as values.

This has asymptotic better runtime than lots of chained if tests and is actually faster even for relatively few strings.

Answer 2

Konrad is correct. In the case of switching on contiguous ranges of integers (eg, where you have case 0, case 1, case 2 .. case n), the compiler can do something even better because it doesn't even need to build a hash table; it simply stores an an array of function pointers, and thus can load its jump target in constant time.

Answer 3

As Konrad said the compiler can build a Jump table.

In C++ a reason it can is because of the limitation of switches.

• The comparison term must be converted to an int.
• The case labl must be a constant.

Answer 4

The no-match stats may not be good.

If you actually download the source, the no match values are known to be 21, in both the if and switch case. A compiler should be able to abstract away, knowing which statement should be run at all times, and a CPU should be able to branch predict properly.

The more interesting case is when not every case breaks, in my opinion, but that may not have been the scope of the experiment.

Answer 5

This is a slight simplification as typically any modern compiler that encounters a if..else if .. sequence that could trivially be converted into a switch statement by a person, the compiler will as well. But just to add extra fun the compiler is not restricted by syntax so can generate "switch" like statements internally that have a mix of ranges, single targets, etc -- and they can (and do) do this for both switch and if..else statements.

Anyhoo, an extension to Konrad's answer is that the compiler may generate a jump table, but that's not necessarily guaranteed (nor desirable). For a variety of reasons jump tables do bad things to the branch predictors on modern processors, and the tables themselves do bad things to cache behaviour, eg.

switch(a) { case 0: ...; break; case 1: ...; break; }

If a compiler actually generated a jump table for this it would likely be slower that the alternative if..else if.. style code because of the jump table defeating branch prediction.

Answer 6

Explained: http://stackoverflow.com/questions/395618/if-else-vs-switch