A little warning in GMP.h

[Brian Hurt]

On Mon, 27 Sep 2004, Karl Hasselström wrote:

> On 2004-09-27 10:22:26 -0500, Brian Hurt wrote:
> 
> > On Mon, 27 Sep 2004, Brian Gladman wrote: So if, for example 90% of
> > the time __gmp_n is non-zero (for example), the total cost for the
> > branch is 0.9*predicted_cost + 0.1*mispredicted_cost. Assuming that
> > predicted_cost is 1 clock, and mispredicted_cost is 20 clocks, the
> > total cost of the branch at this point is 0.9 + 2 = 2.9 clocks.
> 
> This is probably accurate, since a 90% left/10% right split is likey
> to cause the branch predictor to guess "left" all the time, giving 90%
> correct predictions.

Actually, this is low.  They throw enough transistors at the problem 
nowadays that averaging 98%+ accurate branch prediction is standard.  At 
98% accurate, the branch costs 0.98 + (0.02*20) or 1.38 clocks.

> 
> > It's only if the branch is mispredicted often that it becomes a
> > problem- if __gmp_n is non-zero only 60% of the time, the cost is
> > then 0.6 + (0.4*20) = 8.6 clocks.
> 
> For a 60% left/40% right split, the branch predictor is unlikely to
> guess only "left" or only "right", so the actual misprediction ratio
> could be significantly different from 40%, depending on how the
> sequence of actual "left" and "right" branches interacts with the
> branch predictor heuristics.

Change the sentence to "if whatever heuristic the CPU is using is right 
60% of the time, then..."

> 
> > The worst case scenario is a 50% split- a completely unpredictable
> > branch. At this point, the branch takes 10.5 clocks on average.
> 
> This again assumes that the actual branches and the branch predictor's
> guesses are uncorrelated. The real figure might be significantly
> different -- for example, alternating "left" and "right" branches can
> be predicted with 100% accuracy by a very simple predictor.
> 

There are completely unpredictable branches:

    if ((rand() & 1) == 1) {
        ...

With any sort of decent random number generator, the branch will be taken 
half the time and not taken half the time, and the CPU will be very 
hard pressed to predict which it will be this time.

It's hard to get worse than 50/50 correctness on branch prediction- you 
basically have to be 'outthinking' the branch predictor.  Possible, but 
not likely even delibertly.  Which is why I went with it for my worst case 
scenario.

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian