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.

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

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$ – Peter Jan 21 '17 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 '17 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 '17 at 21:48
  • $\begingroup$ @quicksort: It would actually be a very rare situation. $\endgroup$ – gnasher729 Jan 22 '17 at 22:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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