Switch statement instructions
Author
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?
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.
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.
The compiler can implement
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.
switchIt'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.
Author
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.
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:
This could be turned into:
(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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
