2.1 Conditional Branches and Branch Prediction

I want to show you how a computer makes decisions. In high level code, we write simple if statements and assume the computer jumps to the correct branch instantly. At the physical silicon level, decision making is a highly optimized, speculative process where the CPU attempts to read the future.

Let's look at how conditionals compile and how hardware structures affect execution speed.

When you write an if statement, the compiler translates it into a comparison instruction (such as cmp on x86_64 architectures) followed by a conditional jump instruction (like je for jump if equal, jl for jump if less).

int checkAge(int age) {
    if (age < 18) {
        return 0;
    }
    return 1;
}

// Generated x86_64 Assembly
checkAge:
    cmp     edi, 17          ; Compare input age register (edi) to 17
    jg      .L2              ; If greater than 17, jump to branch L2
    mov     eax, 0           ; Otherwise, load 0 into return register
    ret                      ; Return control
.L2:
    mov     eax, 1           ; Load 1 into return register
    ret

To speed up execution, modern CPUs use a pipeline. Instead of waiting for one instruction to complete before reading the next, the CPU loads multiple instructions into memory ahead of time. This is called instruction pipelining.

But what happens when the CPU hits a branch? It does not know which instruction to load next until the comparison completes. If it stops and waits, the pipeline empties, costing the CPU precious clock cycles. This stall is called a pipeline bubble.

To avoid bubbles, the CPU uses a hardware component called the Branch Predictor. The predictor attempts to guess which branch of the if statement will execute based on historical patterns.

* The Soup Waiter Metaphor: Think of the CPU branch predictor as a waiter in a diner. If a regular customer comes in and orders tomato soup 99 days in a row, the waiter pre-heats the soup before the customer even sits down (speculative execution). If on the 100th day the customer suddenly orders chicken noodle soup, the waiter has to throw out the heated tomato soup and start over. The waiter got confused, and service was delayed. In CPU terms, this is a branch misprediction, and clearing the speculative pipeline costs about 15 to 20 clock cycles.

Let's see this in action with a classic systems performance experiment. If we process a large array of random numbers in a loop and sum only the values greater than 128, the execution speed depends heavily on whether the array is sorted:

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>

int main() {
    const unsigned int arraySize{32768};
    std::vector<int> data(arraySize);

    // Fill data with random values from 0 to 255
    for (unsigned int i{0}; i < arraySize; ++i) {
        data[i] = std::rand() % 256;
    }

    // EXPERIMENT A: Unsorted array
    auto startUnsorted = std::chrono::high_resolution_clock::now();
    long long sumUnsorted{0};
    for (int val : data) {
        if (val >= 128) { // Branch predictor struggles to guess random inputs!
            sumUnsorted += val;
        }
    }
    auto endUnsorted = std::chrono::high_resolution_clock::now();

    // EXPERIMENT B: Sorted array
    std::sort(data.begin(), data.end());
    auto startSorted = std::chrono::high_resolution_clock::now();
    long long sumSorted{0};
    for (int val : data) {
        if (val >= 128) { // Branch predictor easily guesses: all false, then all true!
            sumSorted += val;
        }
    }
    auto endSorted = std::chrono::high_resolution_clock::now();

    // The sorted loop runs up to 3 times faster than the unsorted loop!
    return 0;
}

When the array is sorted, the condition val >= 128 evaluates to false for the first half of the array, and true for the second half. The branch predictor quickly locks onto this pattern and guesses correctly every time, achieving maximum instruction pipeline speed.

When writing low latency code, try to structure your algorithms to eliminate conditional branches inside tight loops, or ensure your hot paths process sorted data.

When you evaluate compound logical expressions using AND (&&) or OR (||), C++ performs short circuit evaluation. This means the compiler stops evaluating the expression as soon as the final result is guaranteed.

* For &&, if the left side is false, the right side is never evaluated.

* For ||, if the left side is true, the right side is never evaluated.

You can use this short circuiting behavior as a safety guard to prevent pointer dereferencing crashes:

int* ptr{nullptr};

// Safe! Since ptr is nullptr (false), the right side is never executed,
// preventing a segmentation fault crash!
if (ptr != nullptr && *ptr == 100) {
    std::cout << "Value matches!\n";
}

When you compile a switch statement with contiguous cases, the compiler does not generate a sequence of comparisons. Instead, it generates a Jump Table (an array of code address offsets in memory).

When the switch is executed, the CPU indexes directly into the jump table array in constant O(1) time and jumps straight to the correct code case, skipping all intermediate checks entirely. This is why switch statements are highly optimized for routing systems events.