Thread: Efficiency of case statements

  1. #1
    Registered User
    Join Date
    Sep 2003
    Posts
    224

    Efficiency of case statements

    Hello,

    I've always thought that switch statements were syntatic sugar for if-then-else
    statements, but when debugging, I've come to the conclusion that switch statements
    perform better than if-then-else statements. Here's some code to
    illustrate:
    Code:
    int main()
    {
      int a;
    
      a = 5;
    
      switch(a)
      {
        case 2:
          printf("2\n");
          break;
    
        case 3:
          printf("3\n");
          break;
    
        case 4:
          printf("4\n");
          break;
          
        case 5: 
          printf("5\n");
          break;
      }
          
      return 0;
    }
    Putting a breakpoint on the line with a = 5, and stepping through the code, I
    get to the line with the switch statement and then immediately to the last case
    statement.
    Is the debugger playing tricks with me? Or are case statements implemented with
    some sort of indexing scheme? I'm using gcc and gdb.

    Thanks.

  2. #2
    vae victus! skorman00's Avatar
    Join Date
    Nov 2003
    Posts
    594
    Using a debugger to see your code flow won't show you exactly how it flows underneath.

    I recall an instructor/professor/teacher kinda guy once saying that most compilers will turn most switch blocks into asm that more closely resembles if else's than a switch, but use a table lookup and a jump if there are 113 cases (that a big number, but I didn't question him at the time. He's very old school, so his info might be outdated).

    A lookup table is most suited for when you have consecutive case options, that way you can figure out your jump by simply indexing an array.

  3. #3
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    Quote Originally Posted by Yasir_Malik
    Is the debugger playing tricks with me? Or are case statements implemented with some sort of indexing scheme?
    Call it playing tricks, or call it high-level debugging.

    But implementations of a switch statement may vary. It may be implemented as an if-else type of thing; perhaps a beautiful jump table; it may be something else. It just needs to get to the code you want it to go to.
    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. #4
    Registered User ssharish2005's Avatar
    Join Date
    Sep 2005
    Location
    Cambridge, UK
    Posts
    1,732
    it cant be true that as soon as it enter the case its goes to the case 5 without checking the case before the case 5. it got to check each case weather a == case 2 ,3 ,4 5 as soon it got case 5 it executes the block and break the switch leaving all other cases below case 5 (if any) and comes out. withoout interating the siwtch how can it find the case 5 location. as said others its the way high-level debugger are implemented

    ssharish2005

  5. #5
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    Quote Originally Posted by ssharish2005
    it cant be true that as soon as it enter the case its goes to the case 5 without checking the case before the case 5.
    Sure it can.
    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.*

  6. #6
    Registered User ssharish2005's Avatar
    Join Date
    Sep 2005
    Location
    Cambridge, UK
    Posts
    1,732
    Quote Originally Posted by Dave_Sinkula
    Sure it can.
    so it means that when a program is complied it memorise the case location and store it the code/jump tabble is it?

    ssharish2005

  7. #7
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    Quote Originally Posted by ssharish2005
    so it means that when a program is complied it memorise the case location and store it the code/jump tabble is it?
    I'm not quite sure what you're saying, but the compiler could generate something like this (which is more pseudocode in C than anything accurate).
    Code:
    static void baz2(void) { printf("2\n"); }
    static void baz3(void) { printf("3\n"); }
    static void baz4(void) { printf("4\n"); }
    static void baz5(void) { printf("5\n"); }
    
    void baz(int a)
    {
       static void (*const bazx[])(void) = 
       {
          baz2, baz3, baz4, baz5
       };
       a -= 2;
       if ( a >= 0 && a < sizeof bazx / sizeof *bazx )
       {
          bazx[a]();
       }
    }
    This is one way to implement an equivalent switch without evaluating cases 2, 3, and 4 before getting to the 5th.

    Of course it might implement the switch like this.
    Code:
    void bar(int a)
    {
       if ( a == 2 )
       {
          printf("2\n");
       }
       else if ( a == 3 )
       {
          printf("3\n");
       }
       else if ( a == 4 )
       {
          printf("4\n");
       }
       else if ( a == 5 )
       {
          printf("5\n");
       }
    }
    The switch statement needs to produce correct code, but the implementation can do it a number of ways.
    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.*

  8. #8
    Registered User ssharish2005's Avatar
    Join Date
    Sep 2005
    Location
    Cambridge, UK
    Posts
    1,732
    well, right Dave in your first example. jumping directly on to the appropriate fucntion

    ssharish2005

  9. #9
    Registered User
    Join Date
    Sep 2003
    Posts
    224
    This is all interesting.

  10. #10
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    Don't forget that a smart compiler will optomize the switch statement right out in your code example. It's possible that the compiler will see that a will always be 5 and just leave the irrelevant case statements out of the binary.
    If you understand what you're doing, you're not learning anything.

  11. #11
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    A smart compiler might produce an array of ASM code, then redirect program flow to the relevant lines of code in RAM, in constant time. Who knows?

    If you want pure optimization, go write your own compiler
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  12. #12
    Registered User
    Join Date
    Sep 2003
    Posts
    224
    To investigate whether case statements are faster than an "if-else ladder", I wrote a script to generate C code. Here's an example of the generated code:
    Code:
    #include <sys/time.h>
    
    int if_else_proc(int);
    int switch_proc(int);
    float time_diff(struct timeval, struct timeval);
    
    int main()
    {
      int n, i;
      struct timeval start, end;
      
      srandom(time(0));
      
      gettimeofday(&start, 0);
    
      for(i = 0; i < 10000; i++)
      {
        n = random() % 6;
        if_else_proc(n);
      }
      
      gettimeofday(&end, 0);
      printf("Milliseconds processing if elses: %f\n", time_diff(start, end));
       
      gettimeofday(&start, 0);
    
      for(i = 0; i < 10000; i++)
      {
        n = random() % 6;
        switch_proc(n);
      }
    
      gettimeofday(&end, 0);
      printf("Milliseconds processing cases: %f\n", time_diff(start, end));
    
      return 0;
    }
    
    float time_diff(struct timeval start, struct timeval end)
    {
      if (start.tv_usec > end.tv_usec)
      {
        end.tv_usec += 1000000;
        end.tv_sec--;
      }
    
      return (end.tv_sec - start.tv_sec)*1000 +
             (end.tv_usec - start.tv_usec)/1000.0;
    }
    
    int if_else_proc(int n)
    {
    	if(n == 0) {return n;}
    	else if(n == 1) {return n;}
    	else if(n == 2) {return n;}
    	else if(n == 3) {return n;}
    	else if(n == 4) {return n;}
    	else {return -1;}
    }
    
    int switch_proc(int n)
    {
    	switch(n)
    	{
    		case 0: return n;break;
    		case 1: return n;break;
    		case 2: return n;break;
    		case 3: return n;break;
    		case 4: return n;break;
    		default: return -1;break;
    	}
    }
    When the mod value stayed the same whether there were 100, 1000, or 10000 if-else/switch statements, the switch statement would be about half a millisecond faster than the if-else statements, but all would take the same amount of time regardless of the number of cases. However, when the mod value was equal to the number of cases plus 1, I saw that the switch statement outperfomed the if-else statements. Here's a table of my results in milliseconds:
    Code:
    cases  if-else     switch
    100    2.892       2.003
    500    11.169      2.02
    1000   67.03       2.06
    This shows that the compiler, which in my case is GCC, uses some kind of indexing scheme for switch statements. I'll have a look at the assembly later.
    [edit]I'd like to add that the above output does not reflect any optimizations. With -O2, the if-else processes faster, but the switch is still much faster than the if-else.[/edit]
    Last edited by Yasir_Malik; 05-21-2006 at 08:25 AM.

  13. #13
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    The basic principle is that a lot of machines support a jump (sometimes named JMP, or something else, when you get to the assembler or machine language) which are essentially a conditional goto (i.e. the effective meaning of the instruction is jump to label[index]).

    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. The net effect, on machines that support the necessary instructions, is that jumping to the right case takes exactly one instruction. On machines that don't support the necessary instruction, a switch statement is effectively translated into an equivalent set of if/else statements. This means that, in worst case, performance of a switch statement is no worse than an equivalent set of if/else statements.

    In fact, the switch/case syntax in C/C++ is specified as it is to allow compilers to use a jump table, if the target machine supports it. That is the reason that a switch can only operate on an integral value, and why all the cases must be constant values.
    Last edited by grumpy; 05-21-2006 at 01:20 AM.

  14. #14
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    Quote Originally Posted by Yasir_Malik
    To investigate whether case statements are faster than an "if-else ladder", I wrote a script to generate C code. Here's an example of the generated code:
    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.
    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.*

  15. #15
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Quote Originally Posted by Yasir_Malik
    snip
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 5
    Last Post: 03-05-2009, 11:32 AM
  2. get keyboard and mouse events
    By ratte in forum Linux Programming
    Replies: 10
    Last Post: 11-17-2007, 05: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, 09:19 PM