Branchless Rust: Achieving a 4x Speedup by Eliminating `if` Statements

By Serhii Potapov (greyblake) Published August 02, 2026 #rust #branchless #optimization

Disclaimer: Portions of this text were refined using an LLM.

For the majority of my professional life, I worked in domain-driven programming. In that world, correctness is the gold standard, and raw performance is usually a secondary concern. However, I recently encountered a "hot path" in my code that demanded optimization. This led me to the world of branchless programming, and the performance gains were staggering.

The Challenge: Filtering Data

The goal was simple: take a slice of numbers and filter out everything that doesn't exceed a specific threshold. This is a fundamental operation that database engines perform constantly.

Initially, I implemented the logic using the standard idiomatic approach:

pub fn filter_iter(input: &[f64], threshold: f64) -> Vec<f64> {
    input.iter()
         .filter(|&&x| x > threshold)
         .cloned()
         .collect()
}

Experimental Setup

To test this, I used the following parameters:

Dataset: $1,000,000$ random f64 values.
Distribution: Uniformly spread between $0.0$ and $100.0$ .
Test Cases: I varied the threshold to retain different percentages of the data:
- 1%
- 25%
- 50%
- 75%
- 99%

I used the criterion crate for benchmarking (available in the branchless-rust-benchmarks repository).

The Puzzling Results

Running these tests on an Intel i7-10875H produced some counter-intuitive data:

Kept %	Approx. Output Size	Execution Time
1%	$\sim 10\text{k}$	0.59 ms
25%	$\sim 250\text{k}$	2.69 ms
50%	$\sim 500\text{k}$	3.94 ms
75%	$\sim 750\text{k}$	2.75 ms
99%	$\sim 990\text{k}$	1.49 ms

Wait, what? The 50% case is the slowest, even though we are copying far less data than in the 99% case. If the bottleneck were simply memory bandwidth or allocation, the 99% case should be the slowest.

First Instinct: Preallocation

I suspected that collect() was struggling with frequent reallocations as the Vec grew. I tried preallocating the capacity:

pub fn filter_prealloc(input: &[f64], threshold: f64) -> Vec<f64> {
    let mut out = Vec::with_capacity(input.len());
    // ... filtering logic ...
    out
}

While reallocations were happening, they weren't the primary bottleneck. The performance anomaly remained.

Understanding the CPU Pipeline

To understand why this happens, we have to look at how modern CPUs process instructions. They use a deep pipeline, meaning they fetch and decode future instructions while the current one is still executing.

This is efficient until the CPU hits a conditional branch (a "fork in the road"):

Since the CPU doesn't know the result of the comparison immediately, it uses a branch predictor to guess the path.

The Barista Analogy: Imagine a barista who starts making your "usual" order the moment you walk through the door. If you always order a Latte, the coffee is ready before you even speak. But if you order something random every day, the barista wastes time making the wrong drink and has to pour it down the sink before starting over.

When the CPU guesses wrong, it must discard all speculatively executed work, flush the pipeline, and restart. This "misprediction penalty" is roughly $15\text{--}20$ cycles. On a 4 GHz core, this adds up to about $2\text{ms}$ of overhead—exactly the gap we see between the 50% and 99% benchmarks.

1% Kept: The predictor guesses "skip" and is almost always right.
50% Kept: The data is random; the predictor is essentially flipping a coin and failing half the time.

The Smoking Gun: Sorted Data

If mispredictions are the culprit, then changing the order of the data (without changing the values) should change the speed. I sorted the input and re-ran the 50% test:

Data State	Kept %	Time
Shuffled	50%	4.15 ms
Sorted	50%	0.93 ms

With sorted data, the branch is "skip" for the first half and "keep" for the second. The predictor learns this pattern instantly. This phenomenon is well-documented on Stack Overflow in the famous thread: "Why is processing a sorted array faster than processing an unsorted array?"

The Solution: Branchless Programming

Since we can't always sort our data, the goal is to remove the branch entirely. We want to turn a control dependency (where the program goes) into a data dependency (what value is used).

Here is the branchless implementation:

pub fn filter_branchless(input: &[f64], threshold: f64) -> Vec<f64> {
    let mut out = vec![0.0; input.len()];
    let mut n = 0;
    for &x in input {
        out[n] = x;
        // The boolean result is cast to 0 or 1
        n += (x > threshold) as usize;
    }
    out.truncate(n);
    out
}

How the trick works:

We write every element x to out[n] regardless of the threshold.
We calculate the increment for n using the comparison: $\text{increment} = (x > \text{threshold}) \text{ as usize}$ .
If the element is rejected, n does not increase, and the next valid element simply overwrites the rejected one.
Finally, we truncate(n) to remove the trailing garbage.

In assembly, the if is replaced by a seta instruction, which simply sets a register to 0 or 1. There is no "fork in the road," so there is nothing to mispredict.

(Note: While out[n] has a bounds check and the loop has a condition, these are highly predictable and essentially "free" for the CPU.)

Final Results

Kept %	Idiomatic `iter`	Branchless
1%	0.59 ms	1.09 ms
25%	2.69 ms	1.05 ms
50%	3.94 ms	1.03 ms
75%	2.75 ms	1.02 ms
99%	1.49 ms	1.11 ms

The worst-case scenario is now nearly 4x faster. More importantly, the execution time is now "flat"—it no longer depends on the distribution of the data.

The Trade-off: In the 1% case, the idiomatic version is still faster. This is because a correctly predicted branch is nearly free, whereas the branchless version pays the cost of writing every single element to memory regardless of whether it is kept.

Branchless Rust: Achieving a 4x Speedup by Eliminating if Statements