1
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ I can't understand your post at all. The first sentence, in particular has me completely lost. $\endgroup$ Jan 21, 2017 at 19:00

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Oh, now it makes sense. I knew about pipeline, but didn't think about it at all. Thanks. $\endgroup$
    – Peter
    Jan 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$
    – gnasher729
    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 for loop to clarify what I mean. $\endgroup$
    – quicksort
    Jan 21, 2017 at 21:48
  • $\begingroup$ @quicksort: It would actually be a very rare situation. $\endgroup$
    – gnasher729
    Jan 22, 2017 at 22:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.