Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Likely/Unlikely and standards

Reply
Thread Tools

Likely/Unlikely and standards

 
 
Richard G. Riley
Guest
Posts: n/a
 
      02-24-2006

Gnu C has a feature for optimised branching using likely() and
unlikely() for branch conditions

e.g

if(likely(f)){
...

or

if(unlikely()){

(you pick your check function based on knowledge of likely behaviour)


Does anyone one know of any thing specific to the C language standards
which enables one to approximate these functions for the "more
general" case e.g remain standard compliant and platform independant?

Any hints or tips on optimised conditional branching would be appreciated.

(I could DEFINE them as returning f but thats not what I'm after)

--
Remove evomer to reply
 
Reply With Quote
 
 
 
 
jacob navia
Guest
Posts: n/a
 
      02-24-2006
Richard G. Riley a écrit :
> Gnu C has a feature for optimised branching using likely() and
> unlikely() for branch conditions
>
> e.g
>
> if(likely(f)){
> ...
>
> or
>
> if(unlikely()){
>
> (you pick your check function based on knowledge of likely behaviour)
>
>
> Does anyone one know of any thing specific to the C language standards
> which enables one to approximate these functions for the "more
> general" case e.g remain standard compliant and platform independant?
>
> Any hints or tips on optimised conditional branching would be appreciated.
>
> (I could DEFINE them as returning f but thats not what I'm after)
>


This is a similar case to the subtypes problem.

Sub types are a specialization of some standard type, like
const char *p;

"const" is a subtype of "char *", the char pointer type is annotated
(i.e. specialized) with some attribute that tells the compiler
something, in that case that it can't be changed.

Your problem could be understood as the same if we do:

bool condition = (f > 23 && f < 56);

if (condition) {
// some code
}
else {
// some another code
}

You would like to say:

bool likely condition = (f > 23 && f < 56);

or
bool unlikely condition = (f > 23 && f < 56);

This is a general problem that has never been addressed in the
language but have been solved by different compilers each time in
an ad-hoc, specialized way.

We have for instance the way Microsoft does it:

__declspec(naked)
__declspec(dllimport)
__declspec(align 16)
etc

The way GNU does it is with their
__attribute__ (nonnull)
__attribute_pure
etc.

You would like to add two attributes to the "bool" type: likely and
unlikely, that would tell the compiler that a boolean value should
be preferred/not preferred in the context of a conditional expression.

Recently Microsoft proposed a standard syntax for annotating types.

I quote from http://msdn2.microsoft.com/en-us/library/ms235402.aspx:
<<<
If you examine the library header files, you will notice some unusual
annotations such as __in_z and __out_ecount_part. These are examples of
Microsoft's standard source code annotation language (SAL), which
provides a set of annotations to describe how a function uses its
parameters—the assumptions it makes about them, and the guarantees it
makes upon finishing. The header file <sal.h> defines the annotations.

Annotations may be placed before either a function parameter's type or
its return type, and describe the function's behavior regarding the
parameter or return value. There are two classes of annotations: buffer
annotations and advanced annotations. Buffer annotations describe how
functions use their pointer parameters, and advanced annotations either
describe complex/unusual buffer behavior, or provide additional
information about a parameter that is not otherwise expressible.
where they annotate function attributes
>>>


In your case you would propose a new annotation stating the which branch
to prefer in a conditional.

Until now, no standard solution exists, but the problem is so pervasive
in C (and C++ too by the way) that a standard solution would be really a
bonus for the language.
 
Reply With Quote
 
 
 
 
Tim Prince
Guest
Posts: n/a
 
      02-24-2006
Richard G. Riley wrote:
> Gnu C has a feature for optimised branching using likely() and
> unlikely() for branch conditions
>
> e.g
>
> if(likely(f)){
> ...
>
> or
>
> if(unlikely()){
>
> (you pick your check function based on knowledge of likely behaviour)
>
>
> Does anyone one know of any thing specific to the C language standards
> which enables one to approximate these functions for the "more
> general" case e.g remain standard compliant and platform independant?
>
> Any hints or tips on optimised conditional branching would be appreciated.

Some will say this subject should be left entirely to forums dedicated
to particular compilers or platforms, but there are a few generalizations.

Default optimization for conditional branch not taken is a de facto
standard. Thus, the if() block would be favored over the else. Where
there is a conditional loop exit, the branch which leads to continued
iteration should be favored, as many compilers do.
There should be no performance penalty for the use of a break, except
that it is preferable to use an if() block rather than break, in the
case where the last part of a loop body is to be skipped on the last
loop iteration.
Example:
for(i=0;i<n;++i){
...
if(i < n-1){ // this should be recognized as a "likely" block
...
}
}
That scheme often performs better than 2 separate loops with slightly
different count.
Making an empty if() block, in order to put the unlikely block in the
else, is a bit ugly, but no more so than use of non-standard hints. I
have waged a several year campaign against compilers requiring break to
be placed in an else block to enable optimization. That is more than a
bit ugly. Disliked example:
for(;{...;if(!exit_condition);else break;} // break is "unlikely"

Compilers may over-ride the if() block preference, if that results in
more compact code.
Current architectures have branch history buffers, so that branch
hinting is not so important inside loops with a large trip count.
It is worth while to organize code so as to encourage a compiler to use
conditional moves (e.g. ? operator), rather than branching over a simple
assignment. gcc-4.2 does a particularly good job there.
Otherwise, unrolling a loop which contains branches, will accommodate
more complex execution patterns, at the expense of hogging branch
history table entries. Some compilers suppress automatic unrolling of
such loops.
 
Reply With Quote
 
Richard G. Riley
Guest
Posts: n/a
 
      02-24-2006
On 2006-02-24, Tim Prince <(E-Mail Removed)> wrote:
> Richard G. Riley wrote:
>> Gnu C has a feature for optimised branching using likely() and
>> unlikely() for branch conditions
>>
>> e.g
>>
>> if(likely(f)){
>> ...
>>
>> or
>>
>> if(unlikely()){
>>
>> (you pick your check function based on knowledge of likely behaviour)
>>
>>
>> Does anyone one know of any thing specific to the C language standards
>> which enables one to approximate these functions for the "more
>> general" case e.g remain standard compliant and platform independant?
>>
>> Any hints or tips on optimised conditional branching would be appreciated.

> Some will say this subject should be left entirely to forums dedicated
> to particular compilers or platforms, but there are a few generalizations.
>


Some undoubtedly would .. However I´m really looking for some
standard C techniques for achieving the same end result as the
compiler specifics so well covered in a previous post. Which you
address nicely below : thanks.

> Default optimization for conditional branch not taken is a de facto
> standard. Thus, the if() block would be favored over the else. Where
> there is a conditional loop exit, the branch which leads to continued
> iteration should be favored, as many compilers do.
> There should be no performance penalty for the use of a break, except
> that it is preferable to use an if() block rather than break, in the
> case where the last part of a loop body is to be skipped on the last
> loop iteration.
> Example:
> for(i=0;i<n;++i){
> ...
> if(i < n-1){ // this should be recognized as a "likely" block
> ...
> }
> }
> That scheme often performs better than 2 separate loops with slightly
> different count.
> Making an empty if() block, in order to put the unlikely block in the
> else, is a bit ugly, but no more so than use of non-standard hints. I
> have waged a several year campaign against compilers requiring break to
> be placed in an else block to enable optimization. That is more than a
> bit ugly. Disliked example:
> for(;{...;if(!exit_condition);else break;} // break is "unlikely"
>
> Compilers may over-ride the if() block preference, if that results in
> more compact code.
> Current architectures have branch history buffers, so that branch
> hinting is not so important inside loops with a large trip count.
> It is worth while to organize code so as to encourage a compiler to use
> conditional moves (e.g. ? operator), rather than branching over a simple
> assignment. gcc-4.2 does a particularly good job there.
> Otherwise, unrolling a loop which contains branches, will accommodate
> more complex execution patterns, at the expense of hogging branch


I have frequently unrolled loops to HW word size data having
ascertained the endian characteristics of the underlying HW
programmatically in the initialisation stages of a "performance"
program. e.g the example that came up a few days ago with the chap
trying to clear memory by writing byte at a time to the video HW.

> history table entries. Some compilers suppress automatic unrolling of
> such loops.


Thanks again : some food for thought.

--
Remove evomer to reply
 
Reply With Quote
 
Richard G. Riley
Guest
Posts: n/a
 
      02-24-2006
On 2006-02-24, jacob navia <(E-Mail Removed)> wrote:
>
> This is a similar case to the subtypes problem.
>
> Sub types are a specialization of some standard type, like
> const char *p;
>
> "const" is a subtype of "char *", the char pointer type is annotated
> (i.e. specialized) with some attribute that tells the compiler
> something, in that case that it can't be changed.
>
> Your problem could be understood as the same if we do:
>
> bool condition = (f > 23 && f < 56);
>
> if (condition) {
> // some code
> }
> else {
> // some another code
> }
>
> You would like to say:
>
> bool likely condition = (f > 23 && f < 56);
>
> or
> bool unlikely condition = (f > 23 && f < 56);
>
> This is a general problem that has never been addressed in the
> language but have been solved by different compilers each time in
> an ad-hoc, specialized way.
>
> We have for instance the way Microsoft does it:
>
> __declspec(naked)
> __declspec(dllimport)
> __declspec(align 16)
> etc
>
> The way GNU does it is with their
> __attribute__ (nonnull)
> __attribute_pure
> etc.
>
> You would like to add two attributes to the "bool" type: likely and
> unlikely, that would tell the compiler that a boolean value should
> be preferred/not preferred in the context of a conditional expression.
>
> Recently Microsoft proposed a standard syntax for annotating types.
>
> I quote from http://msdn2.microsoft.com/en-us/library/ms235402.aspx:
><<<
> If you examine the library header files, you will notice some unusual
> annotations such as __in_z and __out_ecount_part. These are examples of
> Microsoft's standard source code annotation language (SAL), which
> provides a set of annotations to describe how a function uses its
> parameters—the assumptions it makes about them, and the guarantees it
> makes upon finishing. The header file <sal.h> defines the annotations.
>
> Annotations may be placed before either a function parameter's type or
> its return type, and describe the function's behavior regarding the
> parameter or return value. There are two classes of annotations: buffer
> annotations and advanced annotations. Buffer annotations describe how
> functions use their pointer parameters, and advanced annotations either
> describe complex/unusual buffer behavior, or provide additional
> information about a parameter that is not otherwise expressible.
> where they annotate function attributes
> >>>

>
> In your case you would propose a new annotation stating the which branch
> to prefer in a conditional.
>
> Until now, no standard solution exists, but the problem is so pervasive
> in C (and C++ too by the way) that a standard solution would be really a
> bonus for the language.


Thanks for the detailed reply : most helpful.

--
Remove evomer to reply
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
ASP.NET v1.1, Validator Controls, Web Standards and Valid (X)HTML danny.rendle@rokstudent.com ASP .Net 3 12-14-2005 04:46 PM
Web Clients, the role of ASP.NET and the Future of Web Development and Web Standards Guadala Harry ASP .Net 9 11-06-2004 03:05 AM
Evolving Web App Standards and ASP.NET =?Utf-8?B?bWtsYXBw?= ASP .Net 4 07-20-2004 07:52 AM
asp.net and Web Accessibility Standards Paul G ASP .Net 1 02-26-2004 10:26 PM
Ordered lists and standards-compliant code Jim Royal HTML 3 09-16-2003 01:51 PM



Advertisments