CONCEPT Cited by 1 source

Branchless programming

Definition

Branchless programming is a code-optimization technique that replaces data-dependent conditional branches (if/else, early-exit breaks) with arithmetic or bitwise operations that produce the same result without control-flow divergence. The goal is to enable CPU pipelining, SIMD vectorization, and speculative execution to proceed without misprediction penalties or vectorization barriers.

Why it matters

Modern CPUs and compilers derive enormous performance from:

1. Auto-vectorization — compilers emit SIMD instructions (processing 16+ bytes per instruction) only when the loop body has no data-dependent control flow. A single break or conditional branch in the loop body is sufficient to prevent vectorization entirely.

2. Pipeline efficiency — branch mispredictions cost 10–20 cycles on modern cores. Hot loops with unpredictable branches (data-dependent) pay this penalty repeatedly.

3. Instruction-level parallelism — out-of-order execution can overlap independent operations only when execution isn't blocked waiting for a branch resolution.

The counterintuitive trade-off

Branchless code is not unconditionally faster. GitHub's case-folding benchmarks demonstrate:

Version	Throughput	Vectorized?
Naive (break + branch)	3.1 GiB/s	No
Branchless body, keep break	2.6 GiB/s	No
Drop break, keep branches	7.6 GiB/s	Partially
Fully branchless	>45 GiB/s	Fully

The branchless body with early-exit is slower than naive branches (2.6 vs 3.1 GiB/s) because it replaces a rarely-taken conditional store with an unconditional store on every iteration — more write traffic for no benefit. Branchless wins only as the enabler for vectorization; in scalar code it can be a pessimization.

(Source: sources/2026-07-31-github-dont-stop-early-case-folding-source-code-at-memory-speed)

Common branchless idioms

• Arithmetic range test: b.wrapping_sub(b'A') < 26 — true exactly for A–Z, no branch
• Mask-based conditional write: b |= (is_upper << 5) — sets bit 5 for uppercase (lowercases it), no-op for everything else
• OR-accumulator instead of early-exit: high_bit_acc |= *b then test once after the loop — same information as if b >= 0x80 { break }, zero branches in the body

Seen in

• sources/2026-07-31-github-dont-stop-early-case-folding-source-code-at-memory-speed — canonical wiki instance demonstrating that branchless enables vectorization (3.1 → 45+ GiB/s) but pessimizes scalar code on its own

Related

• concepts/auto-vectorization — the compiler transform branchless code enables
• concepts/simd-vectorization — the hardware mechanism that delivers the throughput gain
• concepts/swar-byte-parallelism — sub-word parallelism technique for environments without SIMD
• patterns/branchless-sweep-then-check — the pattern of sweeping a buffer branchlessly then checking a single accumulator
• patterns/accumulator-instead-of-early-exit — the specific early-exit elimination technique