Optimizing Switch-Case Statements In C For Speed
Subscribe To Our Feed | Follow Us On Twitter | Get Updates on Email
The biggest bottlenecks in making efficient code today are jumps or branches. You must have always heard of people telling you to use switch-case blocks instead of cascadin if-else’es. They were right, but partially.
This is because a cascading if-else block will check for each condition in each iteration until it reaches the correct one. On the other hand, switch-case blocks are “supposed to” (why supposed to, we’ll see just now) just execute the correct statement and move on.
Optimization Technique 1: Keep the case label values close and small (Answer to “supposed to”)
Actually switch-case statements are also many times changed into if-else cascades by the compilers. This happens when the case label values are too far apart and/or are spread over a fairly large range. If you have a small switch-case statement like below, then the compiler will generate a jump-table instead of the if-else cascade.
switch(a) { case 0: /*do something*/ case 1: /*do something*/ case 2: /*do something*/ case 3: /*do something*/ default: }
A jump table is like a “lookup table” or a “dispatch table”. You can assume that compiler creates an internal array of addresses. The array is indexed by the case lable values and the value at that index is the address of instructions corresponding to that case.
Optimization Technique 2: Place those cases first which are more likely to occur
As we just discussed that switch-case statements can also degenerate into if-else’s. So, if this happens we should follow what would have been best in case of an if-else cascade, i.e., keep those conditions in the beginning which are likely to be satisfied (or found true) most of the times. This is because while falling down the if-else cascade, the earlier the condition is satisfied, lesser will be the checks/branches our code will have to perform.
Optimization Technique 3: Nested switch-case statements
This “feature” of switch-case to if-else degeneration is quite a bit dependent on compiler implementation and hence your mileage may vary as some compilers might not take the order of case placement into consideration while generating the if-else ladder. In case, your compiler is one of these, do not fret. We are here to resque you. You can simulate the same behaviour as technique 2 by creating nested switch-cases. The idea is that whatever may be the implementation, the “default” case will always be the last condition (the “else” part) in the if-else ladder. So, we take advantage of this, place our most frequent few cases in top level switch, and the rest we stuff into the default case as a new, nested switch-case. e.g. if we have 6 cases 1 to 6 and their frequency of occurence is descending from 1 to 6, we can create something like what is show below.
switch(a) { case 1: /*do something*/ case 2: /*do something*/ case 3: /*do something*/ default: switch(a) { case 4: /*do something*/ case 5: /*do something*/ case 6: /*do something*/ default: /*do something*/ } }
So, this was it for today. Don’t forget to write in to let us know about your questions or your own tips and tricks to make your code faster and safer.
© Safer Code | Optimizing Switch-Case Statements In C For Speed
|
Liked this post? Get FREE Updates Subscribe to RSS feed 
|
Related posts
Tags: branches, C, efficient code, if-else, jump-table, Optimization, Optimization techniques, switch-case
Be sure to check also Duff’s device here: http://en.wikipedia.org/wiki/Duff%27s_device
Another viable option – especially if case blocks do lots of work – is to replace whole switch case with function pointer table/map and move the code into the functions.
But frankly I only rarely had problems with switch/case optimization. GCC is not perfect, yet most of the time results are OK.
Needless to mention is switch/case emulation of map look up (binary tree search) with nested switch/case statements.
@Andre Goddard Rosa: Yes, Duff’s device discussion is in the offing but in another context (loop unrolling) which is being taken care of in the latest series. Check out our latest post from Jan 27th.
@Dummy00001: The lookup table is indeed a good option. Thanks for reminding us.
1. actually, most modern/decent compilers will generate the “jump-table”. this renders “optimization technique 1″ irrelevant.
2. “optimization technique 2″ is also about weak (realy non-optimizing compilers) which fail to generate the jump-table. so, given the fact that the array is calculated by the compiler at compile time, then, of course, like any array, has a O(1), this “optimization technique” is also irrelevant.
3. “optimization technique 3″ is also a patch for poorly implemented compilers. in almost 40 years of c/c++, i’ve never seen something so weird.
besides, the whole thing (the whole idea of explicitly “optimizing” your code instead of using a decent compiler) is in lala land… (sounds like the late 60s, maybe early 70s).
like the author said “this was it for today”. quick reminder, we’re in 2009… just in case some of us haven’t noticed…
regards,
d
@daniel: Your assumption that a modern compiler will always generate the jump-table isn’t correct. Just write some code according to the limitations I’ve mentioned and assemble it to see the same. A compiler can goof up as well if not given enough pointers. Heck, gcc 3.x series can’t even create a good jump table for small switch case statements, leave apart the rest. Optimization of code is still a very relevant topic, especially if you are writing code for embedded devices. Moreover, not all compilers are good at optimization. If you have noticed, there are thousands of compilers out there in the market, many of which need to be used even if they are not that good at optimization.
Well,
given all the other common errors that are made, this case optimizing is something that is needed only in very specific cases. You normally would only need this if you want to optimize a CPU intensive task where the case statement is the bottleneck. Seems pretty far-stretched to me.
In 20 years of systems programming (in C) I don’t remember ever actually needing to optimize a case statement.
Also, if ever you encounter such a situation anyway, then #2 might prove the most useful advice.
@Ron: Thanks. You are absolutely correct in your observation that other issues/optimizations are worth more time than switch-case optimization. However, we’ve started this blog to capture as much as we can about these topics, however obscure it might be. So, you will see us covering this as well as all other aspects of optimization, security, etc that make up the base for a solid code. And I hope that readers like you, daniel, dummy, andre and others will keep us on our toes and correct us wherever we deviate from the right path. Thanks once again.
What a waste of time. Micro-optimizations are almost never helpful. Unless you know for sure the assembly code produced by the compiler, you’re just guessing. And even if you do examine the generated code… congratulations! You’ve wasted time micro-optimizing for *one* compiler on *one* processor architecture.
I also agree that the micro optimization is not always useful. There are lots of code patterns which can be observe by a compiler and can be optimized by compiler. But compilers do not implement all of these patterns and only observe most common code patterns. So it is batter to write the simple code without micro-optimization (which may be optimized for one processor but not for other), and let compiler do the optimization.
Rather than optimizing for speed, you should consider optimizing for safety and correctness. Whenever it makes sense, for example, when implementing a finite-state machine consider enumerators instead of integers. A good compiler like GCC will warn you about unhandled cases. Of course, that means you have to omit the “default:” label. You should still catch unhandled values like in the example below:
enum my_enum { a, b, c };
int
function(enum my_enum value)
{
switch (value) {
case a: return …;
case b: return …;
case c: return …;
}
/* handle unexpected case */
}
Of course you can also use goto or a flag, if use of return as above isn’t suitable.
By the way, a compiler can only generate a jump table if it can deduce that the switch parameter or the label values are from a limited range. A jump-table with UINT_MAX entries would be hardly efficient or desirable.