9

Possible Duplicate:
Why Switch/Case and not If/Else If?

I would like to understand how a switch() case: statement in C is translated by the compiler into assembler opcodes.

Specifically, i'm interested in understanding the difference with a serie of if then else branches.

Performance comparison is the main topic.

A few words on vocabulary : i'm familiar with assembler main concepts, having coded in assembler a long time ago for simpler systems, But certainly do not now anything about x86 assembler semantic. So a direct assembler output will not be useful. Pseudo-code is much prefered.

Community
  • 1
  • 1
Cyan
  • 13,248
  • 8
  • 43
  • 78
  • check this link http://www.ashishpaliwal.com/blog/2009/08/if-else-vs-switch-%E2%80%93-which-is-better/ – Charan Pai Sep 21 '12 at 13:00
  • write something then open it in ollydbg, that's the best you can do to really understand it. – Pyjong Sep 21 '12 at 13:03
  • Lot of great answers here. It will be difficult to pick one.... – Cyan Sep 21 '12 at 19:04
  • I do not necessarily agree with the "duplicate" comment imposed on this question. While it's true both questions have some parts in common, the earlier one is much broader (why use switch/case ?), and as such receive answers on many issues, such as cleaner code, easier reading, maintenance, and so on. My question was specifically targeted at Assembler translation from the compiler, and expected impact on performance. A much more precise scope, which was properly answered here. – Cyan Sep 24 '12 at 01:52

4 Answers4

6

The compiler can decide to implement it as the equivalent series of if/else if statements, or it may decide to optimize it using a branch table. This depends on several parameters such as the number of branches and the size of minimum range that includes all values you check against.

Update: I remember reading somewhere that typically compilers do not bother to create a branch table unless there are at least 4 switch cases or more; Stephane Rouberol's informative comment below specifically documents how this threshold can be configured for GCC.

Community
  • 1
  • 1
Jon
  • 428,835
  • 81
  • 738
  • 806
6

Depending on various heuristics in the compiler the code generated can end up being just a simple chain of "if else if" statements. In some situations when the space of cases is small, the compiler can make a jump table, for example:

switch (foo) {
case 0:
    a();
case 1:
    b();
case 2:
    c();
case 3:
    d();
default:
    e();
}

Can be translated into something like:

if (foo < 0 || foo > 3) goto label_default;
else goto internal_jump_table[foo];

internal_jump_table = { label_0, label_1, label_2, label_3 };
label_0: a();
label_1: b();
label_2: c();
label_3: d();
label_default: e();

There are other optimizations that can be done. Instead of checking for equality, the compiler can build a hierarchy of if statements to binary search for the right value. Or you maybe have a bunch of values where a jump table is appropriate and a few outliers where normal searching is done. Or maybe just two jump tables.

Art
  • 19,807
  • 1
  • 34
  • 60
  • Wow, i wasn't aware it was possible to build one's own jump table using your sample C semantic. It looks great – Cyan Sep 21 '12 at 19:03
  • 1
    @Cyan It isn't. This was just pseudocode. There's a gcc extension to take addresses of labels and doing goto to them, but the syntax is different from what I wrote. – Art Sep 24 '12 at 07:17
  • arf, too good to be true... Anyway, your pseudo code clearly expressed your explanation. Thanks – Cyan Sep 24 '12 at 10:07
  • A complex question : let's assume that, as your example, i've got a switch with 4 values, {0, 1, 2, 3}. And let's assume that i can guarantee to provide only autorised values. Is there a way to avoid the sanity check which seems performed before the jump ? Regards – Cyan Sep 24 '12 at 20:51
  • I know that in the past gcc at least would skip the check and instead do something more efficient if you were switching on an enum and handled all the cases. But fiddling with it right now I can't get gcc to not check (I used a different processor architecture in the past though). Btw. the lower limit to generate a jump table seems to be 5 cases, 4 just makes a binary search. – Art Sep 25 '12 at 07:34
  • OK, thanks, that's very clear. Rgds – Cyan Sep 25 '12 at 18:20
2

The common response is always "that depends". The performance may depend on the platform/CPU-type, compiler, the compiler options etc.

I Do think, that given the right circumstances a switch() construct will have complexity log(n), where n is the number of case: statements. This is acheived by "binary search".

This page has lots of details (focuses on Microsofts compiler, but the general ideas I think apply in general).

S.C. Madsen
  • 5,100
  • 5
  • 32
  • 50
  • Surely given the right circumstances switch can have complexity O(1). – Joe Sep 21 '12 at 13:03
  • Right, if the cases are a sequence with no "holes"... I think. Otherwise you'll have to search. – S.C. Madsen Sep 21 '12 at 13:05
  • I meant, the best case is O(1) if there's a jump table. – Joe Sep 21 '12 at 13:07
  • Even if there are holes, the slots for them in the jump table can be filled by jumping to the "default" label or to the end of the switch, as applicable. It's more a question of how big the entire range is (and hence how big the jump table is) rather than whether it's densely populated. – Steve Jessop Sep 21 '12 at 13:08
  • Right, but that requires the "case" criterias to be in-sequence, doesn't it? – S.C. Madsen Sep 21 '12 at 13:09
  • I mean, you'll have to "scan" the table, if the values are not in sequence, or am I missing something obvious here? – S.C. Madsen Sep 21 '12 at 13:10
  • Well, if the cases are 1,3,5 and 13, then a 13-entry jump table would work. Or a 5-entry jump table plus a check for the special case of 13, or whatever else the compiler-writer thinks of. – Steve Jessop Sep 21 '12 at 13:10
  • Ah, yes, I think you're missing something: in the best case the jump table isn't a list of "case, address" pairs, it's just a list of addresses, and the index of the address in the list *is* the value of the case (perhaps minus some offset equal to the value of the smallest case). – Steve Jessop Sep 21 '12 at 13:11
  • Right, but if the values are 0, 2000, and 92834542 that won't work – S.C. Madsen Sep 21 '12 at 13:12
  • Indeed, the worst case is not `O(1)`, at least not within reasonable code size. The compiler has the advantage that it knows how many cases there are, and their values, so it never has to emit "general" code. – Steve Jessop Sep 21 '12 at 13:12
  • Okidoki, so I guess I should've phrased it "significant holes" :-) – S.C. Madsen Sep 21 '12 at 13:14
  • The point is, there are a number of different cases, for which there are different solutions, possibly including jump tables, runs of ifs, binary search etc. – Joe Sep 21 '12 at 15:52
  • Noone mentioned the possibility to use a hash if the range is large with many holes? This is an interesting alternative to binary search. – galinette Jul 22 '21 at 10:50
1

Considering a "big enough" number of switch cases (enough to let the compiler opt to generate a branch table instead of a simple if / else if):

  • a switch-case will have constant time (O(1)) access to the correct block of code to be executed,

  • while a series if/else if statements will have linear time (O(n) where n is the number of conditions to evaluate (if statements), for n >= "big enough")

Update: Of course these considerations do not take into account compiler optimization!

Sdra
  • 2,297
  • 17
  • 30
  • Implementation with `if` should have O(log(n)) time, since one would implement the tests with a binary search (or equivalent; many machines produce a comparison results that allows a three-way distinction: less-than, equal-to, greater-than). – Eric Postpischil Sep 21 '12 at 13:33
  • mmm... not sure, I don't think the compiler is able to do semantic comparison between the condition evaluations of the *if* statements – Sdra Sep 21 '12 at 13:38
  • Of course it can. The controlling expression of a switch is an integer type, so it is well ordered. – Eric Postpischil Sep 21 '12 at 14:41
  • well, for a switch statement it can do even better than binary search (branch table), but not for if statements where the condition expressions may be unrelated each other. – Sdra Sep 24 '12 at 08:57