In C++, does the branch predictor predict implicit conditional statements?

Question

In this code, it is written, result += runs[i] > runs[i-1];, an implicit conditional statement. In C++, does the branch predictor make predictions for this statement? Or do I have to explicitly use the if keyword to get branch prediction going?

using namespace std; 
int progressDays(vector<int> runs) {
    if (runs.size() < 2) {return 0;}
    int result = 0;
    for (int i = 1; i < runs.size(); i++) {result += runs[i] > runs[i-1];}
    return result;
}

I don't think the C++ language, per se, has such a thing as a "branch predictor". Your particular CPU might have one, in which case whether it gets used would depend on whether the compiler generated code containing a branch, or not. Many machines would have ways to do this without branching, and compilers tend to prefer those where possible. Note that even if you do use the `if` keyword, the compiler is still equally free to generate branchless code. — Nate Eldredge, Jul 29 '20 at 02:01

Peter Cordes · Accepted Answer · 2020-07-29T02:53:07.327

CPUs don't run C++ directly, they run machine code. So the answer depends on how your C++ compiles to assembly / machine code. Your choices for expressing program logic in C++ only indirectly influences this. Modern compilers can and will do if-conversion of a C++ if() statement into asm without branches (aka branchless). (For GCC, that's done more aggressively at -O3 than at -O2 - see gcc optimization flag -O3 makes code slower than -O2)

One most architectures, there are efficient ways to turn a compare result into a 0 or 1 integer fairly directly. (Or branchlessly increment a different way, or even more directly, e.g. AArch64's csinc / csel / cinc instruction which does a conditional increment, reading an input register and flags). So generally using x < y as an integer value will compile branchlessly.

int conditional_inc(int x, int y, int z) {
    z += (x<y);
    return z;
}

For example, on the Godbolt compiler explorer

# x86-64 clang -O3
conditional_inc(int, int, int)
        xor     eax, eax        # prepare a zeroed register for setl of the low byte, to extend to 32-bit.  (x86 is annoyingly clunky and inefficient at this)
        cmp     edi, esi
        setl    al              # EAX = AL = (x<y) signed compare
        add     eax, edx        # EAX += z in the retval register
        ret

AArch64 is much more efficient, with a combined increment and select instruction replacing xor-zero/setcc/add.

conditional_inc(int, int, int):
        cmp     w0, w1           // compare
        cinc    w0, w2, lt       // use the flags result, and the other 2 inputs.
        ret

All of these, like x86-64 setcc, are just ALU instructions, not control (no conditional change to the program counter), so have a data dependency instead of a control dependency, and thus don't need branch prediction because there's no branching. (The most well-known such instruction is probably x86 cmovcc, but in this case only setcc is needed)

Is CMOVcc considered a branching instruction?
Why is a conditional move not vulnerable for Branch Prediction Failure? shows an asm example of using cmov to conditionally increment.

In general, compares are separate from to branching. You can compare and then get a boolean without branching. (Branches do need something to branch on, but that can be an implicit compare against zero of an integer or boolean.)

So that's not a conditional statement, it's just a boolean being used as an integer.

In C++, does the branch predictor predict implicit conditional statements?

1 Answers1