embedded software boot camp

Efficient C Tip #12 – Be wary of switch statements

Saturday, April 10th, 2010 by Nigel Jones

This is the twelfth in a series of tips on writing efficient C for embedded systems. Like the previous topic, I suspect that this will be a bit controversial. As the title suggests, if you are interested in writing efficient C, you need to be wary of switch statements. Before I explain why, a little background will be useful. I did all of my early embedded systems programming in assembly language. This wasn’t out of some sense of machismo, it was simply a reflection of the fact that there were no high level languages available (with the possible exception of PL/M). Naturally as well as programming embedded systems I also did computer programming, initially in Pascal and BASIC, and later in C. One of the major differences I found in using the HLL was the wonderful switch / case statement. I found it to be a beautiful tool – with a few lines of source code I could do all sorts of powerful things that were simply very difficult or tedious to do in assembly language. Fast forward a number of years and C compilers began to become available for small embedded systems and so I naturally started using them, together with of course the attendant switch statement. All was well in paradise until the day I used a switch statement in an interrupt service routine and found to my horror that the ISR was taking about ten times longer to execute than I thought was reasonable.

This precipitated an investigation into how exactly switch statements are implemented by the compiler. When I did this, I discovered a number of things that should give one pause.

Heuristic Algorithms

The first thing I discovered is that compilers typically have a number of ways of implementing a switch statement. They seem to be loosely divided into the following trichotomy:

  1. An if-else-if-else-if chain. In this implementation, the switch statement is treated as syntactic sugar for an if-else-if chain.
  2. Some form of jump or control tables, or as they are sometimes called a computed goto. This is a favorite technique of assembly language programmers and the compiler writers can use it to great effect.
  3. A hybrid of 1 & 2.

Where it gets interesting is how the compiler decides which approach to use. If the case values are contiguous (e.g. zero through ten), then it’s likely the compiler will use some form of jump table. Conversely if the case values are completely disjointed (e.g. zero, six, twenty, four hundred and a thousand) then an if-else implementation is likely. However what does the compiler do when, for example, you have a bifurcated set of ranges such as zero-ten and ninety – one hundred? Well the answer is, that each compiler seems to have some form of heuristic algorithm for determining what is the ‘best’ way of implementing a given set of cases. Although some compilers allow you to force a particular implementation, for the most part you are at the mercy of the compiler.

Comparative Execution Speeds

If you think about it, it should become apparent that a jump table approach is likely to give a highly consistent time of execution through the decision tree, whereas the if-else -if chain has a highly variable time of execution depending upon the particular value of the switched variable.  Notwithstanding this, the jump table approach has a certain amount of execution overhead associated with it. This means that although its  mean execution time (which is normally the same as its worst and best execution time) may be dramatically better than the mean execution time of the if-else-if chain, the if-else-if chain’s best execution time may be considerably better. So what you say! Well in some cases, a particular value is far more likely to occur than the other values, thus it would be very nice if this value was tested first. However, as you will now see, this isn’t guaranteed…

Order of Execution

For many years I wrote switch statements under the assumption that the case values would be evaluated from top to bottom. That is, if the compiler chose to implement the switch statement as an if-else-if chain, then it would first test the first case, then the second case and so on down to the default case at the bottom of my source code. Well it turns out that my assumption was completely wrong. The compiler is under no such obligation, and indeed will often evaluate the values bottom to top. Furthermore, the compiler will often evaluate the default value first. For example consider a defaulted switch statement with contiguous case values in the range zero to ten. If the index variable is an unsigned int, then there are at least 65525 possible values handled by the default case, and so it makes sense to eliminate them first. Now if you know that the index variable can only possibly take on the values zero to ten, then you can of course eliminate the default statement – and then get excoriated by the coding standards / MISRA folks.

Maintenance

This is the area where I really get worried. Consider the case where you have a switch statement in an ISR. The code is working with no problems until one day it is necessary to make a change to the switch statement – by for example adding an additional case value. This simple change can cause the compiler to completely change the implementation of the switch statement. As a result, you may find that:

  1. The worst case execution time has jumped dramatically.
  2. The mean execution time has jumped dramatically.
  3. The stack space required by the ISR has jumped dramatically.

Any of these three possibilities can cause your program to fail catastrophically. Now of course one could argue ‘that’s why you test all changes’. However, in my opinion it’s far better to be proactive and to avoid putting yourself in this situation in the first place.

I’d also be remiss in not noting the dreaded missing break statement maintenance problem. However as a religious user of Lint, I’m not normally too concerned about this.

Switch statement alternatives

If performance and stability is your goal then I strongly recommend that you implement your code, the way you want it executed. This means either explicitly use an if-else-if chain or use function pointers. If function pointers scare you, then you might want to read this article I wrote on the subject.

Recommendations

Based on my experience, I have a number of things that I do when it comes to switch statements. If you find my analysis compelling, you may want to adopt them:

  1. Switch statements should be the last language construct you reach for – and not the first.
  2. Learn how to use function pointers. Once you do you’ll find a lot of the reasons for using switch statements go away.
  3. Try to keep all the case values contiguous.
  4. If you can’t keep the case values contiguous, go to the other extreme and make them disparate – that way you are less likely to have the compiler change the algorithm on you.
  5. If your compiler supports it, consider using pragmas to lock in a particular implementation.
  6. Be very wary of using switch statements in interrupt service routines or any other performance critical code.
  7. Use Lint to guard against missing break statements.

Comments welcome!

Next Tip

Previous Tip

Home

21 Responses to “Efficient C Tip #12 – Be wary of switch statements”

  1. Vomit says:

    I don’t really agree with most of the proposed advice: I never abandon core language constructs because of a bad experience with some bad compiler – some people reacted like that in the early VHDL days because of Synopsys’ bad language support and it deformed an entire generation of hardware designers that got scared of the more “advanced” language constructs (pretty normal statements actually, but the crappy compiler support got people scared) and the people ended up essentially writing assembler-like micro-detailed code in a HLL that could do so much more.
    But I don’t want to go into that, to each his own taste. I just wanted to mention my solution for 7:
    switch(var) {
    case 1: {
    int i;

    } break;
    case 2: {
    } break;
    case 3: case 4: {
    } break;
    }

    If one makes a habit of creating each case statement as “case num:{}break” before filling the contents, one
    a. gains a useful declarative part where local variables could be declared
    b. never forgets the break
    c. the case{ and }break form sort of a syntax, where the brace protects the line against the loss of the “break”.

    and if I really need fallthrough then it’s clearer to change the case’s ending line into something like “} // fallthrough” than to leave the next person wondering if it was intended.

    • Nigel Jones says:

      I didn’t think I was advocating abandonment of the switch statement. I am advocating that when you use it you should be aware that small changes to your source code can result in the compiler switching its implementation algorithm, possibly resulting in big changes to the execution time, stack space etc. Incidentally I’ve found this to be the case on a lot of ‘good’ compilers.

      Regarding how you implement a switch statement – I think it has merits. I like the concept of the {…} protecting against an inadvertent loss of the break statement. I still think Lint is the best line of defense against this (and many other problems). However I’m all in favor of coding disciplines that minimize problems on the front end, rather than relying on tools to catch them on the back end. Thanks for the tip.

  2. Bob Weiman says:

    You make some interesting points in your article. I think that avoiding switch statements in ISRs where you need repeatable, consistent timing is good to keep in mind. However, I would disagree with recommendation #1, “Switch statements should be the last language construct you reach for – and not the first.”

    This might be true for ISRs but not for the foreground code. Even in embedded systems programming, fastest speed of execution is not always the most important priority. Most embedded systems have a few areas that need to be coded for fastest speed. The rest should be coded for maximum clarity and maintainability.

    Writing clear, easy to read maintainable code is very important. The real cost of software is in maintaining, upgrading and updating it.

    I have seen far to many highly nested if-then-else structures that are hard to understand and difficult to maintain. It is also difficult to prove that all cases are handled which increases the possibility of software bugs. A finite state machine implemented as a switch statement it much easier to read. It is also easier to prove that all cases are handled properly.

    My advice is to optimize the areas that make a critical difference and document them. I think switch statements can be used to simplify code and make it more readable. The possible inefficiencies of using switch statements are outweighed by readability. That will save more money for companies in the long run.

    I liked your article. You brought up some interesting points that many programmers would not have thought about.

  3. I once tried using a case starement in Keil C for 8051….. about 20 branches turned into a horrendous amount of code…..

    And the dratted chip only had 4K of ROM!

    I guess they’ve no doubt sorted that in the intervening 10 years, but it was a lesson to me.

    D.

  4. Kyle Bostian says:

    I was a believer in switch statement state machines until Nigel introduced me to arrays of pointers to functions. In fact, this week I am adding features to code Nigel authored that uses this approach and I think it is much easier to maintain than a long, complex switch statement. The technique might be a useful and interesting topic for a post, given the comments here.

    • Travis says:

      “…much easier to maintain than a long, complex switch statement” is the deciding factor.

      “Long, complex” == difficult to decipher and understand, so the programmer’s time must also be considered.

  5. Laz says:

    You didn’t mention any good reasons for using switch/case. I have found them very useful for state machines and command/address parsers. The former could be managed with function pointers, but it becomes more difficult to see the overall state machine flow, and more complicated to add a new state (as noted above). Using a switch/case for a parser keeps everything in one place, and often the commands are simple enough to implement right there (unless it violates containment).

  6. Daryl Fortney says:

    I tend to consider which construct is most appropriate for each situation and have found both ‘if’s and ‘switch’s valuable but i really like vomit’s idea to use {} inside cases especially since often i want to declare a variable inside a case and the idea of not using a brace when the code is otherwise indented always has seem inconsistent to me. I guess that is something I just never thought about. As well, being reminded about the power of function pointers for certain switch-like uses is good to keep in mind.

    What I like most about this blog is not necessarily the advice given but the fact that it makes you think twice about how you do things and how you could improve.

    • Nigel Jones says:

      What I like most about this blog is not necessarily the advice given but the fact that it makes you think twice about how you do things and how you could improve.

      I thinks that’s one of the best things anyone has ever said about this blog Daryl – so thank you. Developing this idea a little bit, while there are indeed some fundamental truths in the embedded world, the space is in general so large and diverse that almost any advice can be shown to be poor in certain circumstances. Thus read, learn, but above all think!

  7. Lundin says:

    “Now if you know that the index variable can only possibly take on the values zero to ten, then you can of course eliminate the default statement – and then get excoriated by the coding standards / MISRA folks.”

    The question is, how can you know? The reason MISRA enforces “default”, as well as “else” after every “if-else if”, is for one purpose, and that is defensive programming. If your memory gets corrupted by bugs or by hardware-related problems (EMI memory corruption, broken ADCs, brownout etc etc), a default statement can catch those and you can gracefully terminate/reset the program, instead of running haywire.

    The term defensive programming is typically completely alien to pure software academics. There is just no way they can get in their head that the program may be exposed to the real world outside their desktop, and that an algorithm that is perfect in theory may not be perfect in practice. An -engineer- should however understand and practice defensive programming, especially in safety-critical systems.

    • Nigel Jones says:

      An interesting comment Daniel. To the first part as to how can I know that a variable is range limited? This can occur in a number of ways. For example, let’s say I read a 4 bit DIP switch attached to an 8-bit port. Having read the port, I mask off the unused bits leaving me with a 4 bit variable that can only take on the values of 0-15. If I follow this with a switch statement that has explicit values for 0-15, then the default statement is, in theory, pointless.

      To your second point concerning defensive programming. Let’s assume that between masking the DIP switch value and testing it, some form of corruption occurs, such that it is no longer range limited to 0-15. In this case, a default statement may provide a modicum of protection. I say ‘may’ because if the compiler chooses to implement the switch statement as a jump table, then it will probably emit code that consists of:

      Check that the value is less than 16
      If it is, index into the jump table
      Else jump to the default handler

      Of course, this begs the question, what happens if corruption occurs between the check and the index into the jump table?

      Notwithstanding this, I think your comment illustrates that there is a natural tension between efficient programming and defensive programming. Efficiency is typically about doing just enough to get the job done. Defensive programming is about trying to ensure that the real world doesn’t intrude and cause your system to crash. I use defensive programming by default (if you would pardon the pun) and efficient programming when I have to. Incidentally I wrote a posting a few years ago about another defensive issue – IEC60730. I’d be interested on your comments on that.

  8. Lundin says:

    For the dip-switch example, there is a rather likely scenario is some sort of subtle bug introduced when masking, because of the integer promotions in C. The ~, <<, >> operators are particularly notorious for such. If such a bug slips through into production code, the product will go haywire, instead of reporting that an unexpected error has occured. It will be quite easy to find that bug too, with a proper error report from the program.

    And naturally, many defensive programming methods will be very resource-consuming. I’d be wary of taking things to the extreme, as preached by standards like 60730 or its evil brother 61508, that encourage crazy practices like “walking pattern” memory tests, where you in runtime move a bit pattern through the whole RAM to check for corrupt cells. I’m quite sure that such algorithms will not only be incredible slow, they will be introduce notable hazards and needless complexity. I don’t think programmers should fiddle around with such, it should be implemented in hardware. Such efforts are also currently being made by MCU manufacturers.

    As a sidenote: after spending considerable time with standards like 61508 and ISO 13849, I always come to the conclusion it they are the work of bureaucrat madmen, and that the encouraged practices aren’t based on scientific proof, nor that they have any relevance to safety nor engineering.

  9. Lundin says:

    The nonsense “less than” and “greater than” symbols are supposed to be the left and right shift operators. The form is mistaking it for HTML tags or some such.

    • Nigel Jones says:

      I took the liberty of editing your original comment such that the operators are now correct. HTML is most definitely not conducive to leaving comments concerning C operators.

  10. Bernhard Weller says:

    It might also help to have a look at the compilers intrinsics. Although the code will then get compiler-specific and less portable, in some applications it might be useful.

    Like the MSP430 compiler used in the Code Composer Studio has an intrinsic built in (_never_executed()) which tells the compiler, that the default case is never executed, and thus the variable in the switch statement has to be one of the cases handled above. (see TI document SLAU132) The compiler is then able to generate more efficient code.

    This puts some pressure on the programmer of course, he now has to ensure throughout the code, that the variable always maintains valid values.

  11. Mac says:

    Another way that switch statements can be compiled are as decrementing value.

    So switch (x)
    {
    case 0:Code_Zero(); break;
    case 1:Code_One(); break;
    case 2:Code_Two(); break;
    ..
    }

    .. gets compiled as:

    R0 = (x);
    JEQ CODE_ZERO();
    dec(R0);
    JEQ CODE_ONE();
    dec(R0);
    JEQ CODE_TWO();
    etc…

    It’s an optimization I’ve seen for switch statements but not for the equivalent ‘if’ structure.

  12. Raul says:

    Mr. Jones,

    Thank you for sharing your knowledge and experience.

    I read all 12 tips and learnt a lot!

  13. Roger Wehage says:

    You say that function pointers would be more efficient than switch/case statements. I have a situation where I need to call in random order about 20-40 different simple functions that the compiler would inline. The functions don’t have the same argument lists, so I can’t call them through a single array of function pointers, because the function pointer array requires that all functions have the same call list. Second, if I were to call the functions using function pointers, then it seems that the program would not be able to inline them. Now I would plan to have the case numbers run sequentially from 0 to the n-1, where n is the number of inlined functions. It seems that the savings of inlining the functions would outweigh the cost of using switch/case statements. Guess I will have to try both methods to see which is better.

    • Nigel Jones says:

      When you have a heterogenous set of functions life gets complicated. If they are all small enough that they can be inlined then live gets really complicated. If some functions are called more frequently than others then I’d be inclined to use an if else tree with the most frequently called functions at the top of the tree. If they are called with equal frequency then you may as well use a switch statement and let the chips fall where they may.

      BTW you can sometimes make function parameter lists the same by using unions and / or void pointers. This creates a different set of problems, but can be worth it in some instances.

  14. Alexander Lukyanov says:

    I think good compilers should use binary search for the sparse values switch case. It’s much better than the linear if-else-if-else search. AFAIK, gcc does.

Leave a Reply