Branchless Rust: Making a Filter 4x Faster by Removing an if | Serhii Potapov (greyblake)

A blog about software development.

Branchless Rust: Making a Filter 4x Faster by Removing an if

Serhii Potapov August 09, 2026 #rust #branchless #optimization

Most of my career I spent in the domain world programming, where correctness matters much more<br>than performance. Using Rust already made things fast enough. Avoid the N+1 SQL queries problem<br>and usually we are good.

But recently I found myself in a situation where I actually had to optimize a hot path.<br>This is how I discovered the branchless programming technique, and its results blew my mind.<br>Let me share it with you on a small example.

The problem

Let's keep things simple. We need to filter a slice of numbers and return the elements that are<br>greater than a given threshold (a typical problem that database engines solve all day long).<br>Normally I would write the following code:

pub fn filter_iter(input: &[f64], threshold: f64) -> Vecf64> {<br>input.iter().copied().filter(|&x| x > threshold).collect()<br>Easy to read, idiomatic, correct. Usually I would not touch it ever again.<br>But what if this beast happens to be on a hot path? Let's benchmark it!

The input is one million random f64 values uniformly spread over 0.0..100.0.<br>Instead of one threshold we will try several, chosen so that the filter keeps 1%, 25%, 50%, 75%<br>or 99% of the elements. For example, the threshold 50.0 keeps about a half.

The benchmarks are made with criterion and live in the<br>branchless-rust-benchmarks repo,<br>so you can reproduce everything on your own machine.

Puzzling results

Here is what criterion reports on my laptop (Intel i7-10875H):

keptoutput sizetime<br>1%~10k0.59 ms<br>25%~250k2.69 ms<br>50%~500k3.94 ms<br>75%~750k2.75 ms<br>99%~990k1.49 ms

Look at the 50% row. We copy only half of the elements, yet it is the slowest case of all.<br>Keeping 99% means copying almost twice as much data, and still it is 2.6 times faster.

The amount of input is identical in every row, and the amount of output clearly does not<br>explain the timings. Something else is going on.

First instinct: preallocate

Let's rule out the usual suspect first. collect() does not know the output size in advance,<br>so the Vec grows and reallocates along the way. Every Rust developer has a reflex for that:<br>preallocate!

pub fn filter_prealloc(input: &[f64], threshold: f64) -> Vecf64> {<br>let mut out = Vec::with_capacity(input.len());<br>for &x in input {<br>if x > threshold {<br>out.push(x);<br>out<br>The result at 50% kept: 3.87 ms . About 2% faster.<br>The reallocations were real, but they were never the bottleneck. Then what is?

What CPUs do behind our back

Let's stop for a moment and refresh how CPUs actually work.

A modern CPU does not execute one instruction at a time. It runs a deep<br>pipeline: while one instruction executes,<br>the next ones are already being fetched and decoded. This works beautifully, until the<br>instruction stream hits a fork in the road:

if x > threshold { /* keep */ } else { /* skip */ }<br>Which way does the road go? The CPU cannot know until the comparison actually finishes.<br>And it refuses to wait. Instead it guesses (the hardware responsible for guessing is called the<br>branch predictor) and speculatively runs ahead<br>along the guessed path.

The predictor is like a barista who starts making your usual order the moment you walk in.<br>If you are a regular, this is fantastic: the coffee is ready when you reach the counter.<br>If you order something random every day, the barista keeps pouring drinks into the sink.

A wrong guess is expensive. The CPU has to throw away everything it started speculatively,<br>flush the pipeline and restart from the fork. On a typical modern x86 core this costs around<br>15-20 cycles.<br>The comparison itself costs about one.

Now our table starts to make sense:

Keep 1%: the answer is almost always "skip". The predictor guesses "skip" and is right<br>99% of the time. Nearly free.

Keep 99%: the same story in the opposite direction.

Keep 50% of random data: there is no pattern to learn. The predictor is reduced to a coin<br>flip and is wrong on every second element. That is half a million pipeline flushes. At 15-20<br>cycles each it adds up to roughly 2 ms of pure penalty on a 4 GHz core, which is pretty much<br>the gap between the 50% and the 99% rows.

Note that the villain is not the branch itself. It is the branch that depends on unpredictable<br>data. Which suggests a fun experiment.

The smoking gun

If mispredictions are the problem, we should be able to keep the same data, the same threshold<br>and the same code, and change only the order of the elements. Let's sort the input (outside of<br>the measured section, of course) and rerun the 50% case:

input, 50% kepttime<br>shuffled4.15 ms<br>sorted0.93 ms

Same million floats. Same threshold. Same function. 4.5 times faster. On sorted data the<br>branch says "skip" for the entire first half and "keep" for the entire second half. Such a<br>pattern even the simplest predictor learns after one...