9
\$\begingroup\$

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)

\$\endgroup\$
  • 11
    \$\begingroup\$ what makes you think that a switch would be less performant than an if-else-chain? Both do essentially the same thing: Check conditions until you find one that matches. \$\endgroup\$ – Tim Pohlmann Jun 19 at 9:22
  • \$\begingroup\$ note that this is more like 400 cases anyway \$\endgroup\$ – somebody Jun 19 at 13:30
  • 2
    \$\begingroup\$ For what it's worth, even the developer admits that the code of that game is a bit of a mess. You probably shouldn't try to learn about code quality from it, but perhaps you could use it to convince yourself that your code does not have to be perfect in order to make a fun and successful game. \$\endgroup\$ – Matti Virkkunen Jun 19 at 15:23
  • 6
    \$\begingroup\$ Why is this on gamedev? This has nothing to do with game development and should be a StackOverflow question, and even then it is poorly researched since a simple google: "switch statement performance c++" would have been enough to answer that switch statement being evaluated 60 times each second hardly has any performance impact at all. Casting my vote to close for this reason. \$\endgroup\$ – Charanor Jun 19 at 17:10
  • 4
    \$\begingroup\$ @Charanor It's fine that you vote to close. If it only had been about switch vs if/else, sure, yes, close-and-ask-on-SO, but I answered because "Are switch statements normally used in this manner to implement state handling," My interpretation is really about "game state" handling, which would make it, I believe, on-topic. \$\endgroup\$ – Vaillancourt Jun 22 at 1:43
26
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I'm still a beginner in both programming and game dev, so I'm not very familiar with these concepts. I was under the impression that 3000+ comparison checks would cause at least some slowdown \$\endgroup\$ – Carmo Jun 19 at 1:05
  • \$\begingroup\$ @Carmo The gist of it, really, is if the code works and is clear, leave it as is until you profile it and realize that it needs improvement :) \$\endgroup\$ – Vaillancourt Jun 19 at 1:25
  • 7
    \$\begingroup\$ @Carmo this is part of the point of it. You shouldn't just assume something will be slow and make decisions based on that assumption. You should instead benchmark and profile, and make decisions based on real data and real results. Also, 300 or even 3000 conditions per frame is nothing compared to the amount of work the rest of the code will be doing. You need to look at the whole thing, not parts of it in isolation. \$\endgroup\$ – Maximus Minimus Jun 19 at 4:21
  • 4
    \$\begingroup\$ @Carmo I've got a toy software 3D renderer. Things that happen once-per-frame are almost irrelevant to the performance - you need to do something seriously screwed up to impact performance. I even did texture baking every frame in an earlier version, and adding caching only resulted in some 3% FPS increase. But a single extra memory access or unnecessary instruction in the per-pixel code would easily cause a 50% drop in FPS. That's why software 3D renderers (and in the past, even hardware) try to move as much as they can to per-frame. Frames are short in human-time, but not CPU-time. \$\endgroup\$ – Luaan Jun 19 at 9:15
  • 3
    \$\begingroup\$ Related: Advantage of switch over if-else statement \$\endgroup\$ – Bernhard Barker Jun 19 at 10:16
25
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
8
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Yep, quite bad, coming up with a decent example is a bit hard, and not the focus of the answer, and as such I have remove the highlight over this part of my answer. \$\endgroup\$ – Vaillancourt Jun 21 at 1:51
3
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ I suspect he wrote it that way because like everything else, it started small then grew big, then it worked and he didn't want to fix something that didn't need to be fixed. Who knows! \$\endgroup\$ – Vaillancourt Jun 19 at 1:33
  • \$\begingroup\$ @Vaillancourt yes. note that it is not an issue. it may be long, but using if/else is more unnecessary boilerplate, extracting each case to a function is even more boilerplate than that \$\endgroup\$ – somebody Jun 19 at 13:35
  • \$\begingroup\$ Switch statements don't get compiled to binary trees, they get compiled to jump tables, and have done so for at least as long as there have been compilers. (A binary tree search is O(log n), while a jump table is O(1).) \$\endgroup\$ – Mark Jun 19 at 20:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.