Branch optimization by reordering

Question

I have a C function called a million times:

void foo ()
{
    if (/*condition*/)
    {

    }
    else if(/*another_condition*/)
    {

    }
    else if (/*another_condition_2*/)
    {

    } 
          /*And so on, I have 4 of them, but we can generalize it*/
    else
    {

    }
 }

I have a good test script that calls this function, as a result of which certain if-branches are called more than others.

My goal is to determine the best way to arrange if statements to minimize branching .

The only way I can think of is to write to a file for each condition with a branching condition, thereby creating a histogram. It seems tedious. Is there a better way, better tools?

I create it on AS3 Linux using gcc 3.4; using oprofile (opcontrol) for profiling.

Answer 1

, GCC __builtin_expect(), , , :

if(__builtin_expect(condition, 0)) {
  // We expect condition to be false (0), so we're less likely to get here
} else {
  // We expect to get here more often, so GCC produces better code
}

Linux , , ( , GCC):

#ifdef __GNUC__
#  define likely(x)   __builtin_expect((x), 1)
#  define unlikely(x) __builtin_expect((x), 0)
#else
#  define likely(x)   (x)
#  define unlikely(x) (x)
#endif

:

if(unlikely(condition)) {
  // we're less likely to get here
} else {
  // we expect to get here more often
}

, , , , / , .

Answer 2

(gprof?) - , . , gprof , , .

Answer 3

Callgrind . , , , . if/else if/else, ( , , ) 0, (, , ) .

Answer 4

, , . , .

, -, ... , , if, , .

.. ( , AFAIK). , 1 , 0, . , , 1 0 .

, , . , , , , , ... .

Answer 5

:

// pseudocode
class ProfileNode
{
public:
   inline ProfileNode( const char * name ) : m_name(name)
   {  }
   inline ~ProfileNode()
   {
      s_ProfileDict.Find(name).Value() += 1; // as if Value returns a nonconst ref
   }

   static DictionaryOfNodesByName_t  s_ProfileDict;
   const char * m_name; 
}

void foo ()
{
    if (/*condition*/)
    {
       ProfileNode("Condition A");
       // ...
    }
    else if(/*another_condition*/)
    {
       ProfileNode("Condition B");
       // ...
    } // etc..
    else
    {
       ProfileNode("Condition C");
       // ...
    }
 }

void dumpinfo()
{
  ProfileNode::s_ProfileDict.PrintEverything();
}

, , .

Answer 6

. , , , .

static int cond_1, cond_2, cond_3, ...

void foo (){
    if (condition){
      cond_1 ++;
      ...
    }
    else if(/*another_condition*/){
      cond_2 ++;
      ...
    }
    else if (/*another_condtion*/){
      cond_3 ++;
      ...
    } 
    else{
      cond_N ++;
      ...
    }
 }

EDIT: "" :

void cond_print(void) __attribute__((destructor));

void cond_print(void){
  printf( "cond_1: %6i\n", cond_1 );
  printf( "cond_2: %6i\n", cond_2 );
  printf( "cond_3: %6i\n", cond_3 );
  printf( "cond_4: %6i\n", cond_4 );
}

, , foo().

Answer 7

, , .

Answer 8

, .

- LLVM, .

Answer 9

, .

: , ?

, , , .

, , , , , , , false. , , , , if, , , false true. false, , , .