How does the switch statement execute?

Question

I am stepping through two different blocks of code to learn the difference in execution between the switch and if statements.

While if seems to check every single condition, switch skips directly to the condition that evaluates to true. How does the compiler know which statement will evaluate to true pre-check? Please see below code:

public void IFvSwitch()
    {
        string x = "f";
        switch (x)  // Compiler skips directly to case "f":
        {
            case "a":
                MessageBox.Show(x);
                break;
            case "b":
                MessageBox.Show(x);
                break;
            case "f":
                MessageBox.Show(x);
                break;
        }

        if (x == "a") // Compiler checks all conditions 
        {
            MessageBox.Show(x);
        }
        else if (x == "b")
        {
            MessageBox.Show(x);
        }
        else if (x == "f")
        {
            MessageBox.Show(x);
        }
    }

Answer 1

While if seems to check every single condition, switch seems to skip directly to the condition that evaluates to true. How does the compiler know which statement will evaluate to true before pre-check?

Let's start by correcting your use of jargon. The C# compiler translates C# into IL. The runtime has a jit compiler that translates IL into machine code. The C# compiler also generates information that informs the debugger where it should be causing breaks when you are single-stepping.

So it's not exactly clear what your question is. Is the question "how does the C# compiler generate IL to avoid linear search?" or is it "how does the C# compiler inform the debugger that it should skip showing the search portion of the switch codegen?" Or is it "how does the jit compiler generate machine code for a switch?"

Tell you what, I'll handwave a little here and give you vague answers that describe the strategy but not the details. If you have questions about the details then post a more specific question. In particular, I'll use "the compiler" to mean either the C# compiler or the jit compiler, without saying which. Sometimes work is done by the C# compiler, sometimes it defers that work to the jitter, but either way, the work gets done.

---

Switch codegen is complicated. Let's start with the easy one. The compiler can choose to compile a switch as though it was a bunch of if-else statements, and in practice it often does. It particularly does so if the switch is very small, as in your example.

How does the debugger know to not show you the comparison steps that are really happening? The compiler also generates debugging information that informs the debugger what instructions should be skipped over and which ones should generate automatic breakpoints when single-stepping. So the C# compiler, the jit compiler and the debugger all work together to ensure that the developer has the right experience when stepping on a switch.

---

What happens if the switch is big? Doing a huge if-else to find the right switch section is potentially slow. Let's again do an easy case and look at a big switch full of strings. In that case the compiler will do the following:

• Figure out the address of each switch section
• Generate code which builds a static dictionary from string to int
• The switch becomes "look up the string in the dictionary; if it is not there, go to the default case or the end of the switch if there is no default. If it is there, go to the address that is in the dictionary"

Now the work of quickly finding the string without checking every one of them is left up to the dictionary, which uses a hash table to cut down on the number of string comparisons by a huge factor.

---

What if we have a large switch but the cases are integers?

switch(whatever)
{  
  case 1000: … break;
  case 1001: … break;
  … many more …
  case 1999: … break;
  default: … break;
}

In this situation the compiler could make a static array of a thousand switch case addresses, and then generate code like this:

• If the value is less than 1000 or more than 1999, go to the default case
• Otherwise, look up the address by dereferencing the array, and go there.

So now we are down to two comparisons and an array dereference; this really does jump directly to the right section.

---

What about this?

switch(whatever)
{  
  case 1000: … break;
  case 1001: … break;
  … many more …
  case 1999: … break;
  case 2001: … break;
  default: … break;
}

There's no case 2000. In that case the compiler can generate a jump table as before, with 2002 entries, and in the 2000 slot, it just puts the address of the default section.

What about this?

switch(whatever)
{  
  case 1000: … break;
  case 1001: … break;
  … many more …
  case 1999: … break;
  case 1000001: … break;
  default: … break;
}

Now we are in an interesting case! The compiler will not generate a jump table with 1000002 entries, most of which are "go to the default case". In this case the compiler could generate a hybrid switch:

• If the value is less than 1000 go to the default case
• If the value is 1000001, go to its case
• If the value is greater than 1999 go to the default case
• Otherwise, check the jump table

---

And so on. I'm sure you can see how this can get very complicated when the switches are large and there are many dense ranges of values.

There has been a lot of work in the optimization community on what precisely is the best balance for creating hybrid switch strategies.

There is also lots of opportunity for things to go wrong. I'll end with a war story from the 1990s. The MSVC compiler back then -- I think it was version 4 -- had a bug where in my particular program, the hybrid jump table was generated incorrectly. Basically, it broke up a bunch of contiguous ranges into individual jump tables when it didn't need to.

Normally that would not be a problem, but this particular switch was the innermost loop of the logic in the Microsoft VBScript and JScript engines that dispatched the next instruction in the script. (VBScript and JScript at the time compiled to a proprietary bytecode language.) The bad switch was killing performance of the script engines.

The MSVC team could not prioritize fixing the bug fast enough for us, so we ended up writing heroic macro code that would let us express the switch statement in a way that looked reasonable to read, but behind the scenes the macros would generate the appropriate jump table!

Fortunately you can rely on the C# compiler and the jitter to generate good code for you. You shouldn't have to worry about what code is generated for a switch.

Answer 2

Disclaimer
As others have commented, the underlying compiled IL is different from how you see your breakpoint move. Under the hood, it is actually checking each value one after the other.
However, your breakpoint doesn't show that.

Reading your question, I think the most important thing to notice here is that you're assuming your if else if else if structure to be one block; which it isn't. My answer focuses on this incorrect expectation from a logical perspective, rather than digging into the IL.

You're missing an important clue here:

    if (x == "a") // Compiler checks all conditions 
    {
        MessageBox.Show(x);
    }
    else if (x == "b")
    {
        MessageBox.Show(x);
    }
    else if (x == "f")
    {
        MessageBox.Show(x);
    }

These are all separate if statements, which are stacked one after the other (in each other's else case). They are executed separately because they are separate steps!

Your example has very similar if evaluations, but you could've done wildly different things here:

    if (x == "a") // Compiler checks all conditions 
    {
        MessageBox.Show(x);
    }
    else if (IsElvisStillAlive())
    {
        MessageBox.Show(x);
    }
    else if (sonny + cher == love)
    {
        MessageBox.Show(x);
    }

One evaluation says nothing about the next evaluation. They are not connected in any way.

---

Note that the indentation (and omitting curly braces) can help showcasing that point. Your indentation hides the fact that these are nested steps.

    if (x == "a") // Compiler checks all conditions 
    {
        MessageBox.Show(x);
    }
    else 
    {
        if (x == "b")
        {
            MessageBox.Show(x);
        }
        else 
        {
            if (x == "f")
            {
                MessageBox.Show(x);
            }
        }
    }

This revised indentation, while needlessly verbose (although some like it that way), is much clearer on explaining why these are separate steps.

---

Notice how you're not asking how an if knows how to go to the first or second case. That's fairly obvious.
A switch is, effectively, an if with more than two outcomes.

---

Think of it this way: A switch only needs to take one step:

                **********
                * SWITCH *
                **********
     _________ _/ |    |  \ _________      
    /             |    |             \  
********    ********  ********    ********
* CASE *    * CASE *  * CASE *    * CASE *
********    ********  ********    ******** 

But your if falls through 3 separate if cases:

        ******                             
        * IF *                             
        ******  
    ______|______
    |            |
********    ********  
* THEN *    * ELSE *  
********    ********    
                 |
               ******                      
               * IF *                      
               ******  
           ______|______
           |           |
       ********    ********  
       * THEN *    * ELSE *  
       ********    ********      
                      |
                   ******                  
                   * IF *                  
                   ******  
               ______|______
              |             |
           ********    ********  
           * THEN *    * ELSE *  
           ********    ********  

You're right that they syntactically look very similar, but they are very different when you observe their logical flow.

Answer 3

In linqpad 4 I compiled the following method to look at the underlying IL:

void sw()
{
        string x = "f";
        switch (x)  // Compile skips directly to  case "f":
        {
            case "a":
                Console.WriteLine(x);
                break;
            case "b":
                Console.WriteLine(x);
                break;
            case "f":
                Console.WriteLine(x);
                break;
        }
}

The IL generated was as follows:

IL_0000:  nop         
IL_0001:  ldstr       "f"
IL_0006:  stloc.0     // x
IL_0007:  ldloc.0     // x
IL_0008:  stloc.1     // CS$4$0000
IL_0009:  ldloc.1     // CS$4$0000
IL_000A:  brfalse.s   IL_0050
IL_000C:  ldloc.1     // CS$4$0000
IL_000D:  ldstr       "a"
IL_0012:  call        System.String.op_Equality
IL_0017:  brtrue.s    IL_0035
IL_0019:  ldloc.1     // CS$4$0000
IL_001A:  ldstr       "b"
IL_001F:  call        System.String.op_Equality
IL_0024:  brtrue.s    IL_003E
IL_0026:  ldloc.1     // CS$4$0000
IL_0027:  ldstr       "f"
IL_002C:  call        System.String.op_Equality
IL_0031:  brtrue.s    IL_0047
IL_0033:  br.s        IL_0050
IL_0035:  ldloc.0     // x
IL_0036:  call        System.Console.WriteLine
IL_003B:  nop         
IL_003C:  br.s        IL_0050
IL_003E:  ldloc.0     // x
IL_003F:  call        System.Console.WriteLine
IL_0044:  nop         
IL_0045:  br.s        IL_0050
IL_0047:  ldloc.0     // x
IL_0048:  call        System.Console.WriteLine
IL_004D:  nop         
IL_004E:  br.s        IL_0050
IL_0050:  ret         

Broadly the bit you are interested in starts at IL_000C where it loads up the switch variable, then loads the static value "a" (IL_000D), compares them (IL_0012) and then if true jumps to IL_0035 (IL_0017). It then repeats this for each case statement. After the last case statement it jumps to the end (skipping past all the code that was in each case) (IL_0033).

So your observation that "'Switch' seems to skip directly to the condition that evaluates to true" isn't actually true. When stepping through a debugger it may seem like this but this is not representing how the underlying compiled code works.

I should note that this is now always how the switch statement will be compiled, just that this is how this particular one is getting compiled.

If you increase the number of case statements then it will implement it using a jump table in this case it creates a private dictionary with your case strings as the key and then an index as the value. It then looks up the switch variable in that dictionary and uses that in a jump table to work out where in the IL to move execution to. So in this case it would be able to go directly to the right branch in the same way that when looking up a value in a dictionary it doesn't need to check every single name/value pair.

Is there any significant difference between using if/else and switch-case in C#? (thanks to @Sudsy1002 for linking it) discusses some of these things in more detail.

Answer 4

TL;DR: Logically, each case in the switch statement is checked in turn, and the first one to match "wins". As an implementation detail, the compiler is very often able to optimize this.

When every "case" is a constant, the compiler may well be able to generate a jump table to optimize things. That will always logically give the same result as checking each case in turn. How it creates that table may well depend on the switch type - switching over integers is simpler than switching over strings, for example.

When cases contain patterns as introduced in C# 7, the compiler may not be able to create a jump table. Here's an example to prove that multiple case labels can be checked in a single switch statement:

using System;

class Program
{
    public static void Main()
    {
        object obj = 200;
        switch (obj)
        {
            case int x when Log("First when", x < 10):
                Console.WriteLine("First case");
                break;
            case string y when Log("Second when", y == "This won't happen"):
                Console.WriteLine("Second case");
                break;
            case int z when Log("Third when", true):
                Console.WriteLine("Third case");
                break;                
        }
    }

    static bool Log(string message, bool result)
    {
        Console.WriteLine(message);
        return result;
    }
}

The output is:

First when
Third when
Third case

The "Second when" message isn't logged because the start of the pattern isn't matched: we don't get as far as the guard clause (the when). But execution may still have had to check that. It's possible that the implementation would effectively switch on the type, and know that if obj is an int, it only needs to check the first and third patterns.

Basically, as of C# 7, the compiler has a lot of latitude to optimize - and is very, very likely to do that when all the case labels are constants - but logically it needs to check one case at a time.

Answer 5

I remember someone saying that a switch with string cases internally gets converted to an if-else structure. Basically saying that it's just syntactic sugar.

switch statements with ints/enums might actually work differently (and thus faster than if/else)