optimization suprise

[hgm]

Yes, if everything was truly unpredictable. But as it turns out, these branch predictors nowadays are truly amazing, and get 95% hit rates on branches you would think should be truly random.

[bob]

Yes, but it seems since Pentium M they have implemented something for this. If I understood it correctly, they always predict the branch as taken, but they take the speculative target from the Branch Target Buffer indexed by the global branch predictor (the packed taken/not-taken bits of the last 12 branches).

So if the target address correlates in any way with the code flow just before the indirect jump, it can make a prediction about the target address. Seems to be only 75% efficient, though, while normal branches are typically predicted with 95-97% accuracy.

Correct, but the failing (if you want to call it that) is that using the global history is not a good indicator for which target a branch goes to, which is why it does poorly... I tried the array of functions to see how it would do, but the answer was bad compared to what I do presently in movgen...

[bob]

Yes, if everything was truly unpredictable. But as it turns out, these branch predictors nowadays are truly amazing, and get 95% hit rates on branches you would think should be truly random.

tournament predictors, first introduced in the dec alpha, are truly remarkable in their accuracy, and are able to have correlated and non-correlated branches extremely well...