Thread: Efficiency of case statements

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;
	}
}

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?"

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.

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).

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).

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.