"Branchless is faster" is not a rule; it is a measurement that depends on (a) whether the compiler actually produced branchless code and (b) whether the branch would have been predictable. Four functions on the same data: select_naive s += c[i] ? a[i] : b[i] as people write it select_cmov load both, then select the shape that gets if-converted select_branch a REAL branch, forced with an asm barrier compact out[j] = in[i]; j += keep[i] branchless stream compaction run on a random condition (unpredictable) and a periodic one (predictable).
$ git clone https://github.com/adit4443ya/debug_labs.git && cd debug_labs
$ cd codegen && ./build.sh
$ ../tools/pin.sh -q ./bin/04_branch_cmov
random condition naive 7.35 cmov 1.02 forced-branch 7.56 compact 1.54 (ns/elem)
predictable condition naive 0.97 cmov 1.75 forced-branch 1.20 compact 1.06 (ns/elem)
random condition naive 7.29 cmov 1.49 forced-branch 7.51 compact 1.13 (ns/elem)
predictable condition naive 0.98 cmov 0.73 forced-branch 1.66 compact 0.78 (ns/elem)select_naive: a BRANCH, on the pointer, not a cmov: cmpl $0, (%rdx,%r9,4) movq %rsi, %rcx je .LBB0_8 movq %rdi, %rcx # rcx = c[i] ? a : b ... then load (%rcx,%r9,4) Clang chose to branch and load only one side. Reasonable in general (loading both sides could touch memory you never needed), fatal on random data: 7.3 ns/elem = a mispredict every other element. select_cmov: loading both sides first made the select if-convertible, and then VECTORIZABLE. There is no cmov at all: a 128-bit blend: movq (%rdi,%rax,4),%xmm3 ; movq (%rsi,%rax,4),%xmm5 ; movq (%rdx,%rax,4),%xmm7 pcmpeqd %xmm1,%xmm7 ; pand %xmm7,%xmm5 ; pandn %xmm3,%xmm7 ; por %xmm5,%xmm7 Four elements per step, no control flow, 1.0-1.5 ns on random data: 5-7x faster than the branch. Same source semantics; different shape. select_branch: the asm barrier keeps a real jcc; it tracks `naive`. compact: branchless by construction, and clang found a neat trick: movl (%rsi,%r8,4), %r10d ; movl %r10d, (%rdi,%rax,4) # unconditional store cmpl $1, (%rdx,%r8,4) ; sbbq $-1, %rax # j += (keep != 0) via carry The store always happens (to out[j], overwritten next time if not kept) and the index advances via subtract-with-borrow. ~1 ns/elem regardless of the data. This is how you write a filter for unpredictable predicates.
With a periodic condition (512 true, 512 false) the branch predictor is right almost always, and naive/branch cost 1.0-1.7 ns: about the same as the branchless versions, within run-to-run noise (cmov shows 1.75 in one pass and 0.73 in the next: that spread IS the noise floor of a 4M-element loop on this laptop, lab perf/01). So: on predictable data, nothing to gain; on unpredictable data, 5-7x. The data decides, and you can measure predictability directly: `perf stat -e branch-misses:u`.
B1. Never assume the compiler emitted a cmov. Read the loop. The shape of the source (load-both vs load-one) changes its decision. B2. Branchless wins when the condition is unpredictable AND both sides are cheap and safe to evaluate. It loses when one side is expensive, or when the branch was predictable and the select adds latency to a dependency chain. B3. Prefer formulations the vectorizer can take (load both, blend) over hand-written bit tricks; and check `perf stat -e branch-misses` before and after.
1. Compile with -march=native: the blend becomes 256-bit (vpblendvb); does random-condition cmov get faster? (It is probably already bandwidth/latency-bound on the three loads.) 2. Make `a[i]` expensive: `a[i] * a[i] / 7`. On predictable data the branch now wins clearly: it skips the work half the time. 3. Sort `c_rand` (all zeros then all ones) and rerun: the "random" rows become the predictable ones. That is the classic interview question, and now you own the counter that proves it (lab perf/02). ============================================================
#include "../tools/bench.h"
#define N (1u << 22)
/* Selection as most people write it. Does clang emit a branch or a cmov? (Read the asm before guessing.) */
__attribute__((noinline)) int64_t select_naive(const int *a, const int *b, const int *c, size_t n) {
int64_t s = 0; for (size_t i = 0; i < n; i++) s += c[i] ? a[i] : b[i]; return s;
}
/* Both sides loaded unconditionally, then selected: this shape clang if-converts (and vectorizes). */
__attribute__((noinline)) int64_t select_cmov(const int *a, const int *b, const int *c, size_t n) {
int64_t s = 0; for (size_t i = 0; i < n; i++) { int va = a[i], vb = b[i]; s += c[i] ? va : vb; } return s;
}
/* The same selection with a REAL branch, forced by an asm barrier (see lab perf/02). */
__attribute__((noinline)) int64_t select_branch(const int *a, const int *b, const int *c, size_t n) {
int64_t s = 0;
for (size_t i = 0; i < n; i++) { if (c[i]) { s += a[i]; __asm__ volatile("" ::: "memory"); } else s += b[i]; }
return s;
}
/* Compaction: copy the elements that pass a test. Branchy or branchless? Read the asm. */
__attribute__((noinline)) size_t compact(int *out, const int *in, const int *keep, size_t n) {
size_t j = 0; for (size_t i = 0; i < n; i++) { out[j] = in[i]; j += keep[i] != 0; } return j;
}
static void run(const char *label, const int *c, int *a, int *b, int *out) {
uint64_t t0; int64_t r; size_t k;
t0 = bench_ns(); r = select_naive(a, b, c, N); BENCH_KEEP(r); double nv = (double)(bench_ns() - t0) / N;
t0 = bench_ns(); r = select_cmov(a, b, c, N); BENCH_KEEP(r); double cmov = (double)(bench_ns() - t0) / N;
t0 = bench_ns(); r = select_branch(a, b, c, N); BENCH_KEEP(r); double br = (double)(bench_ns() - t0) / N;
t0 = bench_ns(); k = compact(out, a, c, N); BENCH_KEEP(k); double cp = (double)(bench_ns() - t0) / N;
printf("%-22s naive %5.2f cmov %5.2f forced-branch %5.2f compact %5.2f (ns/elem)\n", label, nv, cmov, br, cp);
}
int main(void) {
int *a = malloc(N * 4), *b = malloc(N * 4), *c_rand = malloc(N * 4), *c_pred = malloc(N * 4), *out = malloc(N * 4);
uint64_t seed = 5;
for (size_t i = 0; i < N; i++) { a[i] = (int)(i & 1023); b[i] = (int)(i & 511); c_rand[i] = (int)(bench_rand(&seed) & 1); c_pred[i] = (i & 1023) < 512; }
for (int rep = 0; rep < 2; rep++) { run("random condition", c_rand, a, b, out); run("predictable condition", c_pred, a, b, out); }
return 0;
}A lab is done when you can say what it showed on your machine — not when you have read it.
It decides which problems come first, which drills open, which labs you see and how the Learn surface is organised. Change it any time from the switch in the top bar, or press Escape to look around first.