[PATCH 0/5] branch hint tweaks

[PATCH 0/5] branch hint tweaks

[Tim Blechmann]

[-- Attachment #1: Type: text/plain, Size: 619 bytes --]

hi all,

doing some branch hint profiling of 2.6.31 on my nehalem machine showed
a few
incorrect branch hints.
these patches remove or change the branch hints

Tim Blechmann (5):
  process_64: remove branch hint
  sched.c: change branch hint
  slab.c: remove branch hint
  sched_fair.c: remove branch hint
  workqueue.c: remove branch hint

 arch/x86/kernel/process_64.c |    4 ++--
 kernel/sched.c               |    4 ++--
 kernel/sched_fair.c          |    2 +-
 kernel/workqueue.c           |    2 +-
 mm/slab.c                    |    2 +-
 5 files changed, 7 insertions(+), 7 deletions(-)



[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 197 bytes --]

Re: [PATCH 0/5] branch hint tweaks

[Brian Gerst]

On Tue, Nov 24, 2009 at 5:54 AM, Tim Blechmann <tim@klingt.org> wrote:
> hi all,
>
> doing some branch hint profiling of 2.6.31 on my nehalem machine showed
> a few
> incorrect branch hints.
> these patches remove or change the branch hints
>
> Tim Blechmann (5):
>  process_64: remove branch hint
>  sched.c: change branch hint
>  slab.c: remove branch hint
>  sched_fair.c: remove branch hint
>  workqueue.c: remove branch hint
>
>  arch/x86/kernel/process_64.c |    4 ++--
>  kernel/sched.c               |    4 ++--
>  kernel/sched_fair.c          |    2 +-
>  kernel/workqueue.c           |    2 +-
>  mm/slab.c                    |    2 +-
>  5 files changed, 7 insertions(+), 7 deletions(-)

Did you run profiling tests again after making these changes to see if
they had any effect?  likely() and unlikely() are only hints.  GCC
doesn't have to follow them, or it could be broken in recent GCC
versions.

I'm not sure what version of GCC added this, but I wonder if this
option will fix the problem:

-fno-guess-branch-probability
    Do not guess branch probabilities using heuristics.

    GCC will use heuristics to guess branch probabilities if they are
not provided by profiling feedback (-fprofile-arcs). These heuristics
are based on the control flow graph. If some branch probabilities are
specified by `__builtin_expect', then the heuristics will be used to
guess branch probabilities for the rest of the control flow graph,
taking the `__builtin_expect' info into account. The interactions
between the heuristics and `__builtin_expect' can be complex, and in
some cases, it may be useful to disable the heuristics so that the
effects of `__builtin_expect' are easier to understand.

    The default is -fguess-branch-probability at levels -O, -O2, -O3, -Os.

--
Brian Gerst

Re: [PATCH 0/5] branch hint tweaks

[Aaron Cohen]

On Tue, Nov 24, 2009 at 12:50 PM, Brian Gerst <brgerst@gmail.com> wrote:
> On Tue, Nov 24, 2009 at 5:54 AM, Tim Blechmann <tim@klingt.org> wrote:
>> hi all,
>>
>> doing some branch hint profiling of 2.6.31 on my nehalem machine showed
>> a few
>> incorrect branch hints.
>> these patches remove or change the branch hints
>
> I'm not sure what version of GCC added this, but I wonder if this
> option will fix the problem:
>
> -fno-guess-branch-probability
>    Do not guess branch probabilities using heuristics.
>
>    GCC will use heuristics to guess branch probabilities if they are
> not provided by profiling feedback (-fprofile-arcs). These heuristics
> are based on the control flow graph. If some branch probabilities are

Is the kernel's use of unlikely typically intended to mean "I consider
the following unlikely so please optimize with that expectation" or is
meant to indicate "the following is a slow-path so please pessimize
it" or both?

Re: [PATCH 0/5] branch hint tweaks

[Brian Gerst]

On Tue, Nov 24, 2009 at 1:17 PM, Aaron Cohen <remleduff@gmail.com> wrote:
> On Tue, Nov 24, 2009 at 12:50 PM, Brian Gerst <brgerst@gmail.com> wrote:
>> On Tue, Nov 24, 2009 at 5:54 AM, Tim Blechmann <tim@klingt.org> wrote:
>>> hi all,
>>>
>>> doing some branch hint profiling of 2.6.31 on my nehalem machine showed
>>> a few
>>> incorrect branch hints.
>>> these patches remove or change the branch hints
>>
>> I'm not sure what version of GCC added this, but I wonder if this
>> option will fix the problem:
>>
>> -fno-guess-branch-probability
>>    Do not guess branch probabilities using heuristics.
>>
>>    GCC will use heuristics to guess branch probabilities if they are
>> not provided by profiling feedback (-fprofile-arcs). These heuristics
>> are based on the control flow graph. If some branch probabilities are
>
> Is the kernel's use of unlikely typically intended to mean "I consider
> the following unlikely so please optimize with that expectation" or is
> meant to indicate "the following is a slow-path so please pessimize
> it" or both?
>

Both.  It is meant to optimize static branch prediction (on x86,
forward branches are by default predicted not taken), and to reduce
icache footprint of infrequently used code in the main execution path.
 If a section of code is marked unlikely(), GCC should put the code at
the end of the function.

--
Brian Gerst

Re: [PATCH 0/5] branch hint tweaks

[Tim Blechmann]

[-- Attachment #1: Type: text/plain, Size: 710 bytes --]

> Did you run profiling tests again after making these changes to see if
> they had any effect?  likely() and unlikely() are only hints.  GCC
> doesn't have to follow them, or it could be broken in recent GCC
> versions.

i know, the compiler doesn't have to follow the hint ... but with the
likely/unlikely profiling, not the execution time is profiled, but
whether the branch hint is pointing to the right direction on my machine
... if the assembly is actually affected does probably depend on the
compiler version, instruction set, cpu tuning ...

tim

-- 
tim@klingt.org
http://tim.klingt.org

The aim of education is the knowledge, not of facts, but of values
  William S. Burroughs


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 197 bytes --]

Re: [PATCH 0/5] branch hint tweaks

[Brian Gerst]

On Tue, Nov 24, 2009 at 1:21 PM, Tim Blechmann <tim@klingt.org> wrote:
>> Did you run profiling tests again after making these changes to see if
>> they had any effect?  likely() and unlikely() are only hints.  GCC
>> doesn't have to follow them, or it could be broken in recent GCC
>> versions.
>
> i know, the compiler doesn't have to follow the hint ... but with the
> likely/unlikely profiling, not the execution time is profiled, but
> whether the branch hint is pointing to the right direction on my machine
> ... if the assembly is actually affected does probably depend on the
> compiler version, instruction set, cpu tuning ...

The only branch "hint" in the final assembly output is whether a
branch points forward or backward.  unlikely() should tell GCC to put
the code at the end of the function, and use a forward branch to it.

Take for instance the code in arch/x86/kernel/process_64.c:

        savesegment(es, prev->es);
        if (unlikely(next->es | prev->es))
                loadsegment(es, next->es);

 5eb:   66 8c c1                mov    %es,%cx
 5ee:   66 89 48 30             mov    %cx,0x30(%rax)
 5f2:   66 83 bb a8 04 00 00    cmpw   $0x0,0x4a8(%rbx)
 5f9:   00
 5fa:   41 8b 8d a8 04 00 00    mov    0x4a8(%r13),%ecx
 601:   75 05                   jne    608 <__switch_to+0x86>
 603:   66 85 c9                test   %cx,%cx
 606:   74 04                   je     60c <__switch_to+0x8a>
 608:   31 f6                   xor    %esi,%esi
 60a:   8e c1                   mov    %ecx,%es

Both of those branches are forward, which will be statically predicted
as not taken.  Removing the unlikely() did not change the generated
code in this case with GCC 4.4.2.  So this patch does nothing for that
compiler version, but will lead to worse code on compilers that do
respect the hint.

Note that there is some weirdness in how the actual test is generated.
 It's not doing a bitwise-or operation like the C code describes.
This could be throwing off the optimizer.

--
Brian Gerst