Jump to content
  • Advertisement
Sign in to follow this  
DrEvil

Switch statement instructions

This topic is 4888 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Can someone explain how switch statements work at an instruction level? I believe I've heard them referred to as a jump table as well, but does the code that is generated essentially have to do if checks until it finds a matching case? I also believe that I read somewhere that due to how switch statements work, in certain cases an if/else would perform better, particularly if you order the if/else by the cases that will turn up most frequently, is this true?

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
A modern compiler is pretty clever. Until you've found a bottleneck there's no need try these kind of optimizations, spend your time on bottlenecks you've actually seen in a profiler.

If you're switching on a byte value, e.g.

switch ( myByte )
{
case 0: ...
case 1: ...
...
case 255: ...
}

Most compilers can easily generate a jump table. If you switch on a 32-bit value with sparse values (1, 5003, 31355454) it wouldn't be practical with a jump table (as it would need more RAM than you probably have in your system).

If you for instance are using Visual C++, your best bet is to build a release build, put a break point on your switch statement and run til you get there. Then right-click on the row and select "Go to disassembly". That way you can see what the compiler actually generated.

For a small switch statement I wouldn't even think about it. I rarely have larger switch statement, since that probably means I could have done a better design to avoid it.

Share this post


Link to post
Share on other sites
The compiler can implement
switch
any way it wants. It might be a jump table, it might be a big series of conditionals, or maybe something else more appropriate for the situation. It should really make very little difference to you, though, and whatever it picks is likely to be a good choice.

It's barely worth worrying about unless this is in the very core of your code (ie. running thousands of times per frame). If you're just curious from a geeky point of view, it's not specified, but it's quite likely to be a jump table.

Share this post


Link to post
Share on other sites
I'm curious from a "would like to know" point of view. I'm not asking because I'm trying to optimize a switch statement or something.

Share this post


Link to post
Share on other sites
The best way to learn is obviously to examine your compiler's assembly output :)

That said, in almost all cases a switch statement can be optimized to be considerably faster than a series of if/elses. It is specifically for optimization purposes that the case labels have the restrictions of only allowing constant integral expressions.

GCC, at least, has two ways to compile a switch statement, depending on if the range of the case values is dense or sparse, respectively (whether a given range is dense or sparse is up to the compiler to decide, obviously):

1) Use a jump table. That is, create an array where for each (compile-time evaluated) case value, there is a jump address at the corresponding index pointing to the code for that case. So all that the switch becomes is a single, constant time, table lookup, independent on how many cases there are. No comparisons whatsoever need to be made, so obviously, this is *fast*.

2) Do a binary search: by comparing the given value to the median of the case values, eliminate half of the possibilities on each round. This gives us a logarithmic time complexity, still much faster than the naive O(n) linear search when the number of cases is large.

For example, consider the following code:

switch(val)
{
case 34: a(); break;
case -54365: b(); break;
case 0: c(); break;
case 789: d(); break;
case -1: e(); break;
case 788: f(); break;
case 2345678: g(); break;
default: h(); break;
}



This could be turned into:

if(val < 34) {
if(val < -1) {
if(val == -54365) b(); else h();
}
else if(val > -1) {
if(val == 0) c(); else h();
}
else e(); /* val == -1 */
}
else if(val > 34) {
if(val < 789) {
if(val == 788) f(); else h();
}
else if(val > 789) {
if(val == 2345678) g(); else h();
}
else d(); /* val == 789 */
}
else a(); /* val == 34 */


(If there's no default case, the innermost level of comparisons is unnecessary.)

When the number of cases is small, as above, binary search hasn't *that* much advantage over linear search, but consider that with binary search, doubling the number of cases only takes *one* additional comparison, whereas with linear search, the number of comparisons made is also doubled.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!