Hi Manish, On Mon, Aug 1, 2011 at 4:45 PM, Manish Katiyar <mkatiyar@gmail.com> wrote:

...

C absolutely guarantees that the second will NEVER be evaluated before the first. Otherwise, things like this:

if ( ptr && ptr->field )

could fail if ptr was NULL.

In your example yes. But is there a problem if the two conditions are independent ? for eg..

The compiler doesn't care if the two conditions are independent or dependant.

foo() { ....  a = 0;  b = my_complex_function_call();  if (b && a) {      /* Do some non-trivial stuff */  } else {     printf("I'm an intelligent compiler\n");  } ..... }

Does C guarantee that even in this case it won't be reordered and not optimized ?

C guarantees that within the if ( b && a ) statement, a won't be evaluated if b evaluates to zero. If you coded if ( 0 && func() ) then func will NEVER be called. if you coded if ( func() && 0 ) then I think that func will always be called since it won't evaluate the 0 until after the left hand side of the && has been evaluated. I tried the following very simple example (compiled with -O3) #include <stdio.h> static inline int func() { printf( "func called\n" ); return 1; } int main( int argc, char **argv ) { if ( func() && 0 ) printf( "path1\n" ); else printf( "path2\n" ); return 0; } The compiler was smart enough to optimize out the printf( "path1\n" ) (i.e. running strings on the executable only showed path2), but it still calls func(). -- Dave Hylands Shuswap, BC, Canada http://www.davehylands.com

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

On Wed, Aug 3, 2011 at 7:37 AM, Mulyadi Santosa <mulyadi.santosa@gmail.com> wrote:

Dear Julie....

On Tue, Aug 2, 2011 at 04:28, Julie Sullivan <kernelmail.jms@gmail.com> wrote:

...

Specifically, the conditional

 if (t->rcu_read_lock_nesting == 0 &&            unlikely(ACCESS_ONCE(t->rcu_read_unlock_special)))                rcu_read_unlock_special(t);

I've googled for 'likely/unlikely' and i've seen

 if (unlikely(...

before in kernel code, and I might understand if the logical operator here were || not &&, but why is the 'unlikely' attribute only applied to the second operand here?

i guess that's because first condition "t->rcu_read_lock_nesting == 0" has about 50%-50% chance.... so putting likely() or unlikely() has no use here...

i read somewhere (or maybe someone's opinion) that you only use likely() or unlikely() if you are about above 90% (or maybe...if possible 99%) sure that condition will be true or false....otherwise, avoid likely()/unlikely() and let the compiler+processor do the usual ordering/branch prediction.

just my 2 cents...

-- regards,

Mulyadi Santosa Freelance Linux trainer and consultant

blog: the-hydra.blogspot.com training: mulyaditraining.blogspot.com

Thanks Mulyadi, maybe someday when I get round to performance testing I'll try this out for myself... Cheers Julie