lkml.org 
[lkml]   [2000]   [Feb]   [23]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
SubjectRE: Kernel bugs found using inspect tool
Date
The speed trade-off is directly related to the predictability of the
branch(es). A branch which goes rlrlrlrlrlrlrlr will, under most schemes in
use, be mispredicted either 50 or 100% of the time. rrllrrllrrllrrllrrll is
another really bad sequence.

A REALLY good optimizer might take the lazy-branch version of the code,
recognize that the later tests are side effect-free, and chose the version
is thinks is better. Problem is, such a compiler would likely be helpless
attempting to recognize an alternating branch point such as above.

Each mispredict will cost you several clocks, depending on the processor.

Each processor has its own prediction scheme.

Which gets us to a Dykstra quote, "Programming is, by definition, what you
have to tell the computer to do."


> From: Jamie Lokier [mailto:lk@tantalophile.demon.co.uk]

> ...

> The point is that an out-of-order processor (such as a modern x86)
> doesn't execute instructions in the order emitted by the C
> compiler. So
> in the above expression, it will typically fetch a, b, c, d, e and f,
> and execute all the comparisons in parallel.
>
> However, an out of order process will speculatively execute past
> branches, so that || version might be just as fast. And if the branch
> predictor is doing a good job, it might just be faster
> because you don't
> issue the unlikely instructions. But Nathan is from AMD so I'm sure
> he's right :-)

I'm right when I say "The rules have changed. Consider bit-logicals. Time
your critical inner loops". It all depends on the exact details of the code
& the processor. When c, d, e, and f are simple variables and the first two
branches are hard to predict, bit-ors should be faster on all the latest
superscalar systems.

Nathan Zook

-
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:56    [W:0.032 / U:0.292 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site