Efficiency of case statements

This is a discussion on Efficiency of case statements within the C Programming forums, part of the General Programming Boards category; Originally Posted by Dave_Sinkula Throw in a couple of oddities such as not being 0-N (have holes). For example 1, ...

  1. #16
    Registered User
    Join Date
    Sep 2003
    Posts
    224
    Quote 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. #17
    Registered User
    Join Date
    Sep 2003
    Posts
    224
    Quote 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. #18
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    Quote 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;
    	}
    }
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  4. #19
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    Quote 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.
    Last edited by Dave_Sinkula; 05-21-2006 at 08:49 AM. Reason: Added links.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  5. #20
    Registered User
    Join Date
    Sep 2003
    Posts
    224
    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. #21
    Registered User
    Join Date
    Jun 2005
    Posts
    6,255
    Quote 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. #22
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,490
    It's the worst case of premature optimisation disease I've seen in a long while...
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  8. #23
    Registered User
    Join Date
    Jun 2005
    Posts
    6,255
    Quote 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. #24
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,490
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  10. #25
    Registered User
    Join Date
    Jun 2005
    Posts
    6,255
    Quote 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. #26
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    Quote 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:
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  12. #27
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,490
    > 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".
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 5
    Last Post: 03-05-2009, 10:32 AM
  2. get keyboard and mouse events
    By ratte in forum Linux Programming
    Replies: 10
    Last Post: 11-17-2007, 04:42 PM
  3. Keypress reading
    By geek@02 in forum Windows Programming
    Replies: 1
    Last Post: 06-16-2004, 12:16 PM
  4. Converting Numbers to Words
    By denizengt in forum C Programming
    Replies: 20
    Last Post: 11-05-2003, 08:19 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21