# Static prediction of branch prediction

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.

• I can't understand your post at all. The first sentence, in particular has me completely lost. – 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.

• Oh, now it makes sense. I knew about pipeline, but didn't think about it at all. Thanks. – Peter Jan 21 '17 at 18:24
• 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. – gnasher729 Jan 21 '17 at 21:45
• @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. – quicksort Jan 21 '17 at 21:48
• @quicksort: It would actually be a very rare situation. – gnasher729 Jan 22 '17 at 22:47