Branchless Rust: How Removing an if Made a Filter 4x Faster
Branchless Rust: Making a Filter 4x Faster by Removing an If
Filtering a slice of numbers sounds trivial, but a simple `if` can tank performance when the data is unpredictable. Serhii Potapov discovered that his idiomatic Rust filter was 4x slower on shuffled data than on sorted data, due to branch mispredictions. By rewriting the filter to use arithmetic instead of a branch—always writing and conditionally advancing—he made the worst case 4x faster and independent of data order. The trade-off: the best case gets slower, so branchless programming is only worth it for hot paths.
A branch is cheap. A mispredicted branch is not.
- anematode
Nice post!
You can do even a bit better if you're willing to use intrinsics. In particular this kind of operation is well-suited for compress-type operations, available as a first-class operation in at least AVX512, SVE and RVV; you can also emulate them reasonably quickly on NEON and AVX2.
Here's an example, building on the OP's work:
pub fn filter_compress(input: &[f64], threshold: f64) -> Vec<f64> {
use std::arch::x86_64::*;
let mut out = vec![0.0; input.len()];
let mut n = 0usize;
let (head, tail) = input.as_chunks::<8>();
for chunk in head {
unsafe {
let p = _mm512_loadu_pd(chunk.as_ptr());
let m = _mm512_cmpnle_pd_mask(p, _mm512_set1_pd(threshold));
let compress = _mm512_maskz_compress_pd(m, p);
_mm512_storeu_pd(out.as_mut_ptr().wrapping_add(n), compress);
n += m.count_ones() as usize;
}
}
for &x in tail {
out[n] = x;
n += (x > threshold) as usize;
}
out.truncate(n);
out
}
For me it's about 25% less time than the branchless version with 1,000,000 elements, and 60% less with 10,000 elements where memory bandwidth effects are less relevant.
- Retro_Dev
This article is 100% AI written. The data was interesting, the commentary overly verbose and hard to gain useful insights from.
- amiga386
A much clearer article from yesterday on making casefolding 15x faster by removing an if:
https://github.blog/engineering/architecture-optimization/do...
Discussion: https://news.ycombinator.com/item?id=49127983
- bormaj
Great explanation of why a branchless approach results in such a speed up. I've never really had to deal with performance optimization at this level. Generally it's probably best not to get too involved letting the CPU black box do its thing.
I do wonder, would the performance characteristics of branchless vs branching be consistent across different CPUs/architectures? If you had a CPU that wasn't trying to be fancy with branch prediction, would the regular algo be faster?
- aarjaneiro
I really hope all these guns give up smoking sometime soon...
- Magicrafter13
Based on the title, I knew the issue as soon as I looked at the first table. Still, great primer for those who don't know about such CPU shenanigans, and I did appreciate the solution, since I knew high level how to solve it, but didn't come up with an actual piece of code before the author presented theirs.
I didn't know about branch prediction or pipelined CPUs back when I was profiling the code I wrote - honestly it probably would have helped.
- yturijea
I like how we have pretty much established how branchless coding is superior to branched coding.
However I wonder if the compiler itself could recognize these patterns and turn branches into branchless instead, rather than making the code harder to read? as removing if conditions of course have a readability impact on the code.
- veqq
I've been doing leetcode in Janet in a (sometimes) tacit (variabless), branchless way:
(def find-shared-gcd
(comp
(fn [e] (max ;(map (fn [d] (* d ;(map |(- 1 (min 1 (mod $ d))) e)))
(range 1 (+ 1 (min ;e))))))
|((juxt* max min) ;$)))
(defn max-diff `where elements increase` [& numbs]
(reduce max
-1 (filter |(< 0 $) # strip 0s and add -1 in case (= true (apply > numbs))
(map - numbs (accumulate2 min numbs)))))