Usage of unlikely in RCU code

[Adam Cozzette]

On Tue, Aug 02, 2011 at 11:03:58PM +0100, Julie Sullivan wrote:
> With
> 
> if (a && unlikely(b))
> 
> where a is false and b is false, the b will never be reached - so it
> really doesn't matter whether it's 'unlikely' or not.
> 
> However, where a is true, even if a is not 'unlikely', b must still be
> evaluated anyway to find the result. So I couldn't understand how the
> branch optimization would be effective.
> 
> if(unlikely(a) && b)
> 
> or
> 
> if(unlikely(a) && unlikely(b))
> 
> seems to make more sense (from a branch optimization point of view) if
> the result of if(...) is in doubt?

I think that C's short-circuit evaluation and the use of likely()/unlikely() for
branch prediction are for the most part orthogonal issues. We could rewrite the
statement

if (a && unlikely(b))

as

if (a) {
    if (unlikely(b)) {
        ...
    }
}

and we get the same result without using the boolean &&. So whenever a is true,
the CPU can improve its branch prediction because it has the knowledge that b is
probably not true.

As I understand it, branch prediction works like this: the CPU can have multiple
instructions executing in its pipeline because often it does not have to wait
for one instruction to finish before it can start working on another one. So
when it approaches a condition it has a problem: it doesn't know yet how the
condition will evaluate but it wants to be able to keep pushing new instructions
down the pipeline. So the processor just makes its best guess and keeps going.
When the condition finishes evaluating, the processor will find out if it
guessed correctly and if it needs to it can undo its changes and start over on
the correct branch. I'm not familiar with the underlying implementation of
unlikely() but I assume that it generates instructions which will somehow hint
to the processor which branch is the better guess. Guessing correctly is
important because it's expensive to have to undo a handful of instructions and
start over.

So I think all of this makes sense on a machine instruction level and is not
directly related to the order that ANDed conditions are evaluated. It seems to
me that there are two distinct questions here:

(1) How do I help the compiler/processor make the best branching predictions?
(2) How do I rearrange the conditions in a boolean expression in order to
evaluate as few conditions as possible?

My understanding is that likely() and unlikely() only answer the first question.
As for the second question, I think you may be right that it is generally best
to put the most unlikely condition first in a series of ANDed conditions. I
haven't been able to figure out why the RCU code you showed does not do that.

-- 
Adam Cozzette
Harvey Mudd College Class of 2012