handmade.network » Wiki » Branch Prediction

Branch prediction is a technique employed by modern processors to speculatively guess if a conditional branch will be taken or not, allowing for speed up.

Modern processors run instructions out-of-order. This means it's useful to know which instructions are going to be executed after a branch, even if the values that determine the condition haven't been calculated yet.

Example:

1
2
3
4
5
6
loop:
mov eax,[esi]
mov [esi-1],esi
inc esi ; Increment esi
cmp esi,ebx
jne loop ; Does esi=ebx? If so, don't take the branch and stop.

A modern processor would be able to execute this code much faster if they knew that the jne loop branch is almost always taken. And therefore it'll notice the pattern in which the branch is being taken, and use that to predict where the branch will go subsequent times.

Branch predictors in modern processors are quite clever. They should at least be able to pick up something like a for loop.

If the branch is incorrectly predicted - a branch misprediction - then the processor will have to "undo" the speculative execution that it did under the assumption it was correct about the branch. This can be quite time costly. In a binary search, for example, there will be a lot of branch mispredictions because there is no way for the processor to judge which way the branch will go. In theory this might make it slower than linear search for small lists - but you should always benchmark to make sure.