how to suggest gcc compiler more probable branch

Question

Example:

if (almost_always_false_condition) {
       // do something
}

Is there a way to suggest compiler that in 99% condition will be false. The condition calculation takes ~60 cycles to be checked, and it cannot be calculated at compile time by compiler itself.

(gcc 4.3)

Answer 1

If you want to suggest to GCC that a condition is likely to have a given value as a hint for arranging code flow, you should use __builtin_expect( ):

if (__builtin_expect(almost_always_false_condition,0)) {
   // do something
}

However, it sounds like you want to find a way to avoid evaluating the condition, which __builtin_expect( ) won't do. Is there a way that you can quickly approximate the condition, and only do the full check when the approximation is true:

if (__builtin_expect(fastCheckThatIsTrueIfFullConditionIsTrue,0)) {
    // most of the time, we don't even get to here, so you don't need
    // to evaluate the condition
    if (almostAlwaysFalseCondition) {
        // do something
    }
}

Can you tell us more about what the condition is?

Answer 2

If the result might vary during a single run, you may be able to use lazy evaluation of boolean operators to split your condition into a cheap part and an expensive part, and run the cheap part first.

if (a == 5 && somethingexpensive())
{
   ...
}

Since calculating a == 5 is cheaper than somethingexpensive(), and if it is almost always false you should run it first, which avoids evaluating the somethingexpensive clause.

If on the other hand the result is constant for a run of the program, you can optimise it by storing the result of the calculation in a static or global variable.

static int result = doevalfunctiononlyonce();

if (result)
{
   ....    
}

This way you have reduced the cost of the if to a simple memory lookup.

If the condition only changes in response to an action in another procedure, you can update the global from that procedure:

int condition;

void appendToList(int a)
{
   list.append(a);
   if (list.somethingexpensive())
   {
     condition = true;
   } else
   {
     condition = false;
   }
}

void someotherfunction()
{
  // if (list.somethingexpensive())
  if (condition)
  {
    ...
  }
}

This is useful if someotherfunction is called lots more often than the appendtolist function.

Answer 3

First of all, how many cycles are spent in the else clause, or elsewhere in the program? If you profile or take stackshots, are you spending at least 10% of your time in that test? If not, there probably are bigger problems you should look at first.

Second, if you are spending >10% of time in that test, you should look to see if the algorithm can be adjusted to have decision points closer to 50-50 probability. A 50-50 decision point yields 1 bit of information when it is executed, while a 99-1 decision point only yields about .07 bits.* (i.e. it doesn't tell you much, so it is inefficient use of CPU cycles.) An example of this phenomenon is if you compare linear search with binary search.

*If you have a binary decision point and the probabilities of the outcomes are a and b, the information yield (entropy) in bits is -(a*log(a) + b*log(b))/log(2).