Switch statement efficiency in game code

Question

Recently, I was digging into VVVVVVV's source code that was released on GitHub by Terry Cavanagh. I went into the Game.cpp file, and found that it contains an absolutely gigantic, 3000+ case long switch statement in what is seemingly a function that is called consistently, not just once.

This made me ponder about how efficient switch statements are, and I realized I don't know much about their difference to normal if-else chains. Are switch statements normally used in this manner to implement state handling, and why doesn't something like this lag the game like crazy? (I'm assuming a massive amount of comparisons are being made every time)

Answer 1

In this situation, it is trivial and a no-brainer.

I'll be bold and not look at the whole code. I'll assume that the function in which this switch statement is (Game::updatestate()) is called once per frame.

This switch statement being called once per frame is a droplet in the ocean. Typically, graphics rendering, physics and AI take up much more CPU time than this type of decision making, whether it is a switch or a series of if-else-if.

From the couple of videos I've seen on youtube, the game runs smoothly, without lag.

I assume Terry Cavanagh, like any good dev, profiled the game at some point and fixed/improved/optimized some parts of it based on the profiler results; it's safe to assume that the issue was not that part.

That's the key part here. The syntax of the switch is clean and clear with the minimum of overhead code, going another way would clutter more the code without real technical benefit.

---

To be honest, I would personally be more worried about the use of raw integers instead of constant in the case parts, as this makes the code much harder to read. (I'll give the author the benefit of the doubt, as coming up with 300+ GOOD constant names could be a challenge. He used comments in an OK manner, in this case, and using constants like this removes the need to link all the files that share the constant names together.)

---

To answer your questions directly:

Are switch statements normally used in this manner to implement state handling

There are many games around, and many ways to do this, but yes, using a switch to handle a state (or multiple states) is a perfectly acceptable way of doing this.

and why doesn't something like this lag the game like crazy?

As it's been pointed out, this switch is called 30, 60, 90 times per seconds, it's trivial for a CPU to handle.

---

Finally, if you're curious to go and see the "under the hood" effects of the code you write, there is an online tool called Compiler explorer that lets you write some chunks of c++ code and see how it is compiled to assembler by the different compilers out there.

Although you can come up with trivial tests for this tool, you'll never know the full effects of actual real code compiled with optimization flags (because you ship your game with optimizations turned on). Compilers are very smart to not do some work.

As a simple, trivial, non-optimized test, I've written two similar chunks, one using if-else (Link), and one using a switch (Link). You can take a look and see for yourself the different output, and even toy around and add the optimization to see the effects (and see why using simple-trivial test code is often useless for testing real world situations).

Answer 2

In fact, switch statements are more efficient than if-else chains for one simple reason: Switch tables! (Also known as branch tables or jump tables).

The simple explanation is that in a typical switch statement, each case ends in a break statement, so the compiler can figure out that exactly one path is going to be taken upon entering the switch. So then each case entry just becomes an entry in a table. Your switch statement becomes:

1. Look up table entry
2. Jump to the appropriate block

This is versus a naive if-else chain, where each if clause needs to be evaluated one at a time. So if you're looking for case 200, you need to evaluate 199 false. Much slower than a lookup.

However, modern compilers are really smart. What you'll probably see if you run with optimizations is that something like this:

if (x == 1) {
  ...
} else if (x == 2) {
  ...
} else if (x == 3) {
  ...
}
...

can be turned into:

switch(x) {
  case 1:
    ...
    break;
  case 2:
    ...
    break;
  case 3:
    ...
    break;
  ...
}

So a good compiler will take advantage of switch tables either way, and you probably won't notice any difference between the two.

Answer 3

There is a surprising amount of confusion about how the compiler optimizes if/else chains vs switch statements. This is probably because there have been many changes over time in how compilers optimize these constructs. And even using the latest compiler versions, the answer depends on:

• what optimization level you are using,
• what values you are checking for,
• the number of values you are checking for,
• what code is being executed inside each case.

Note that if a chain of if/else statements is semantically identical to a switch statement, the compiler is free to optimize the if/else chain in the same way as the switch statement. Nothing prevents the compiler from using a jump table in either case.

In an earlier version of Vaillancourt's answer, examples on the Compiler Explorer were given for the if/else chain and the switch statement. These examples are not representative of real game code, since they did not use any optimization flags, and because every case executes exactly the same statement. The examples do match one aspect though: in VVVVVV's switch statement, there are gaps in the case values tested for.

When a game is released, it is typically compiled with a high optimization level. When adding -Ofast to the compiler flags in the examples, and looking at the resulting assembly, the results are quite interesting, showing both that compilers can use jump tables for if/else chains, and that there is a huge variation in how compilers optimize code:

• if/else statement:
  • GCC 10.1 -Ofast: linear sequence of compare and jump instructions
  • Clang 10.0.0 -Ofast: jump table
• switch statement:
  • GCC 10.1 -Ofast: jump table
  • Clang 10.0.0 -Ofast: replaces the whole function with return state * state;

And it's not even clear which of those results is fastest. The branch predictor might hide a lot of the latency with the linear sequence of jump instructions, so if it hits one of the early cases most of the time, it might even win.

Answer 4

Because switch statements work on only a single variable they can be optimized very easily compared to an if-else statement. The most naïve way to do so would be to determine the case using a binary tree.

Of course, I doubt this is the reason for using switch in VVVVVVV. The amount of time saved is unlikely to be meaningful especially with branch prediction.