Olivier Langlois's blog

Pipelined processors do not like conditional branches because when conditional branch is entering in the pipeline, the processor does not know yet what will be the condition outcome but it needs to continue to fill the pipeline with new instructions. In that situation the processor will try to predict what will be the condition outcome and start filling the pipeline from its prediction. This is very costly performance wise when the processor mispredicts the condition outcome. When that happens, the processor has to flush the pipeline content and start filling it again from the branch point.

The conditional branch prediction module has 2 components. There is the branch outcome cache that will help the processor to remember what was the outcome of branches that it has encountered recently and a static branch prediction algorithm.

The static branch algorithm is very simple:

• If the conditional branch goes further in the code, it will not be taken
• If the conditional branch goes back in the code, it will be taken

If you read the Intel processor optimization guide, few simple guidelines are easy to apply:

1. Eliminate branches

Some conditional branches are simply useless as whether they are taken or not, it will not make any differences on the end result. 2 examples of these are:

if( i != 0 )
  i = 0;

or

if( ptr != NULL )
{
  delete ptr;
  ptr = NULL;
}

should be changed to:

i = 0;

and

delete ptr;
ptr = NULL;

It is faster to reassign the same value to a variable than conditionally assign it. The operator delete and the function free() already contain safeguards against NULL pointers and it should be quite exceptional that they are called anyway with NULL pointers.

2. Refactor if statement conditions to be true most of the time.

Here is an example:

if(error)
{
  // exceptional error handling
}
else
{
  // normal operation
}

would be faster written like:

if(!error)
{
  // normal operation
}
else
{
  // exceptional error handling
}

To conclude, these guidelines are specifically for Intel processors but since the static branch prediction algorithm used by Intel processors is widely used by other pipelined processors (PowerPC is one of them), applying them on other platforms should be beneficial as well. Also, if you are looking for other optimization techniques, you can consult these sources.