The Problem: A Simple Filter That's Slow

Most Rust developers would write a filter like this without a second thought:

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

It's idiomatic, readable, and correct. But when Serhii Potapov benchmarked this on a hot path, he found something surprising. Using one million random f64 values uniformly distributed between 0.0 and 100.0, and varying the threshold to keep different percentages of elements, the timings were bizarre:

KeptOutput SizeTime
1%~10k0.59 ms
25%~250k2.69 ms
50%~500k3.94 ms
75%~750k2.75 ms
99%~990k1.49 ms

At 50% kept, the function is slowest, even though it copies only half the data. Keeping 99% means copying almost twice as much, yet it's 2.6 times faster. The amount of input is identical in every row, so what's going on?

The Usual Suspect: Reallocations

First instinct: collect() doesn't know the output size, so the Vec grows and reallocates. Preallocating with Vec::with_capacity should fix that:

pub fn filter_prealloc(input: &[f64], threshold: f64) -> Vec {
    let mut out = Vec::with_capacity(input.len());
    for &x in input {
        if x > threshold {
            out.push(x);
        }
    }
    out
}

At 50% kept, this runs in 3.87 ms — only 2% faster. Reallocations were real but not the bottleneck.

The Real Culprit: Branch Prediction

Modern CPUs don't execute one instruction at a time. They pipeline: while one instruction executes, the next ones are fetched and decoded. This works beautifully until the instruction stream hits a fork:

if x > threshold { /* keep */ } else { /* skip */ }

The CPU can't know which way to go until the comparison finishes. Instead, it guesses — the branch predictor — and speculatively executes the guessed path. A wrong guess is expensive: the CPU flushes the pipeline and restarts, costing 15-20 cycles on a typical x86 core. The comparison itself costs about one cycle.

Now the table makes sense:

  • Keep 1%: The answer is almost always "skip". The predictor guesses "skip" and is right 99% of the time. Nearly free.
  • Keep 99%: Same story in the opposite direction.
  • Keep 50% of random data: No pattern to learn. The predictor is a coin flip, wrong on every second element. Half a million pipeline flushes at 15-20 cycles each adds up to roughly 2 ms of pure penalty on a 4 GHz core.

The villain isn't the branch itself — it's the branch that depends on unpredictable data.

The Smoking Gun: Sorting

To prove it, Potapov sorted the input (outside the measured section) and reran the 50% case:

Input, 50% keptTime
Shuffled4.15 ms
Sorted0.93 ms

Same million floats, same threshold, same function — 4.5x faster. On sorted data, the branch says "skip" for the entire first half and "keep" for the second half. Even the simplest predictor learns that pattern after one miss.

This is exactly the effect described in the famous Stack Overflow question "Why is processing a sorted array faster than processing an unsorted array?" with 27K upvotes.

Of course, sorting isn't a fix: it costs more than filtering, and we usually need the original order. But now we know what to fix.

Branchless Programming: Removing the Fork

The idea is to remove the unpredictable branch entirely, so there's nothing to guess. Instead of deciding whether to write an element, always write it, and use the comparison to decide where the next element goes:

pub fn filter_branchless(input: &[f64], threshold: f64) -> Vec {
    let mut out = vec![0.0; input.len()];
    let mut n = 0;
    for &x in input {
        out[n] = x;
        n += (x > threshold) as usize;
    }
    out.truncate(n);
    out
}

Every element is written to out[n] unconditionally. (x > threshold) as usize is 1 when kept, 0 otherwise. If kept, the cursor n moves forward; if not, the next iteration overwrites the rejected value. At the end, truncate(n) cuts off the garbage tail.

The comparison is still there, but its result is used as a number, not as a decision. In compiler terms, we turned a control dependency into a data dependency. In the generated assembly, the comparison becomes a seta instruction that just produces 0 or 1. There's no fork, so nothing to mispredict.

(One caveat: out[n] = x performs a bounds check, and the loop condition is also a branch. But those branches go the same way a million times in a row, so the predictor handles them for free.)

Results: Flat and Fast

KeptIterBranchless
1%0.59 ms1.09 ms
25%2.69 ms1.05 ms
50%3.94 ms1.03 ms
75%2.75 ms1.02 ms
99%1.49 ms1.11 ms

The worst case became almost 4x faster. The branchless column is flat — running time doesn't depend on the data anymore.

But notice the price: at 1% kept, the idiomatic version wins because an almost always correctly predicted branch is nearly free, while the branchless version always pays for one million writes. Branchless code trades the best case for the worst case.

Should You Go Branchless?

Most of the time, no. Branchless code is harder to read and easier to get wrong. Compilers already know many tricks and do a lot of this work automatically.

Only when a profiler points at a hot loop containing a branch on unpredictable data does this technique pay off big.

Key Takeaways

  • A branch is cheap; a mispredicted branch is not.
  • The same filter is slowest around 50% selectivity on shuffled data because the branch predictor is reduced to a coin flip.
  • Branchless programming replaces the unpredictable branch with plain arithmetic: always write, conditionally advance.
  • The worst case got almost 4x faster and became independent of data distribution.
  • It's a trade, not magic: the best case gets worse, and readability suffers. Reserve it for measured hot paths.

Further Reading