Re: schedule() "spaghetti" in 2.3.2 ..

Andi Kleen (ak@muc.de)
Tue, 18 May 1999 22:14:40 +0200

On Tue, May 18, 1999 at 01:12:19PM +0200, Pavel Machek wrote:
> Hi!
>
> > > why not move code blocks in macros ( like that in mm module ) or better in
> > > inline functions.
> >
> > That would not have the intended effect - to keep jumps out of the
> > fast path.
> >
> > Normally gcc codes a normal if like that (pseudo, m68k like assembly)
> >
> > if (x < 0) {
> > /* error */
> > }
> > /* rest of fast path */
> >
> > tst x
> > bgr L1 /* jump taken in most cases */
> > /* error */
> > L1:
> > /* rest of fast path */
> >
> > this means there is a jump in the fast path (on modern CPUs that can be
> > quite costly because of the pipeline stall when the jump is mispredicted).
> > It is usually faster to have code like this:
>
> What about heuristic which says
>
> if (...) {
> ...
> return;
> }
>
> should be moved out of line?

Breaks cases like

f() {
if (common_case) {
/* handle common case quickly */
return;
}
slow path

critical examples for that is tcp_input.c:tcp_data_queue or parts of
the page fault path in mm/memory.c. You really either need user hints or
profile feedback.

Given some data there are good algorithms in the literature to get a near
perfect jump-less path for the fast paths.

It is definitely worthwhile, for example the Alpha architecture manual makes
it quite clear that even if the probability of a branch being take or not
is only 51:49 moving the less frequent case out-of-line is a win. This is most likely
true for other modern architectures too.

I'm sure which a working __builtin_expect in the kernel that moves blocks
hundreds of gotos could be eliminated from the kernel source :)

-Andi

-- 
This is like TV. I don't like TV.


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/