21

From what I have read I can summarize,

  • Switch case is implementation defined but is mostly defined as a jump table
  • Switch case makes the code more readable
  • Switch is faster than if/elseif (?)

Consider a case where I have 300+ switch cases. I know an if/elseif in this scene will be a mess.

But I want to know how will a switch case perform in such a scene?

  • Is it scalable i.e it remains relatively faster than an if/else no matter how many cases are present ?
  • Since it is implementation defined how can I figure out how my compiler is implementing it?
  • And above all how do I do this if/elseif - switch comparison apart from actually writing the code and using a profiler? I have tried compiling a small .c file with switch case using gcc 4.8.1 -S switch and it looks like a jump table is created.Where do I go from here?
  • Is it better/worse to use an if/elseif in such scenarios

I am primarily interested in C/C++ specific details

Suvarna Pattayil
  • 5,136
  • 5
  • 32
  • 59
  • jump tables are *fast*. – Karoly Horvath Feb 05 '15 at 09:14
  • If/else has more flexibility with conditions, but switch/case can only operate with int-based types and allows only == operation – VolAnd Feb 05 '15 at 09:14
  • I'm not sure about 300+ cases. "ANSI C requires at least 257 case labels be allowed in a switch statement." – VolAnd Feb 05 '15 at 09:16
  • @KarolyHorvath Are jump tables scalable? Is there a performance issue when you have a big switch statement.I mean in terms of the compiler creating a jump table and accessing it ? – Suvarna Pattayil Feb 05 '15 at 09:17
  • 8
    Most of modern compilers would optimize a bunch of if's into a jump table anyway, so you will not notice any difference. One could also argue that if you have to make 300 if conditions in one place, your code is badly designed – SingerOfTheFall Feb 05 '15 at 09:17
  • @VolAnd IN `C99`, IT'S `1023 case labels for a switch statement` – Sourav Ghosh Feb 05 '15 at 09:18
  • @VolAnd You mean atmost 257 case labels? – Suvarna Pattayil Feb 05 '15 at 09:19
  • Even in cases when jump tables are not efficient from compiler point of view it is able to [replace it](http://goo.gl/gkTgWi) with binary-search-like comparisons. – dewaffled Feb 05 '15 at 09:21
  • Scalable to what? The more cases, the more it will outperform an if/else. NB jump tables aren't the only option. – user207421 Feb 05 '15 at 09:21
  • 1
    @SingerOfTheFall Yes I would agree with the ill designed part.It is a legacy code and from its use case i.e runtime choosing of subclass based on the switch condition maybe it was most feasible – Suvarna Pattayil Feb 05 '15 at 09:22
  • 2
    How does switch perform? Measure it! Is it scalable? Yes, the worst case is like chain of if/else. How is compiler implementing switch? Look at the generated assembly code. It's not always jump table. If the values in case labels are far apart (e.g. case 1, case 10000, case 90000), then switch is converted to series of if/else or mix of if/else and jump table. Is if/else better than switch? Measure it. – sdkljhdf hda Feb 05 '15 at 09:24
  • @EJP I meant scalable in terms of speed with increase in number of switch cases.You answered my query anyway. – Suvarna Pattayil Feb 05 '15 at 09:24
  • 23
    If you have 300+ switch cases, what you need is refactoring. – rubikonx9 Feb 05 '15 at 09:28
  • 1
    @Suvarna The more interesting question to pose to the community would be how to fix this ill-designed code so that you don't need either the switch or the if/elseif chain. I look forward to seeing that question :) – user3386109 Feb 05 '15 at 09:29
  • @user3386109 Yes, I guess I need to look at the code from a fresher perspective – Suvarna Pattayil Feb 05 '15 at 09:38
  • 1
    It isn't implementation-defined (that is, an implementation doesn't need to document its choice nor be consistent). – mafso Feb 05 '15 at 13:16
  • Sounds like what you need is not an `if/else` or a `switch`, but a `map` – David says Reinstate Monica Feb 05 '15 at 14:24
  • "how can I figure out how my compiler is implementing it"? Look at the assembly output. – glglgl Feb 05 '15 at 15:32
  • 1
    @lego Amen! ["If you have two horses and you want to know which of the two is the faster then race your horses."](http://ericlippert.com/2012/12/17/performance-rant/) – Filburt Feb 05 '15 at 16:40
  • @Filburt: Oftentimes, I find myself with two horses that seem roughly equal, but want to know if there are any situations where one of the horses might be an order of magnitude slower than expected. Such situations aren't hugely common, but I've been bit a few times, and thus would prefer to avoid them if possible. – supercat Feb 05 '15 at 20:40

4 Answers4

24

The compiler might decide to use a jump table and make a huge improvement in the case of 300+.

Compilers do make optimizations over branches using various techniques like decision trees .

The more easy is for a compiler to understand the code, the better. And the switch statement is more readable for the compiler as well.

Think about the else if from a compilers point of view . It would look like an arrowhead :

    - if 
     - else
      - else 
       - else
        - else

You need to evaluate each previous if in order to get to the correct else .

However a Switch looks more like a block :

     - case
     - case
     - case
     - case

So the compiler can sometimes determine where to go directly.

For your bullet questions :

  1. it is scalable. It's easy to be written by the developers and if the compiler uses jump tables adding more cases won't affect.

  2. it's up to the compiler to decide what to use. It might choose to not optimize it at all (but most likely jump tables).

  3. You can run a loop and meassure times by hand maybe ?

  4. It's always better to use switch. The worst case scenario the switch will act just as an if/else .

glglgl
  • 89,107
  • 13
  • 149
  • 217
MichaelCMS
  • 4,703
  • 2
  • 23
  • 29
  • 3
    "It's always better to use switch." In performance, yes. In readability and potential for programmer error, no. – Paul Draper Feb 05 '15 at 17:06
  • Why can't a compiler determine that a given set of if..else statements are logically equivalent to a switch, and optimize accordingly? – PythonNut Feb 05 '15 at 19:31
  • 1
    @PaulDraper: Even in terms of performance, a chain of `if` statements may be better if each `if` ends up being true roughly half the time it's executed (so half of the items satisfy the first `if`, a quarter satisfy the second, an satisfy the third, etc. Obviously that exponential decay is not going to continue for 300 items, but using `if` statements for the parts of the list which represent the most frequent usage cases can sometimes be a significant win as compared with a `switch`. – supercat Feb 05 '15 at 22:57
  • @PythonNut, a [sufficiently smart compiler](http://c2.com/cgi/wiki?SufficientlySmartCompiler) certainly *can*. The mostly likely reason it wouldn't is that the programmer inadvertently wrote the if-else in a way that is not convertible by the compiler. Writing a switch-case from the start with guarantees this. FYI, some features in other languages try to bridge the abstraction/optimization gap. Scala has the [`@switch`](http://www.scala-lang.org/api/2.11.4/index.html#scala.annotation.switch) annotation, requiring compilation to a JVM tableswitch or lookupswitch, or else failure to compile. – Paul Draper Feb 05 '15 at 23:10
  • @supercat, you describe a `O(log n)` algorithm. switch-case (when compiled to a lookup table) is **`O(1)`** – Paul Draper Feb 05 '15 at 23:11
  • @PaulDraper: If half the data items match the first `if`, a quarter match the second, etc. the average number of `if` statements to be evaluated will be two. A table-based switch is apt to take about as long as 3-5 simple-condition `if` statements. Note that in some real-world situations, the first `if` might be the taken branch 99% of the time, in which case the average number of `if` statements executed might be closer to one. – supercat Feb 05 '15 at 23:14
  • @supercat, yes there may be a space in which the nested if-else you describe is better than sequential conditions or table lookup. And branch prediction may also help if-else out. I'm not sure. – Paul Draper Feb 05 '15 at 23:23
  • @PaulDraper: Generally it's not worth pulling out more than one or two `if` cases that could be handled by a `switch`, but if e.g. a variable is going to be zero 99% of the time, it's often better to say `if (foo != 0) switch(foo) {...}` than to simply have the zero case be handled in the switch. – supercat Feb 06 '15 at 00:05
4

Compilers for most of the low end processors(Mostly Used in Embedded Systems) compiler do not always generate jump table for switch case.

If the case variables are in sequence (e.g 1,2,3,4....) then jump table implementation of switch case is preferred by compiler ,but for random sequence of case variable(e.g. 12,344,565,1,5...) compiler generates same code as generated in case of if-else code.

Sometimes,due to this developers land into trouble when adding a random case variable into already OK code may change the whole implementation of the that section of code which can result major change in code execution timing and code size. These are most concerning point to a embedded developer.

Vagish
  • 2,520
  • 19
  • 32
  • 2
    @EJP why is this untrue? I has faced this issue on one of my projects. I am not saying this is the behavior of all compilers.Please explain me your point if am missing something. – Vagish Feb 05 '15 at 09:46
  • My point is that when you use switch statement in resource critical systems you should be aware of what your compiler is doing with your code. – Vagish Feb 05 '15 at 09:50
  • You should say “If … compiler generates …” if you actually mean “If … compiler *may* generate …” or “I encountered *one* compiler which generates …if …” – Holger Feb 05 '15 at 13:57
  • @Holger, have you considered to rewrite your comment using switch? ;) – jmster Feb 05 '15 at 20:09
  • Damn typo it should be: You *shouldn’t* say “If … compiler generates …” if you actually mean “If … compiler *may* generate …” or “I encountered *one* compiler which generates …if …” – Holger Feb 06 '15 at 09:43
2

An if else is better than a switch case in the event that you have few choices, with deep decision trees, or need to use non-specific decision making,

ie. it's easy to implement an if statement that checks whether an int is greater than 0, which is more difficult to build into a switch statement. This is the type of logic that is best implemented using if statements.

If you have a flat, very broad, but specific condition dependent decision table, then a switch case is better. For example, you want specific things to happen if when a value is either 1, 2, 3, 4...etc to 10, it will be easier and saner to use a switch case.

In the end, modern compilers will change it to whatever is most efficient computationally, but how you built it will affect functionality, and supportability once you build it.

axjjienn
  • 56
  • 4
1

From the question of comparing a switch with an if..then..else construct, ~I assume that you are only cocnerned with a situation where a single test is required and the outcome depends on the answer (eg if x == ?? then ...). It is always better to use a switch in this case since: a) you cannnot introduce an erroneous condition part way down the chain of tests. b) the test is only undertaken once.

Donald Ashton
  • 51
  • 4