Speculative execution vs branchless code

Speculative Execution and Branchless Code: Hidden Performance Trade-offs

Modern processors execute billions of operations per second, but memory access speeds are growing more slowly. This gap means waiting for data becomes a major source of performance loss. Processors have evolved from passive executors to active data flow managers: out-of-order execution, dependency reordering, and speculative execution.

Branch prediction allows loads to start early, hiding memory latency. A misprediction costs 10–20 cycles, but waiting for L3 or DRAM takes hundreds. Branchless code eliminates misprediction but removes the processor's ability to speculate.

Evolution from Sequential to Speculative Execution

Early systems executed instructions strictly sequentially. The IBM System/360 Model 91 introduced the Tomasulo algorithm for out-of-order execution: instructions start when operands are ready.

Speculative execution emerged later in superscalar processors like the Intel Pentium Pro (1995). A 40-micro-op pipeline keeps dozens of instructions in flight, predicting branches based on history.

for (size_t i = 0; i < n; i++) {
    if (arr[i] >= 0) {
          ... code_true ...;
    } else {
        ... code_false ...;
    }
}

Here, loading arr[i] can cause a stall of 10–100+ cycles if the data isn't in L1. The processor predicts the branch, starts code_true, and initiates prefetch. On a misprediction—flush and restart.

Branchless vs Branchful: Cache Dependency

Simplified with branching:

if (arr[i] > 0) {
    result++;
}

Becomes:

result += (arr[i] > 0);

• Data in L1: branchless wins—no misprediction, minimal delay.
• L2: neutral, the cost of misprediction is low.
• L3/DRAM: branchful is faster—speculation triggers prefetch early, hiding latency.

Branchless moves the delay into the critical path: the processor waits for data before comparison, without overlapping computations.

Value Search: The Cost of Unconditional Loads

Original:

Value result = default_value;
for (size_t i = 0; i < n; ++i) {
    if (keys[i] == target) {
        result = values[i];
    }
}
return result;

Branchless:

Value result = default_value;
for (size_t i = 0; i < n; ++i) {
    result = (keys[i] == target) ? values[i] : result;
}
return result;

In branchless, values[i] loads on every iteration, wasting bandwidth on the entire array. The original reads only until a match.

Binary Search: Dependency Chains

Branchful:

while (low < high) {
    size_t mid = low + (high - low) / 2;
    if (keys[mid] < target)
        low = mid + 1;
    else
        high = mid;
}

The processor speculatively computes the next mid and prefetches keys[mid].

Branchless:

while (low < high) {
    size_t mid = low + (high - low) / 2;
    size_t step = (high - low) / 2;
    low  = (keys[mid] < target) ? mid + 1 : low;
    high = (keys[mid] < target) ? high    : mid;
}

Dependencies on the comparison result block speculation: the next mid waits for low/high writes.

• Half of predictions are wrong, but early prefetch overlaps the flush.
• Branchless: more instructions, later loads, explicit memory delays.

Key Takeaways

• Speculation hides memory latency by triggering prefetch on predicted branches.
• Branchless eliminates misprediction but worsens performance with L3/DRAM access.
• Profile on target hardware: L1—branchless, large arrays—branchful.
• Console game ports often suffer from ignoring these effects.
• Dependencies in branchless chains block OoO optimizations.

With random data in L1, branchless dominates. With patterns or large volumes, branchful wins due to speculative loads.

— Editorial Team