It's dangerous to code alone! Take this.

Switches and Jump Tables

Published on 19 Mar 2022.

Are switches or if statements faster?

Consider this code:

Weather current = Weather.Cloudy;

string toDisplay = current switch
{
    Weather.Sunny => "It's going to be a sunny day!",
    Weather.Cloudy => "Expect some clouds.",
    Weather.Overcast => "It's going to be overcast and dreary today.",
    _ => "Who knows."
};

public enum Weather { Sunny, Cloudy, Overcast }

And compare it against its if-based counterpart:

string toDisplay;
if (current == Weather.Sunny) toDisplay = "It's going to be a sunny day!";
if (current == Weather.Cloudy) toDisplay = "Expect some clouds.";
if (current == Weather.Overcast) toDisplay = "It's going to be overcast and dreary today.";

Does one or the other of these have performance advantage?

Possibly!

To get a true, thorough answer to this question, we need to discuss how the computer runs these types of instructions….

Hardware Jump and Branch Instructions

The model that nearly every hardware CPU supports is one that loads a pile of instructions into memory and then runs them one at a time, in the order they appear. The current instruction is tracked in a special place called the instruction pointer, or the IP. (This is also called the program counter or PC.)

The instruction pointer gets incremented after each instruction automatically, allowing us to move to the next instruction in the sequence.

But simply moving to the next instruction is not enough. Some instructions can change the instruction pointer directly, allowing us to jump around in the pile of available instructions at will. These instructions are sometimes called jump instructions or branch instructions.

For example, when we call a method, we need to set the instruction pointer to wherever that method’s code lives in the pile of instructions.

In other cases, we want to change the instruction pointer, but only if some specific condition is met. Depending on the data and the condition, we may jump or not. Stated differently, these conditional jump instructions create a branch in the pathways we could take. We’re left with two possibilities:

  1. If the condition is true, we jump to another location.
  2. If the condition is false, we increment the instruction pointer like normal.

These conditional jump instructions can be referred to as branch instructions, but the truth is, it seems like the line is pretty blurry. To illustrate, the x86 instruction set has a JMP command that is an unconditional jump and also things like JEQ for “jump if equal”, JNE for “jump if not equal,” etc. Similarly, CIL, the instruction set of the C# virtual machine, has a jmp instruction and a br instruction that both do unconditional jumps. CIL also has beq (“branch if equal”) and bne (“branch if not equal”) instructions. So the terminology is a little vague, and you could generally consider the words jump instruction and branch instruction as synonymous. (However, when people say unconditional jump/branch or conditional jump/branch, those are not ambiguous. Those clearly state whether or not it is based on some condition.)

That’s a lot of low-level stuff, but the bottom line is that virtually everything you do in code, when it comes to control flow, will be turned into these jump instructions. That is true for method calls. It is true for loops. It is true for if statements. It is even true for switch statements and expressions.

As with most things, I’ve greatly oversimplified a lot of the details, but the fundamentals here are sound.

Since everything ultimately compiles to these simple jump instructions (among the instructions that move data around and perform calculations), we’re left in a state where we shouldn’t expect wildly different performance characteristics between an if statement and a switch.

But there’s one caveat…

Jump Tables

With jump instructions, it is possible to allow the target of a jump instruction to be pulled from a non-fixed location. Meaning, we could write code where the destination of a jump is computed from other code and supplied to a jump instruction.

This has many uses, but one of the big ones is a tool called a jump table. You can think of a jump table as an array that contains different potential targets for a jump instruction. We can do some other computation to figure out which index to look up in this jump table, retrieve the target instruction from within it, and then jump to that location. Even if your jump table had 200 slots in it, the procedure is the same, and doesn’t slow down program execution.

When the conditions are right, a switch may be turned into a jump table instead of checking each pathway one at a time. When you have quite a few options, this approach may be substantially faster.

The Conditions for a Jump Table

For a jump table to work, you need to be able to know the index into the jump table. Consider this code:

switch (someNumber)
{
    case 0:
        // Do some stuff.
        break;
    case 1:
        // Do something else.
        break;
    case 2:
        // Do another thing.
        break;
    default:
        // Yet another thing.
        break;
}

This code could easily use a jump table because we can come up with the instructions for each body of the switch statement and just put them into the jump table, one at a time. Evaluating the switch comes down to retrieving the current value in someNumber, looking up the correct target instruction in the jump table, and then jumping to it.

That’s a very direct example. But the compiler is smart and might be able to make a jump table for some slight variations on the idea. For example:

switch (someNumber)
{
    case 0:
        // Do some stuff.
        break;
    case 1:
    case 2:
        // Do another thing.
        break;
    case 4:
        // Do something surprising.
        break;
    default:
        // Yet another thing.
        break;
}

Here, the cases for 1 and 2 share the same body, and 3 is left out. But we can still make a jump table. We’d just have index 1 and 2 use the same address. Meanwhile, index 3 in the jump table can simply jump to the same place as the default path.

So we can bend things a little bit and have it still work, but there’s a point where it bends so much that it breaks:

switch (someNumber)
{
    case 0:
        // Do some stuff.
        break;
    case 100:
        // Do another thing.
        break;
    case 10000:
        // Do weird things.
        break;
    default:
        // Yet another thing.
        break;
}

We could arguably make a jump table that is 10000 items long and have most of them contain the location of the default branch’s first instruction. But that would require a ton of memory on something that needs to be fast. Most compilers, including the C# compiler, will just failover to normal branch instructions instead of a jump table in this situation.

Of course, you could make a hybrid. Consider this code:

switch (someNumber)
{
    case 0:
        // Do some stuff.
        break;
    case 1:
        // Do another thing.
        break;
    case 2:
        // Do something else.
        break;
    case 3:
        // Do crazy things.
        break;
    case 10:
        // Do weird things.
        break;
    case 90:
        // Do an awkward happy dance.
        break;
    default:
        // Yet another thing.
        break;
}

Here, the first several items might be well suited to a jump table. So we could check to see if the number is between 0 and 3, and if so, use a jump table, but otherwise use normal branch instructions. A little of both.

Integers aren’t the only thing that could potentially benefit from a jump table. Enumerations are a fantastic candidate for a jump table. For example:

string toDisplay = weather switch
{
    Weather.Sunny => "It's going to be a sunny day!",
    Weather.Cloudy => "Expect to see some clouds.",
    Weather.Overcast => "It's going to be overcast and gloomy.",
    _ => "Unknown"
};

Since enumerations are integers at heart, the compiler will typically convert this to a jump table.

Alas, if you can’t boil down your data to a set of low-numbered integer values, you probably won’t be able to do a jump table. This code will probably not be able to compile to a jump table:

string toDisplay = Console.ReadLine().ToLower() switch
{
    "sunny" => "It's going to be a sunny day!",
    "cloudy" => "Expect to see some clouds.",
    "overcast" => "It's going to be overcast and gloomy.",
    _ => "Unknown"
};

There isn’t a simple way to map these complex strings to an index for a jump table. The compiler will just use normal branch instructions instead.

The bottom line is that switches can be faster than plain old if statements. But that will only typically happen if they can take advantage of a jump table. You’ll only get that benefit if you’re using an integer type and the numbers are small and packed in close to zero.

(And as a side note, you almost certainly won’t get a jump table if you’re using anything but the constant pattern.)

I’ll wrap this up with a comment I’ve said several times now about performance: Sure, sometimes one option is a bit faster than another. Both if statements and switches are quite fast. 99.99% of the time, you should focus on what makes the code more readable and maintainable, not which one squeezes the most out of the runtime performance.