lkml.org 
[lkml]   [1999]   [May]   [21]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: schedule() "spaghetti" in 2.3.2 ..
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/

\
 
 \ /
  Last update: 2005-03-22 13:51    [W:0.074 / U:2.136 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site