Likely/Unlikely and standards

[Richard G. Riley]

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

[jacob navia]

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.

[Tim Prince]

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.

[Richard G. Riley]

On 2006-02-24, Tim Prince <tp*****@nospamcomputer.org> 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

[Richard G. Riley]

On 2006-02-24, jacob navia <ja***@jacob.remcomp.fr> 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