A hot loop picks the better of two quotes with an if. Rewriting it branchless with a conditional move made a random input case 3 times faster and a sorted input case 20 percent slower. Explain both results and state the rule you would use to choose.

A hot loop picks the better of two quotes with an if. Rewriting it branchless with a conditional move made a random input case 3 times faster and a sorted input case 20 percent slower. Explain both results and state the rule you would use to choose.

Approach: Compare the cost of a mispredicted branch against the cost of a data dependency the processor is unable to speculate through.

A branch that mispredicts near half the time costs 15 to 20 cycles of pipeline flush, so the branchless form wins on random data, while a conditional move creates a data dependency the processor must wait on instead of speculating past, so on sorted data the branch predicts correctly and is effectively free and the conditional move is slower. The rule is to keep the branch while the predictor is right above roughly 95 percent, and to go branchless once the outcome is close to random or depends on a value that arrives with the market data. Measure the branch-misses counter before changing anything, because the answer is a property of the input distribution rather than of the code. Branchless also removes the risk of speculating down the wrong path with a long latency load in it, which is the second reason to use it right after a load from memory.

Follow-up: How do you get the compiler to emit the conditional move without inline assembly, and how do you verify that it did?

Key concepts: branch misprediction, conditional move, data dependency, speculation.