Skip to contentSkip to conversation

branch hint tweaks

PATCH In review Tim Blechmann 3 participants 6 messages Nov 24, 2009

lore
Share & tools
lore
#0 lore raw

cover branch hint tweaks

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(-)
#1 lore raw
Quoted 14 lines · Tim Blechmann

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

Quoted 6 lines

 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

#2 lore raw
Quoted 11 lines · Brian Gerst
Quoted 6 lines · Tim Blechmann

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:

Quoted 6 lines

-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?

#3 lore raw
Quoted 15 lines · Aaron Cohen
Quoted 14 lines · Brian Gerst
Quoted 6 lines · Tim Blechmann

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.

Quoted 9 lines
Quoted 3 lines

   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

#4 lore raw
In reply to Brian Gerst
Quoted 4 lines

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

Signature · 5 lines
[email protected]
http://tim.klingt.org

The aim of education is the knowledge, not of facts, but of values
  William S. Burroughs
#5 lore raw
Quoted 10 lines · Tim Blechmann
Quoted 4 lines

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