How does switch compile in Visual C++ and how optimized and fast is it?

Question

As I found out that I can use only numerical values in C++'s switch statements, I thought that there then must be some deeper difference between it and a bunch of if-else's.

Therefore I asked myself:

• (How) does switch differ from if-elseif-elseif in terms of runtime speed, compile time optimization and general compilation? I'm mainly speaking of MSVC here.

Solution 1

A switch is often compiled to a jump-table (one comparison to find out which code to run), or if that is not possible, the compiler may still reorder the comparisons, so as to perform a binary search among the values (log N comparisons). An if-else chain is a linear search (although, I suppose, if all the relevant values are compile-time integral constants, the compiler could in principle perform similar optimizations).

Solution 2

Switch statements are often a common source of compiler optimization. That is, how they are treated depends on the optimization settings you use on your compiler.

The most basic (un-optimized) way of compiling a switch statement is to treat it as a chain of if ... else if ... statements. The common way that compilers optimize a switch is to convert it to a jump table which can look something like:

if (condition1) goto label1;
if (condition2) goto label2;
if (condition3) goto label3;
else            goto default;
label1:
  <<<code from first `case statement`>>>
  goto end;
label2:
  <<<code from first `case statement`>>>
  goto end;
label3:
  <<<code from first `case statement`>>>
  goto end;
default:
  <<<code from `default` case>>>
  goto end;
end:

One reason this method is faster is because the code inside the conditionals is smaller (so there's a smaller instruction cache penalty if the conditional is mis-predicted). Also, the "fall-through" case becomes more trivial to implement (the compiler leaves off the goto end statement).

Compilers can further optimize the jump table by creating an array of pointers (to the locations marked by the labels) and use the value you are switching on as an index into that array. This would eliminate nearly all of the conditionals from the code (except for whatever was needed to validate whether the value you are switching on matches one of your cases or not).

A word of caution: nested jump tables are difficult to generate and some compilers refuse to even try to create one. For that reason, avoid nesting a switch inside another switch if maximally-optimized code is important to you (I'm not 100% sure how MSVC in particular handles nested switches, but the compiler manual should tell you).

Comments

[Amardeep AC9MF]

+1 for good answer. I'm also going to use this opportunity to disparage the if-then-elseif chain. More than one 'else if' is a marker for DDD (Design Deficit Disorder).

[bta]

One note: I failed to mention any specific numbers regarding switch performance relative to an if-else tree because the benefits of optimization are heavily dependent on the code. The only real way to tell how much improvement you are getting from optimizations is to write the code both ways and measure how long it takes to run each.

[dualed]

The given code is not a jump table. It does not represent any table at all for that matter. The link to Wikipedia does however provide correct examples.

[David Andreoletti]

Here is a real world C++ switch implementation for VisualC++.

[Lothar]

It would be nice to now if this is optimized not if they could.

[Opux]

If the cases are/can be sorted, is a jump table not just as good as a binary search?

[Flamefire]

@Opux The jump table is faster: One lookup vs log n comparisons. However you need to access memory which might make it slower in running time