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?

Boat

Explained: https://mcmap.net/q/35670/-is-there-any-significant-difference-between-using-if-else-and-switch-case-in-c – Surpassing

A possible good answer: dotnetperls.com/if-switch-performance – Cataclysm

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.

Deification

They also convert to tree comparisons in some cases. The reasoning is somewhat complex but basically boils down to the table indirection neutering modern cpu jump target buffers and so wipes out the branch predictor. I vaguely recall a paper at a GCC conference on codegen for switches. – Tarr

That means: switch (a) case "x": case "y": case "z": //something break; } is faster than: if(a=="x"||a=="b"||a=="c") //something right? – Kagera

here we have no nested if else, only OR so what do you think? – Kagera

@Kagera On old compilers potentially yes (but note that the number of cases is so small that it might not make a difference!). Modern compilers do a lot more code analysis though. As a consequence, they might figure out that these two code snippets are equivalent, and apply the same optimisations. But this is pure speculation on my part, I don’t know whether any compiler actually does that. – Deification

Answer 2

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.

Tarr

Answer 3

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.

Reliquiae

Answer 4

Switch/case statements may be typically faster 1-level deep, but when you start getting into 2 or more, switch/case statements start taking 2-3 times as long as nested if/else statements.

This article has some speed comparisons highlighting the speed differences when such statements are nested.

For example, according to their tests, sample code like the following:

if (x % 3 == 0)
            if (y % 3 == 0)
                total += 3;
            else if (y % 3 == 1)
                total += 2;
            else if (y % 3 == 2)
                total += 1;
            else
                total += 0;
        else if (x % 3 == 1)
            if (y % 3 == 0)
                total += 3;
            else if (y % 3 == 1)
                total += 2;
            else if (y % 3 == 2)
                total += 1;
            else
                total += 0;
        else if (x % 3 == 2)
            if (y % 3 == 0)
                total += 3;
            else if (y % 3 == 1)
                total += 2;
            else if (y % 3 == 2)
                total += 1;
            else
                total += 0;
        else
            if (y % 3 == 0)
                total += 3;
            else if (y % 3 == 1)
                total += 2;
            else if (y % 3 == 2)
                total += 1;
            else
                total += 0;

finished in half the time the equivalent switch/case statement took to run:

switch (x % 3)
    {
        case 0:
            switch (y % 3)
            {
                case 0: total += 3;
                    break;
                case 1: total += 2;
                    break;
                case 2: total += 1;
                    break;
                default: total += 0;
                    break;
            }
            break;
        case 1:
            switch (y % 3)
            {
                case 0: total += 3;
                    break;
                case 1: total += 2;
                    break;
                case 2: total += 1;
                    break;
                default: total += 0;
                    break;
            }
            break;
    case 2:
            switch (y % 3)
            {
                case 0: total += 3;
                    break;
                case 1: total += 2;
                    break;
                case 2: total += 1;
                    break;
                default: total += 0;
                    break;
            }
            break;
    default:
        switch (y % 3)
        {
            case 0: total += 3;
                break;
            case 1: total += 2;
                break;
            case 2: total += 1;
                break;
            default: total += 0;
                break;
        }
        break;
    }

Yeah it's a rudimentary example, but it illustrates the point.

So a conclusion might be use switch/case for simple types that are only one level deep, but for more complex comparisons and multiple nested levels use the classic if/else constructs?

Africa

-1: 1. The article completely ignored Branch Prediction, 2. the algorithms aren't exactly the same (the single if-else one on the link is already coded more optimized) and 3. the differences found are so small that nothing excuses the use of proper, clean code (about 4 ns in 10.000.000 calls between switch and same if-else construct) – Personate

That example won't be optimized because of how few cases the switch block has. Typically after 5-6 elements it'll generate a jump table. – Golconda

The value of x doesn't even matter in that input, so an entire level of the conditionals can be removed. If the compiler didn't, it probably means the blog author ran his timing tests with optimizations turned off. – Strickland

Answer 5

The only advantage of the if over case is when there is a noticeable increase of occurrence frequency of the first case.

Not sure exactly where the threshold is, but I use case syntax unless the first "almost always" passes the first test.

Curse

Answer 6

Arithmetic can replace efficiently if and case :

if (x % 3 == 0)
        if (y % 3 == 0)
            total += 3;
        else if (y % 3 == 1)
            total += 2;
        else if (y % 3 == 2)
            total += 1;
        else
            total += 0;
    else if (x % 3 == 1)
        if (y % 3 == 0)
            total += 3;
        else if (y % 3 == 1)
            total += 2;
        else if (y % 3 == 2)
            total += 1;
        ...

can be replaced by a single faster line

total += 3 - y%3;

Calondra