Branch prediction is how a CPU guesses where to fetch instructions before a branch resolves. For a conditional jump, it predicts whether to jump to the target or continue to the next instruction. Branchless programming expresses a decision without a conditional jump at that point in the compiled code, for example by selecting between values with a conditional move. In a low-latency trading system, a wrong guess in a market-data loop can make the processor discard work and fetch again from the correct path. Intel’s guide to speculative execution
Prediction supplies the guess. Speculative execution can act on it by running instructions before the branch resolves. On a miss, the CPU discards wrong-path results before they become part of the program’s committed state and resumes on the correct path. A wrong-path load can still affect the CPU cache. Removing one branch can remove that branch’s misses, while other control-flow or data speculation can still occur. Intel’s sections on transient execution and incidental channels
What a two-bit counter remembers
Imagine replaying one conditional branch in a feed handler. Model its predictor as a single two-bit counter. States 0 and 1 predict N (the jump is not taken), while 2 and 3 predict T (the jump is taken). Make each prediction from the current state. After resolution, add one on T or subtract one on N, stopping at 3 or 0 respectively. The counter saturates at each endpoint. This is a teaching version of the saturating-counter idea studied by Smith. Smith (1981), Strategy 7
Start at state 1. The first T catches the predictor guessing N, then moves the state to 2 so the second decision predicts T. The second T pushes it to 3. The next N is a miss, but it only moves the state back to 2. The counter will still predict T on the following decision. Later, two N outcomes in a row move it from 3 to 2 to 1, so a seventh decision would predict N. The six decisions shown have a miss rate of .
Read the point to the left of a decision to make its prediction. The point directly above it shows the state after the actual outcome.
The trace isolates one direction counter. Predictors can use history across multiple branches and look for patterns over several history lengths, as in the published TAGE design. An indirect jump can also require predicting a target address. The four misses above describe this counter with this initial state and sequence. A hardware predictor can give a different result, even on a sequence with the same mix of T and N outcomes. Seznec and Michaud (2006), §3 · Intel’s overview of branch speculation
When removing the branch helps
Suppose a compiled inventory loop chooses the signed quantity for a buy or sell. When both candidate values are cheap to compute, a conditional move can select one without sending the instruction stream down separate paths. In a feed decoder, by contrast, a predictable branch can avoid computing a candidate that requires parsing a different message layout or performing a separate lookup. A conditional move can put both candidate values and the comparison on the path to the result. A rewrite that computes both candidates must also preserve which memory accesses and side effects are allowed. For instance, selecting between two loaded values requires both loads to be valid. Intel’s branch-mispredict example · LLVM’s x86 conditional-move conversion
Inspect the optimized machine code to see which form the compiler emitted. LLVM, for instance, can turn an x86 conditional move back into a jump. Then compare equivalent implementations on the target CPU with the same representative events in the same order. Use branch and branch-miss counters to diagnose the hot path, and measure elapsed time or the relevant latency percentile to judge the change. Fewer misses can still leave the loop slower if the new version does more work or lengthens the chain of operations that must finish before the result is ready. LLVM’s x86 conditional-move conversion · Intel’s comparison of elapsed time and hardware counters
The SelfMadeQuant lesson on Profiling and Optimisation works through matched inputs, timing the actual entry point and checking that the results agree. The preview is public and the full lesson requires membership.
Sources
- Intel, Hardware Features and Behaviors Related to Speculative Execution, overview and incidental channels.
- James E. Smith, A Study of Branch Prediction Strategies (1981), Strategy 7.
- André Seznec and Pierre Michaud, A Case for (Partially) Tagged Geometric History Length Branch Prediction (2006), §3.
- LLVM, X86CmovConversion.cpp, pass overview and profitability criteria.
- Intel, Hardware-based Profile Guided Optimization, branch mispredict feedback and evaluation.