Messages in this thread | | | From | nathan.zook@amd ... | Subject | RE: Kernel bugs found using inspect tool | Date | Wed, 23 Feb 2000 13:31:55 -0600 |
| |
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/
| |