Branchless Rust: Making a Filter 4x Faster by Removing an If
Ranked #5 on Hacker News with 107 points and 24 comments.
Most of my career I spent in the domain world programming, where correctness matters much more than performance. Using Rust already made things fast enough. Avoid the N+1 SQL queries problem and usually we are good.
But recently I found myself in a situation where I actually had to optimize a hot path. This is how I discovered the branchless programming technique, and its results blew my mind. Let me share it with you on a small example.
Let's keep things simple. We need to filter a slice of numbers and return the elements that are greater than a given threshold (a typical problem that database engines solve all day long). Normally I would write the following code:
Easy to read, idiomatic, correct. Usually I would not touch it ever again. 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 . Instead of one threshold we will try several, chosen so that the filter keeps 1%, 25%, 50%, 75% 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 branchless-rust-benchmarks repo, so you can reproduce everything on your own machine.