2 ms·
The phrase used by the author "because the CPU can't predict more than one branch per cycle" is misleading. Most existing CPUs can execute at least 2 condition
by adrian_b 2y ago
The phrase used by the author "because the CPU can't predict more than one branch per cycle" is misleading.
Most existing CPUs can execute at least 2 conditional jumps a.k.a. branches per clock cycle, if they are predicted as not taken.
Such CPUs can execute only one conditional jump per clock cycle when it is predicted as taken, which also means that in the same clock cycle one can speculatively execute only instructions that are beyond a single conditional jump that is predicted as taken.
So in most CPUs at least 2 conditional jumps can be predicted per clock cycle, but whether they can also be executed depends on the result of the prediction.
As mentioned in an endnote of the article, in the latest generation of CPUs from multiple companies, including AMD Zen 5, the ability to execute in a single clock cycle 2 branches predicted as taken has appeared (and the ability to speculatively execute instructions past the second taken branch).
Because of this difference between taken and not taken branches, it is always good for a compiler or for a human programmer to generate code such that all the conditional jumps (except those that terminate loops) are statically predicted as not taken. Both "if ... then ..." and "if ... then ... else ..." conditional statements have alternative implementations that can ensure that all conditional jumps are statically predicted as not taken. For "switch" a.k.a. "select" a.k.a. "case" instructions it is always possible to reorder the tested cases such that all the conditional jumps are statically predicted as not taken.
Unfortunately, in most programming languages it is not possible to provide a hint for the compiler on whether a tested condition is expected to be true or false. Such a hint could be easily provided in a programming language that has both "if" and "unless" conditional statements or expressions, where "if" could mean that the conditional statement is expected to be not executed and "unless" could mean that the conditional statement is expected to be executed (for the "else" or "otherwise" branch the expectation would be opposite).