How Switch case Statement Implemented or works internally?

Question

I read somewhere that the switch statement uses "Binary Search" or some sorting techniques to exactly choose the correct case and this increases its performance compared to else-if ladder.

And also if we give the case in order does the switch work faster? is it so? Can you add your valuable suggestions on this?

We discussed here about the same and planned to post as a question.

Depends on the compiler and the actual switch cases. Some common implementations are demonstrated in [Secrets of Reverse Engineering](http://www.amazon.co.uk/dp/0764574817/). — DCoder, Dec 28 '12 at 09:48
This would be very compiler specific. The limited times I've looked at assembler output most seem to just use jumps tables, I've never seen a binary search but would be plausible for an optimised compiler with enough case clauses where the expressions were spaced apart to make it worthwhile. — PeterJ, Dec 28 '12 at 09:49
Duplicate of: http://stackoverflow.com/questions/2596320/how-does-switch-compile-and-how-optimized-and-fast-is-it — Reuben Morais, Dec 28 '12 at 09:53
@2vision2, not really, I've only looked at embedded processor output mainly. But this kind of search would only make sense of sparse case values, which I've never seen a lot of in practice. — PeterJ, Dec 28 '12 at 09:54
My personal experience with GCC is limited, and I can only point to [one interesting example](http://news.ycombinator.com/item?id=1301529). Edit: of course, if you're curious, you should compile multiple different switch() statements and disassemble the results. — DCoder, Dec 28 '12 at 09:54
@DCoder http://www.codeproject.com/Articles/100473/Something-You-May-Not-Know-About-the-Switch-Statem — 2vision2, Dec 28 '12 at 10:02
That is a nice article, but again - the compiler is free to implement a switch however it wants - as a series of if/else, as a one-level or multi-level jump table, as a binary search pattern... the fact that MSVC implements them in a particular way does not guarantee that GCC, clang or ICC will do the same. — DCoder, Dec 28 '12 at 10:04
@ReubenMorais disagree with duplicate because that was Visual C++ specific. If else vs switch is likely to answer this as well: http://stackoverflow.com/questions/97987/advantage-of-switch-over-if-else-statement is likely to answer this as well. — Ciro Santilli OurBigBook.com, Jun 23 '15 at 10:09

score 22 · Accepted Answer · edited Jul 25 '16 at 13:51

22

It's actually up to the compiler how a switch statement is realized in code.

However, my understanding is that when it's suitable (that is, relatively dense cases), a jump table is used.

That would mean that something like:

switch(i) {
  case 0: doZero(); break;
  case 1: doOne();
  case 2: doTwo(); break;
  default: doDefault();
}

Would end up getting compiled to something like (horrible pseudo-assembler, but it should be clear, I hope).

load i into REG
compare REG to 2
if greater, jmp to DEFAULT
compare REG to 0
if less jmp to DEFAULT
jmp to table[REG]
data table
  ZERO
  ONE
  TWO
end data
ZERO: call doZero
jmp END
ONE: call doOne
TWO: call doTwo
jmp END
DEFAULT: call doDefault
END:

If that's not the case, there are other possible implementations that allow for some extent of "better than a a sequence of conditionals".

edited Jul 25 '16 at 13:51

Mrunal

13,982
6
52
96

answered Dec 28 '12 at 09:53

Vatine

20,782
4
54
70

1

The “use value as offset jump destination” trick doesn’t work for cases like `switch( i ) { case 0: foo(); case 9999999: bar(); }` otherwise it would massively add to the compiled program size. – Dai Aug 26 '19 at 23:00
Yes, other possible implementations would be "a hash table of target addresses", "a few jump tables, with a bunch of if/then/else to get to the right table", etc. The exact form would depend on the exact code. – Vatine Sep 01 '19 at 12:10

score 12 · Answer 2 · answered Dec 28 '12 at 10:05

How swtich is implemented depends on what values you have. For values that are close in range, the compiler will generally generate a jump table. If the values are far apart, it will generate a linked branch, using something like a binary search to find the right value.

The order of the switch statements as such doesn't matter, it will do the same thing whether you have the order in ascending, descending or random order - do what makes most sense with regard to what you want to do.

If nothing else, switch is usually a lot easier to read than an if-else sequence.

I think you've captured the main point - a compiler doesn't have to be consistent about the code it emits for a `switch` statement, it can choose a strategy based on your actual conditions. — Mark Ransom, Jul 30 '21 at 17:41

score 1 · Answer 3 · answered Dec 28 '12 at 10:01

1

On some googling I found some interestin link and planned to post as an answer to my question. http://www.codeproject.com/Articles/100473/Something-You-May-Not-Know-About-the-Switch-Statem

Comments are welcome..

answered Dec 28 '12 at 10:01

2vision2

4,933
16
83
164

Yes, that's sort of what I tried to say - the compiler will build tables and use them to jump through. But it may also use compare/jump statements, and it will hybridize between the two if that leads to "better" code [all depending on what you define as better - someone may think that having 32KB of table to sort out a switch-statement is better than four jumps, because those jumps are bad to predict in the branch prediction in the processor, but someone else thinks it's ridiculous to have 32KB to solve this particular case] – Mats Petersson Dec 28 '12 at 17:08

score 0 · Answer 4 · answered May 09 '21 at 13:37

Although it can be implemented as several ways it depends on how the language designer wants to implement it. One possible efficient way is to use Hash Maps Map every condition (usually integer) to the corresponding expression to be evaluated followed by a jump statement. Other solutions also might work as often switch has finite conditions but a efficient solution shall be to use Hash map

How Switch case Statement Implemented or works internally?

4 Answers4

Linked

Related