EduardoS (no@spam.com) on 8/16/09 wrote:
>
>Very interesting data about branches, so 90% of all
>conditional branches goes always to the same path?

.. for a specific load!

The thing is, for some cases, branches always go the same
way. Imagine some load like gcc - and think about the fact
that gcc uses all the same back-end code for C and C++,
and how some issues will basically never happen for one or
the other.

So when you do something like a SpecInt run, and you run
the gcc tests, yes, a lot of branches will go only one way
for that run. But that does not mean that they go
only one way in general!

Under other loads, they might well be unpredictable, or
predict well, but go the other way entirely! It might be
a conditional branch that tests for a specific flag or
mode, and if you run it in that mode, it will obviously
always go just one way. But other people may well care
about the "other case", the one that never happened when
you did your benchmark run.

>Doing a good branch predictor isn't that hard so...

I'm sorry, but you're totally wrong.

Doing a good branch predictor is very very hard, and the
spec runs don't show any of it.

What makes good branch predictors hard is exactly the
fact that actual users do odd (and often stupid - but hey,
they care about their own loads) things. And they don't
just run one single benchmark that they first could warm
up the caches for. No, they run things cold-cache, and they
run tons of other things in between.

And they may share the same code (dynamically loaded shared
libraries, anyone?) with different users and different
applications that have totally different behavior, and that
thus have different branch prediction.

>Also look on how badly static predictors was.

Exactly. Static prediction sucks. You can improve it by
doing PGO, but I suspect that paper had essentially already
done that (ie the "static prediction" was to predict a
particular branch as well as you could from the trace, but
always predict it one way).

And it sucks exactly because circumstances change. But that
is also why dynamic prediction is never easy. You not only
have cold-cache cases, but let's say that your branch
prediction table is 4k entries in size - now think about
how many branches you are actually going to predict when
that system is busy with anything serious that actually has
IO delays etc.

Why do IO delays matter? They matter because they affect
the working set enormously. If you run something like Spec,
where you run only one program at a time, and where you
have warm caches, then your working set is literally just
that single program.

Now think about usage on real high-end machines, and ask
yourself if they ever run a single program. They
generally don't. Even if it's technically a single program
(like a single database), it's going to have lots of threads
and run all those different parts of the same program at
once.

Do you think those 4k branch prediction entries are going
to capture all those conditional branches? Really? Or do
you think that maybe you have to just realize that your
predictor is going to miss a whole lot more on real loads
than you'll miss on something controlled like a specint run?

In other words: the branch prediction numbers from specint
should be considered absolutely "best possible case". Not
"oh, I could improve on that in an afternoon".

Linus