Return to Answer

An official answer would be from

1. Intel - Avoiding the Cost of Branch Misprediction
2. Intel - Branch and Loop Reorganization to Prevent Mispredicts
3. Scientific papers - branch prediction computer architecture
4. Books: J.L. Hennessy, D.A. Patterson: Computer architecture: a quantitative approach
5. 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.

An official answer would be from

1. Intel - Avoiding the Cost of Branch Misprediction
2. Intel - Branch and Loop Reorganization to Prevent Mispredicts
3. Scientific papers - branch prediction computer architecture
4. Books: J.L. Hennessy, D.A. Patterson: Computer architecture: a quantitative approach
5. Articles in scientific publications: 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 from strongly not taken to strongly taken.

An official answer would be from

1. Intel
2. Intel
3. Scientific papers
4. Books: J.L. Hennessy, D.A. Patterson: Computer architecture: a quantitative approach
5. 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.

An official answer would be from

1. Intel - Avoiding the Cost of Branch Misprediction
2. Intel - Branch and Loop Reorganization to Prevent Mispredicts
3. Scientific papers - branch prediction computer architecture
4. Books: J.L. Hennessy, D.A. Patterson: Computer architecture: a quantitative approach
5. 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.

An official answer would be from

1. Intel
2. Intel
3. Scientific papers
4. Books: J.L. Hennessy, D.A. Patterson: Computer architecture: a quantitative approach
5. 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.

An official answer would be from

1. Intel
2. Intel
3. Scientific papers
4. Books: J.L. Hennessy, D.A. Patterson: Computer architecture: a quantitative approach
5. 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.