anon (anon@anon.com) on 8/16/09 wrote:
>
>I saw this post referenced here once before when this came
>up. Not too scientific but it shows that even on x86 CPUs
>that predication is a win if the branch is not predictable.
>(and also shows it a loss when the branch is predictable)
>
>http://gcc.gnu.org/ml/gcc/2008-02/msg00601.html
>
>Whether this is true and how pronounced the effects are on
>real programs, I don't know.

The above is a great example, especially because it has
that "no dependencies" vs "has dependencies" case, and
thus really shows the effect of the branch predictor in
actually lowering the dependency chain.

At the same time, it's a bad example, because 'cmov' is
such a special case of predication (very targeted) and
doesn't really allow for any complex predication.

Without any dependencies, the predicated version is faster
even when things are predictable - because there is no
dependency chain to be broken, so the fact that you have
to wait for the predicate to be computed doesn't hurt. As
a result, the big win from branch prediction just doesn't
ever appear.

And the unpredictable case obviously shows all the downsides
of branch prediction. When you mispredict, you lose, and you
often lose big. Which is why you want your branch predictors
to be 99%+ accurate.

Of course, at the same time, this is also going to be very
sensitive to microarchitectural issues. Predication is
generally more expensive on x86 than it would be on IA64:
it's not generally what the microarchitecture is optimized
for. The fairly complex x86 eflags result is often computed
one cycle late, so eflags latency tends to be two cycles.

At the same time, the advantages of predication are bigger
on ia64, since you need to always pack the instructions
well, and with branchy code with long dependency chains
you'd often otherwise have instruction packing problems.
In contrast, in an OoO x86, instruction scheduling being
dynamic doesn't have any of these issues, and there the
fact that branch prediction dynamically breaks the data
dependencies can be a big advantage.

So the fact that predication can be a loss (even on this
trivial example) on x86 does not translate to it being a
loss in general. On ia64, I suspect the predicated version
of this trivial program would always win.

So microarchitectural choices matter a lot. 'cmov' was
pretty bad on a P4, for example, and had some silly latency
of five cycles or something.

Linus

PS, just for fun, I ran that thing on Nehalem. End result:
it looks like Intel has improved both cmov and branch
misprediction to the point where there remains a noticeable
difference in just one case.

 no deps,   predictable -- C    code took   1.76ns per iteration

 no deps,   predictable -- cmov code took   1.76ns per iteration

 no deps,   predictable -- jmp  code took   1.73ns per iteration

has deps,   predictable -- C    code took   2.16ns per iteration

has deps,   predictable -- cmov code took   2.25ns per iteration

has deps,   predictable -- jmp  code took   2.01ns per iteration

 no deps, unpredictable -- C    code took   1.75ns per iteration

 no deps, unpredictable -- cmov code took   1.76ns per iteration

 no deps, unpredictable -- jmp  code took   5.19ns per iteration

has deps, unpredictable -- C    code took  13.31ns per iteration

has deps, unpredictable -- cmov code took  14.01ns per iteration

has deps, unpredictable -- jmp  code took  13.33ns per iteration