Does 2-bit prediction always better than 1-bit? And from wikipedia, how ‘a loop-closing conditional jump is mispredicted once rather than twice.’ with 2-bit prediction?
According to this answer, 2-bit prediction will have 1 misprediction if with always taken.Then according to this one (see context of 'first and last loop iterations' in this link), 1-bit will also have 1 misprediction which is same as 2-bit prediction if with always taken?
Better if one concrete example with some explanation.
Does 2-bit prediction always better than 1-bit?
We can construct a pathological case for either predictor, and they are not the same case, thus one will be better than the other in some case.
The pathological case for the 1-bit predictor is simple alternation, TNTNTNTNT... The 1-bit predictor will mispredict all branches (save perhaps the first) — whereas the 2-bit predictor will predict some of these correctly, an improvement over no correct predictions.
The pathological case for the 2-bit predictor is double alternation, TTNNTTNNTTNN... The 2-bit predictor mispredict all branches (save perhaps the first) — whereas the 1-bit predictor will predict some of these correctly — again, an improvement over no correct predictions.
How do we construct such cases? Using if-then-else inside a larger loop, where the branch of interest we focus on is the one deciding the then vs. else case, and with a data set / workload that involves this alternation.
(If that construct is itself in an outer loop, then save for the first execution of the inner loop, the if-then-else will have some initial history.)
According to this answer, 2-bit prediction will have 1 misprediction if with always taken.
That answer glosses over the first potential mispredict from the first execution of the inner loop inside the first iteration of the outer loop. It rather (reasonably correctly) points out that the second and beyond iteration of the inner loop (inside the outer loop), there is history to predict the branch taken, so there should be no question of a miss on the first iteration of the inner loop (in the second and beyond iteration of the outer loop).
(That answer also transforms both loops from for-loop to do-while-loop — which don't have the same semantics in the general case, though this is a valid to do because the loops are counted and we know by the counts they will each iterate at least once (this transformation is an efficiency improvement — there are other such transformations for the more general case that involve initially jumping to an exit condition at the end, or, repeating the exit condition test outside the loop followed by the do-while form)).
Then according to this one (see context of 'first and last loop iterations' in this link), 1-bit will also have 1 misprediction which is same as 2-bit prediction if with always taken?
The first + last adds up to 2 mispredictions per execution of the loop, assuming repeated execution of the loop as a whole, and that the loop itself iterates rather than does not iterate. Assuming other things being equal, the 2-bit predictor will mispredict only last, but not first (in the context of repeated iteration of the loop as a whole).