An official answer would be from
- Intel
- Intel
- Scientific papers
- Books: J.L. Hennessy, D.A. Patterson: Computer architecture: a quantitative approach
- Articles in scientific puplications: T.Y. Yeh, Y.N. Patt made a lot of these on branch predictions.
You can also see from this lovely diagram why the branch predictor gets confused.
Each element in the original code is a random value
data[c] = std::rand() % 256;
so the predictor will change sides as the std::rand()
blow.
On the other hand, once it's sorted, the predictor will first move into a state of strongly not taken and when the values change to the high value the predictor will in three runs through change all the way fron strongly not taken to strongly taken.