In this lesson, you will learn how to structure your iterator predicates to minimize CPU pipeline stalls caused by branch mispredictions.
The Cost of Uncertainty
Modern CPUs use a pipeline to execute instructions in parallel. When your code hits an if statement, the CPU guesses which path it will take (branch prediction). If the guess is wrong, the CPU must flush the pipeline and restart, which is expensive. In an iterator pipeline, a filter condition that is "unpredictable" (e.g., alternating randomly between true and false) forces the CPU to guess repeatedly, resulting in significant performance degradation.
Designing Predictable Filters
To maximize throughput, you want your filter conditions to be stable. A filter that is consistently true or consistently false for long runs of data allows the CPU’s hardware predictor to lock onto a pattern.
Consider this scenario where we filter a large vector of integers:
// Less efficient: Randomly distributed data leads to mispredictions
let data = vec![1, 100, 2, 99, 3, 98];
let filtered: Vec<_> = data.iter().filter(|&&x| x > 50).collect();
// More efficient: Sorting or organizing data by the predicate condition
// allows the branch predictor to 'learn' the path quickly.
let mut data = vec![1, 100, 2, 99, 3, 98];
data.sort_unstable(); // Grouping values makes the predicate predictable
let filtered: Vec<_> = data.iter().filter(|&&x| x > 50).collect();
By sorting the data, you transform a sequence of alternating branches into a clear "false, false, false, true, true, true" pattern. The CPU quickly realizes that the first half of the sequence will fail the predicate and the second half will pass, essentially removing the misprediction penalty entirely.
Predicate Filtering vs. Branching
When possible, prefer "predicated" execution—where logic flows without branching. If you have complex logic, try to flatten it. Instead of nested if statements inside a filter, combine your conditions into a single Boolean expression. This reduces the number of branch points the CPU has to track, keeping the pipeline flowing smoothly through your iterator transformation.
Key Takeaway: To keep the CPU pipeline saturated, organize your data to ensure filter predicates remain stable for long sequences rather than alternating unpredictably.