Switch case optimization scenario

I am aware of various switch case opimization techniques, but as per my understanding most of the modern compilers do not care about how you write switch cases, they optimize them anyway.

Here is the issue:

void func( int num)

set = 1,2,3,4,6,7,8,10,11,15

{
     if (num is not from set )
  regular_action();
     else
      unusual_stuff();
}

The set would always have values mentioned above or something resembling with many of the elements closely spaced.

E.g.

set = 0,2,3,6,7,8,11,15,27 is another possible value.

The passed no is not from this set most of the times during my program ru开发者_StackOverflow社区n, but when it is from the set I need to take some actions.

I have tried to simulate the above behavior with following functions just to figure out which way the switch statement should be written. Below functions do not do anything except the switch case - jump tables - comparisons.

I need to determine whether compare_1 is faster or compare_2 is faster. On my dual core machine, compare_2 always looks faster but I am unable to figure out why does this happen? Is the compiler so smart that it optimizes in such cases too?

There is no way of feeling that one function is faster than the other. Do measurements (without the printf) and also compare the assembler that is produced (use the option -S to the compiler).

Here are some suggestions for optimizing a switch statement:

Remove the switch statement

Redesign your code so that a switch statement is not necessary. For example, implementing virtual base methods in a base class. Or using an array.

Filter out common choices. If there are many choices in a range, reduce the choices to the first item in the range (although the compiler may do this automagically for you.)

Keep choices contiguous

This is very easy for the compiler to implement as a single indexed jump table.

Many choices, not contiguous

One method is to implement an associated array (key, function pointer). The code may search the table or for larger tables, they could be implemented as a linked list. Other options are possible.

Few choices, not contiguous

Often implemented by compilers as an if-elseif ladder.

Profiling

The real proof is in setting compiler optimization switches and profiling.

The Assembly Listing

You may want to code up some switch statements and see how the compiler generates the assembly code. See which version generates the optimal assembly code for your situation.

If your set really consists of numbers in the range 0 to 63, use:

#define SET 0x.......ULL
if (num < 64U && (1ULL<<num & SET)) foo();
else bar();

Looking at your comparison functions, the second one is always faster because it is optimized to always execute the default statement. The default statement is execute "in order" as it appears in the switch, so in the second function it is immediately executed. It is very efficiently giving you the same answer for every switch! Default case must always appear as the last case in a switch. See http://www.tutorialspoint.com/cplusplus/cpp_switch_statement.htm for example, where it states "A switch statement can have an optional default case, which must appear at the end of the switch. The default case can be used for performing a task when none of the cases is true. No break is needed in the default case."

Here are the functions mentioned above

#define MAX 100000000
void compare_1(void)
{
   unsigned long i;
   unsigned long j;
   printf("%s\n", __FUNCTION__);
   for(i=0;i<MAX;i++)
   {
      j = rand()%100;
      switch(j)
      {
    case 1:
    case 2:
    case 3:
    case 4:
    case 6:
    case 7:
    case 8:
    case 10:
    case 11:
    case 15:
       break   ;
    default:
       break   ;
      }
   }
}


void unreg(void)
{
   int i;
   int j;
   printf("%s\n", __FUNCTION__);
   for(i=0;i<MAX;i++)
   {
      j = rand()%100;
      switch(j)
      {
    default:
       break   ;
    case 1:
    case 2:
    case 3:
    case 4:
    case 6:
    case 7:
    case 8:
    case 10:
    case 11:
    case 15:
       break   ;
      }
   }
}