Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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.
like image 938
ekul Avatar asked Apr 07 '10 22:04

ekul


People also ask

How do switch statements compile?

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

How does compiler optimize code?

Compiler optimization is generally implemented using a sequence of optimizing transformations, algorithms which take a program and transform it to produce a semantically equivalent output program that uses fewer resources or executes faster.

What is optimize code in Visual Studio?

You set the Optimize option from Build properties page for your project in Visual Studio. Optimize also tells the common language runtime to optimize code at run time. By default, optimizations are disabled. Specify Optimize+ to enable optimizations.

Which compiler does Visual Studio use for C?

Microsoft C++ Compiler (MSVC) This is the default compiler for most Visual Studio C++ projects and is recommended if you are targeting Windows.


2 Answers

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

like image 165
UncleBens Avatar answered Oct 07 '22 17:10

UncleBens


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

like image 35
bta Avatar answered Oct 07 '22 16:10

bta