# Thread: Efficiency of case statements

1. Originally Posted by Dave_Sinkula
Throw in a couple of oddities such as not being 0-N (have holes). For example 1, 3, 5, ..., or start at 100 or -100 and have subsequent cases at differing intervals. Switches like that don't map to a jump table as easily, and that optimization may go away.
I'll try that, but I also randomized the cases output and returned a random value, not n. I got the same results. For example:
Code:
```int if_else_proc(int n)
{
if(n == 0) {return 6;}
else if(n == 4) {return 1002;}
else if(n == 1) {return 234;}
else if(n == 3) {return 546;}
else if(n == 2) {return 980;}
else {return -1;}
}

int switch_proc(int n)
{
switch(n)
{
case 0: return 6;break;
case 4: return 1002;break;
case 1: return 234;break;
case 3: return 546;break;
case 2: return 980;break;
default: return -1;break;
}
}```

2. Originally Posted by grumpy
On machines that support necessary instructions, a switch statement is compiled into a jump table (a table of labels (or instruction locations)) and a single jump instruction. At run time, that single instruction is used to jump to location specified by the integer value. No need to compare the integer against all possible values, which is how the "if" statement works.
Don't you mean "which is how the 'switch' statement works?"

3. Originally Posted by Yasir_Malik
I'll try that, but I also randomized the cases output and returned a random value, not n.
To clarify, I'd meant something more like this:
Code:
```int if_else_proc(int n)
{
if(n == 6) {return 0;}
else if(n == 1002) {return 4;}
else if(n == 234) {return 1;}
else if(n == 546) {return 3;}
else if(n == 980) {return 2;}
else {return -1;}
}

int switch_proc(int n)
{
switch(n)
{
case 6: return 0;break;
case 1002: return 4;break;
case 234: return 1;break;
case 546: return 3;break;
case 980: return 2;break;
default: return -1;break;
}
}```

4. Originally Posted by citizen
Also along with what Dave was saying, if you are coing to make an experiment like this than you should be aware that a switch has a maximum of like 270-something cases.
I believe at least 257 for C89 and 1023 for C99.

5. I generated 10000 case statements, and the compiler didn't complain. It took a long time to compile and the 10000 if-elses took a lot of time.

6. Originally Posted by Yasir_Malik
Don't you mean "which is how the 'switch' statement works?"
No, I did not.

What I meant is, for example, that
Code:
```switch(x)
{
case 1:
case 2:
something();
break;
case 3:
something_else();
break;
default;
something_else_again();
}```
gives the same net effect as
Code:
```   if (x == 1 || x == 2)
something();
else if (x == 3)
something_else();
else
something_else_again();```
However, the compiler has to do all the tests until it finds one that succeeds.

Let's say, x is given a value of 3. The switch statement (again assuming the target machine supports appropriate instructions) simply jumps to the appropriate label (or instruction) and calls something_else(). However, the "if" approach requires a test of x == 1 (which yields false), so x == 2 is then computed. That also yields false, so the next test (x == 3) is performed. That yields true, so something_else() is called.

If, on the other hand, x is given a value 5, the switch (again) jumps to the default label and calls something_else_again(). The if approach requires testing x ==1, x == 2, and x == 3 before deciding to call something_else_again().

The net effect is that the switch behaviour takes constant time, whereas the worst case effect of the if statement is to check the value x against all possible values it might hold. The worst case effect comes in when the final "else" clause is reached.

Some compilers might be smart enough to turn the above series of if/else statements into a switch, but I'm not aware of any that smart. The reason is that the translation only works if the value being tested is integral, as that's all the corresponding machine instructions support. And, more significantly, it will only need one change in the logic to make the make that optimisation more difficult, and potentially impossible.

For example, this is not readily amenable to an attempt by a compiler to optimise it;
Code:
```   if (x == 1 || x == 2)
something();
else if (x == 3 || x == some_function_return() || y == 7)
something_else();
else
something_else_again();```
as the bit in bold violates the requirements of a switch statement (and, incidentally, the machine instructions it would be translated to).

7. It's the worst case of premature optimisation disease I've seen in a long while...

8. Originally Posted by Salem
It's the worst case of premature optimisation disease I've seen in a long while...
Not really. The purpose of the switch statement was to allow optimisation on machines that allow it, over and above what is possible with an if/else. When C was originally designed, the difference was quite significant in practice; machines were somewhat less capable than they are now, and one of the design goals of C was to allow the programmer to get close to the machine to achieve efficiency (in various measures).

9. But there is no way you can look at any given switch/case statement and decide whether the compiler will implement it as a jump table or a series of if/else statements.

10. Originally Posted by Salem
But there is no way you can look at any given switch/case statement and decide whether the compiler will implement it as a jump table or a series of if/else statements.
Incorrect. A switch/case statement will be implemented as a jump table on any target machine that supports the necessary instructions.

In reality, the performance of switch/case comes at the expense of some form of memory (the jump table) compared with the if/else approach (which executes more instructions). Assuming that the same net behaviour is being implemented (i.e. different actions based on values of a variable, with possible values fixed at compile time), and a machine that supports a jump table, the if/else approach is a memory-usage optimisation while the switch/case approach is a performance (in terms of number of instructions executed) optimisation. In other words, without doing any gymnastics (eg turning if/else effectively into switch/case or vice versa) the compiler achieves an optimisation --- just against different criteria.

Which means that if something can be implemented as a switch/case, the resultant code will be performance optimised. But if something is implemented as an if/else, the resultant code will be memory-usage optimised. Without the compiler doing any gymnastics.

11. Originally Posted by grumpy
Incorrect. A switch/case statement will be implemented as a jump table on any target machine that supports the necessary instructions.
To me this looks like an if-else tree.
Code:
```   ;	int switch_proc(int n)
push      ebp
mov       ebp,esp
;	{
;		switch(n)
@15:
mov       eax,dword ptr [ebp+8]
cmp       eax,546
jg        short @23
je        short @20
sub       eax,6
je        short @22
sub       eax,228
je        short @21
jmp       short @16
@23:
sub       eax,980
je        short @19
sub       eax,22
je        short @18
jmp       short @16
;		{
;			case 6: return 0;break;
@22:
xor       eax,eax
@27:
pop       ebp
ret
;			case 1002: return 4;break;
@18:
mov       eax,4
@28:
pop       ebp
ret
;			case 234: return 1;break;
@21:
mov       eax,1
@29:
pop       ebp
ret
;			case 546: return 3;break;
@20:
mov       eax,3
@30:
pop       ebp
ret
;			case 980: return 2;break;
@19:
mov       eax,2
@31:
pop       ebp
ret
;			default: return -1;break;
@16:
or        eax,-1
;		}
;	}
@26:
@24:```

12. > In reality, the performance of switch/case comes at the expense of some form of memory
Which Dave just proved to you that you don't always get a jump table.

If your cases are sparse, then you'll end up with an if/else chain. Nobody wants a 10K jump table with only 5 entries used, that really would be a waste of resources.

If your cases are consecutive, then it's likely to be a jump table.

Like I said, you cannot know from just looking at your case statement which way any given compiler is going to implement it. You can make guesses based on past experience, but that isn't the same as "guaranteed to always be a jump table".