Branchless code and bit tricks

A branch costs almost nothing when the CPU guesses its direction right, and 15–20 cycles when it guesses wrong: the pipeline has already fetched and started executing dozens of instructions down the wrong path, and throws them all away. Branchless code replaces "jump if" with "compute both, select one" — trading a possible misprediction for a certain small cost. This skill is about knowing which side of that trade you're on, reading the select instructions the compiler emits, and the bit-manipulation instructions that make a lot of branchy code unnecessary.

1. Branch prediction in one picture

The front end can't wait for a comparison to finish before fetching the next instruction, so it predicts. Predictors are very good at patterns — always-taken, alternating, loop exits, correlation with recent branches. They are hopeless on data that's genuinely random. A branch taken 50% of the time at random mispredicts about half the time.

#include <algorithm>
#include <chrono>
#include <cstdio>
#include <random>
#include <vector>

// asm volatile keeps a real conditional jump: without it GCC would turn the
// loop branch-free (and vectorise it) on its own.
[[gnu::noinline]] long sum_big(const std::vector<int>& v) {
    long s = 0;
    for (int x : v)
        if (x >= 128) { s += x; asm volatile("" ::: "memory"); }
    return s;
}

double ms(const std::vector<int>& v) {
    auto t0 = std::chrono::steady_clock::now();
    long r = 0;
    for (int rep = 0; rep < 20; ++rep) r += sum_big(v);
    auto t1 = std::chrono::steady_clock::now();
    if (r == 42) std::puts("");  // use r
    return std::chrono::duration<double, std::milli>(t1 - t0).count();
}

int main() {
    std::vector<int> v(1 << 20);
    std::mt19937 rng(1);
    for (int& x : v) x = static_cast<int>(rng() % 256);
    double random = ms(v);
    std::sort(v.begin(), v.end());
    double sorted = ms(v);
    std::printf("random: %.1f ms   sorted: %.1f ms\n", random, sorted);
}

Same work, same data, sorted versus shuffled — typically 5–10× apart on this machine. Sorted data makes the branch "not taken 128 times, then taken 128 times", which the predictor learns.

2. The select instructions

extern "C" int max_i(int a, int b) { return a > b ? a : b; }
extern "C" int below_mask(unsigned a, unsigned b) { return a < b ? -1 : 0; }

max_i:                 below_mask:
    cmp   edi, esi         cmp  edi, esi     ; CF = (a < b) unsigned
    mov   eax, esi         sbb  eax, eax     ; eax = -CF
    cmovge eax, edi        ret
    ret

cmov is not magic. It has a data dependency on both inputs and the flags, so the result can't be used until the comparison and both operands are ready. A correctly predicted branch has no such dependency — execution continues speculatively. That's why:

• Unpredictable condition → branchless wins. No misprediction to pay.
• Predictable condition → the branch often wins, especially when the condition sits on a long dependency chain or one side is expensive (cmov must compute both sides).

Compilers guess. GCC and Clang turn small ?: and if bodies into cmov when both sides are cheap and side-effect free; they keep branches when a side has a store, a call, or work you'd rather skip. When the choice matters, measure, and check the listing.

3. Writing it yourself

Arithmetic selects work with any compiler and every type:

#include <cstdint>
// mask is all ones or all zeros
inline std::uint32_t select(bool c, std::uint32_t a, std::uint32_t b) {
    std::uint32_t mask = -static_cast<std::uint32_t>(c);   // c ? 0xffffffff : 0
    return (a & mask) | (b & ~mask);
}

Watch out for signed overflow in the classic tricks. abs(x) as (x ^ (x >> 31)) - (x >> 31) overflows for INT_MIN; a - b to compare two ints overflows when they have opposite signs. Do the arithmetic in unsigned, where wrapping is defined, and convert at the end.

#include <climits>
#include <cstdint>
#include <cstdio>

// |a - b| as an unsigned value: exact for every pair of ints, no UB.
std::uint32_t abs_diff(std::int32_t a, std::int32_t b) {
    std::uint32_t ua = static_cast<std::uint32_t>(a), ub = static_cast<std::uint32_t>(b);
    return a < b ? ub - ua : ua - ub;
}

int main() {
    std::printf("%u %u %u\n", abs_diff(3, 10), abs_diff(INT_MIN, INT_MAX), abs_diff(-5, -5));
}

4. Branchless binary search

A textbook binary search has one unpredictable branch per level: whether to go left or right depends on the data. A branch-free version keeps a base pointer and a remaining length, and moves the base with a select:

#include <cstddef>
// Index of the first element >= key in sorted a[0, n).
inline long lower_bound_branchless(const int* a, long n, int key) {
    if (n == 0) return 0;
    const int* base = a;
    while (n > 1) {
        long half = n / 2;
        base = (base[half] < key) ? base + half : base;   // cmov
        n -= half;                                        // NOT n = half: odd n
    }
    return (base - a) + (*base < key);
}

The loop runs exactly ⌈log₂ n⌉ times regardless of the data, so its own branch is perfectly predicted. On arrays that fit in cache this is typically 1.5–3× faster than std::lower_bound on random queries; on huge arrays, cache misses dominate both and prefetching matters more (see the microarchitecture skill).

5. The bit-manipulation instructions

C++20's <bit> header maps directly onto single instructions — if the target has them:

Plain g++ -O2 targets the 2003-era x86-64 baseline, which has no popcnt. Either compile for a newer level (-march=x86-64-v2 has popcnt; -v3 adds lzcnt, tzcnt, BMI1/2, AVX2) or mark individual functions with __attribute__((target("popcnt"))) and dispatch at run time.

The std:: functions are defined for every input, including zero: std::countl_zero(0u) == 32. The GCC builtins they replace are not: __builtin_clz(0) and __builtin_ctz(0) are undefined behaviour (the old bsr/bsf instructions leave the destination undefined for zero input). Prefer <bit>.

Useful identities, all branch-free:

6. pext and pdep

BMI2's pext gathers the bits of x selected by a mask into the low end; pdep scatters low bits into the mask positions:

They're one instruction on Intel since Haswell and on AMD since Zen 3 (on Zen 1/2 they were microcoded and slow — a good example of "measure on your target"). A portable version loops over the mask's set bits, using m & (m - 1) to step:

#include <cstdint>
#include <cstdio>
#include <immintrin.h>

std::uint64_t pext_portable(std::uint64_t x, std::uint64_t mask) {
    std::uint64_t out = 0;
    for (std::uint64_t bit = 1; mask != 0; bit <<= 1) {
        if (x & mask & -mask) out |= bit;   // lowest remaining mask bit
        mask &= mask - 1;                    // drop it
    }
    return out;
}

__attribute__((target("bmi2"))) std::uint64_t pext_hw(std::uint64_t x, std::uint64_t mask) {
    return _pext_u64(x, mask);
}

int main() {
    std::uint64_t x = 0b1011'0110, m = 0b1100'1010;
    std::printf("%llu %llu\n", (unsigned long long)pext_portable(x, m), (unsigned long long)pext_hw(x, m));
}

(Calling a target("bmi2") function on a CPU without BMI2 crashes with an illegal instruction; real code checks __builtin_cpu_supports("bmi2") first.)

7. Checklist

• Is the condition predictable? Then a branch is probably fine. Random? Go branchless.
• Does the listing actually contain cmov/setcc? The compiler may have already done it — or refused because a side has a store or a call.
• Are the edge cases defined? INT_MIN, shift counts ≥ the width, clz(0).
• Is the bit instruction available on the target? Check the flags.