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?

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

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

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

Solution 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?

View more solutions

Comments

[Matthew M. Osborn]

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

[Paul Marcelin Bejan]

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

[olliej]

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.

[yazanpro]

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

[yazanpro]

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

[Konrad Rudolph]

@yazanpro 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.

[Enes Sadık Özbek]

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

[antiduh]

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.