Switch case optimization scenario

Question

Hi folks,

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 run, 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?

Answer 1

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

Answer 2

The order is uninportant if you use breaks.

The compiler just knows where to go.. I think there's an implicit convention to put the "default" at last (unless you want to do bizzarre thinks avoiding the break;'s)

Answer 3

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.

Answer 4

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

Answer 5

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();