Likely/Unlikely and standards

Discussion in 'C Programming' started by Richard G. Riley, Feb 24, 2006.

  1. 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
     
    Richard G. Riley, Feb 24, 2006
    #1
    1. Advertising

  2. Richard G. Riley

    jacob navia Guest

    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.
     
    jacob navia, Feb 24, 2006
    #2
    1. Advertising

  3. Richard G. Riley

    Tim Prince Guest

    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.
     
    Tim Prince, Feb 24, 2006
    #3
  4. On 2006-02-24, Tim Prince <> 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, Feb 24, 2006
    #4
  5. On 2006-02-24, jacob navia <> 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
     
    Richard G. Riley, Feb 24, 2006
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Tzury Bar Yochay
    Replies:
    3
    Views:
    498
    Jacob Yang [MSFT]
    Nov 29, 2003
  2. Ken Guest
    Replies:
    2
    Views:
    295
    Ken Guest
    Jan 6, 2006
  3. Kenneth McDonald
    Replies:
    3
    Views:
    295
    Paul Boddie
    Sep 7, 2007
  4. Ferenczi Viktor
    Replies:
    12
    Views:
    365
    Fernando Perez
    Sep 9, 2007
  5. Nitin Tripathi

    when should one go for likely and unlikely

    Nitin Tripathi, Sep 10, 2013, in forum: C Programming
    Replies:
    3
    Views:
    188
    Keith Thompson
    Sep 11, 2013
Loading...

Share This Page