Or am I wrong?
Or am I wrong?
When the processor reaches a conditional branch (the 'if' statement comparing the test value), rather than waiting for the actual results of the comparison to be known (and thus waiting for the test value to be loaded), it blindly guesses one of the branches and continues executing instructions as fast as it can. It doesn't commit the results of these instructions ('retire' the instructions) until the real answer is known, but crucially, it executes the loads sooner than they would otherwise be executed.
Most of these early loads are along the wrong path and the load is wasted, but half the time, the first guess is right, and half the time, the branch after that, etc. The end result is that branchy binary search ends up roughly twice as fast as a branchless version that waits for the loads to complete and efficiently makes only the loads that need to be made.
Conditional moves create a data dependency, and thus do not involve speculative execution. While the program can explicitly try to preload both possible values (and can benefit from doing so) the processor doesn't ever do this automatically. Other instructions can still be executed (out-of-order) but the path of execution does not change.
With a branch, rather than waiting for the results of the comparison to be known, the processor guesses at the result and chooses a path of execution. It thus executes the fetch immediately, but (about) half the time it's the wrong fetch. If after the original load completes it realizes that it guessed the wrong side of the branch, an 'exception' occurs, the speculative work is thrown away, and the execution begins again with the correct branch.