Branch Misprediction Penalties & Branchless Algorithmic Design

Speculative Execution, TAGE Predictors & The 18-Cycle Flush Penalty

Modern out-of-order processors divide instruction execution into deep pipelines (Fetch $\to$ Decode $\to$ Rename $\to$ Dispatch $\to$ Execute $\to$ Retire). When the decoder encounters a conditional jump (je, jg), the outcome may depend on an arithmetic operation or memory load still in flight. The hardware Branch Predictor (typically a TAGE—TAgged GEometric history length predictor) predicts Taken or Not-Taken based on local two-bit saturating counters and global branch history registers:

• Correct Prediction (~0–1 cycle overhead): Speculative instructions along the predicted path are already decoded and executing in the Reorder Buffer (ROB). When the branch resolves, those instructions retire seamlessly.
• Branch Misprediction (15–20 cycle pipeline flush): Every speculative instruction fetched after the branch must be squashed from the ROB, register alias tables must be rolled back, and the instruction fetcher must restart from the correct target address—wasting 15 to 20 clock cycles (equivalent to 60–100 ALU instructions!).
• Data-Dependent Branching (Quicksort / Binary Search / Filtering): When partitioning random keys around a median pivot or binary searching a large table, a[i] < pivot is information-theoretically has maximum Shannon entropy ($H = 1$ bit): the branch predictor cannot do better than 50% accuracy!

Visualizing Speculative Pipeline Flush vs Branchless CMOV Dataflow

The diagram below shows how a single mispredicted branch squashes 16 cycles of in-flight pipeline stages, whereas a branchless CMOV or bitmask instruction streams through the execution units without ever stalling instruction fetch.

Production Implementations: Branchless Binary Search & BlockQuicksort Offset Buffering

The C++20 implementations below show two landmark branchless algorithms: branchless lower_bound (which compiles to a tight 4-instruction cmp + cmov loop) and the core offset-collection loop of Orson Peters' pdqsort / Edelkamp-Weiss BlockQuicksort.

// C++20: Branchless Binary Search & BlockQuicksort Branchless Partitioning
#include <cstddef>
#include <cstdint>
#include <utility>

// 1. Branchless Lower Bound: Compiles to cmp + cmovb with ZERO conditional jumps!
const int64_t* branchlessLowerBound(const int64_t* base, size_t n, int64_t target) noexcept {
    while (n > 1) {
        size_t half = n / 2;
        // __builtin_prefetch(base + half / 2); // Optional L1 prefetch for huge N
        base += (base[half - 1] < target) ? half : 0; // Single CMOV instruction!
        n -= half;
    }
    return base + (*base < target);
}

// 2. Edelkamp-Weiss / pdqsort Branchless Offset Filtering (64-element L1 block)
// Collects indices of elements < pivot without a single branch misprediction!
size_t collectLeftOffsets(const int64_t* block, int64_t pivot, uint8_t* offsetsOut) noexcept {
    size_t count = 0;
    for (uint8_t i = 0; i < 64; ++i) {
        offsetsOut[count] = i;               // Always write index i to current slot
        count += (block[i] < pivot);         // Advance slot pointer ONLY if condition holds!
    }
    return count;
}