A little warning in GMP.h

Karl Hasselström kha at treskal.com
Mon Sep 27 22:11:33 CEST 2004

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.

> 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.

> 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.

Karl Hasselström, kha at treskal.com

More information about the gmp-discuss mailing list