If we have a static implementation of branch prediction and we always fetch the next sequential instruction isn't inefficient to do that if we, at a future point verify if the prediction was correctly done? We just evaluate the branch in future... Why don't we just simply verify this thing every time we encounter a branch and not just execute what we think it's correct? I see here a delay because we double check the incorrect situations. 10 predictions, 4 wrong => 14 evaluations instead of 10. I know I'm wrong but I can't figure it why.
1
-
3$\begingroup$ I can't understand your post at all. The first sentence, in particular has me completely lost. $\endgroup$– David RicherbyJan 21, 2017 at 19:00
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
You are missing a fundamental detail: modern processors are pipelined. What it means in a nutshell is that instruction $I_{n+1}$ is fetched from memory and begins being processed way before instruction $I_n$ has been executed completely. But if $I_n$ is a conditional branch, we have no way to know for sure whether or not the jump will happen: we would have to stop fetching instructions until we finish evaluating $I_n$.
Branch prediction doesn't come from theory but from a strictly practical observation: it is better to be sometimes wrong, but decide quickly than to be always correct but slowly.
A classical example is the following:
for (i <-- 0 to 1,000,000) do {
...
}
If we just take the "loop continues" branch every time, we will be wrong once but correct the other $999,999$ times, yielding a better average running time in practice.
-
$\begingroup$ Oh, now it makes sense. I knew about pipeline, but didn't think about it at all. Thanks. $\endgroup$– PeterJan 21, 2017 at 18:24
-
$\begingroup$ Depending on the code, there may be more than one branch mispredicted. Start with a floating point number x = 1,000,000, then divide by 1.001 until the result is less than 1. Each division takes easily 20 cycles. If the rest of the loop runs fast, there can be a few mispredicted branches. It's still faster that way than to wait. $\endgroup$ Jan 21, 2017 at 21:45
-
$\begingroup$ @gnasher729 Yeah, I was a little sloppy there, thanks for pointing out. I meant it a simple example, maybe I should change it to a
forloop to clarify what I mean. $\endgroup$ Jan 21, 2017 at 21:48 -
$\begingroup$ @quicksort: It would actually be a very rare situation. $\endgroup$ Jan 22, 2017 at 22:47