How deleting one if-statement made this filter 4x faster
How deleting one if-statement made this filter 4× faster.
A developer deleted one if-statement from ordinary code. It ran up to four times faster. Here's why that makes sense.
Slowest when it keeps half. Faster when it keeps almost all
Slowest when it keeps half. Faster when it keeps almost all.
The code is a filter: run through a million numbers, keep the ones past a cutoff. Yet it is slowest when it keeps half of them, and more than twice as fast when it keeps almost all. The input never changes.
Sort the same numbers first, and it runs 4.5x faster
Sort the same numbers first, and it runs 4.5× faster.
The obvious fix barely helped, about two percent. So copying was never the cost. The real clue: sort the same numbers first, and the slow case runs four and a half times faster. Only the order changed.
Your processor guesses which way each if goes, and races ahead
Your processor guesses which way each ‘if’ goes, and races ahead.
→ skip the number
Nearly free.
is thrown away.
A modern processor does not finish one step before starting the next. At every if, the processor cannot wait to see which way to go. So it guesses, and races ahead. On sorted data the answer barely changes, so the guess is nearly always right. On shuffled data, at the halfway mark, the guess is a coin flip. The processor is wrong about half the time, and every wrong guess throws away the work it already started. That wasted work, not the copying, is the slow part.
Delete the if. Always write, then move the cursor by 1 or 0
Delete the ‘if’. Always write, then move the cursor by 1 or 0.
input.iter().filter(|&x| x > threshold).collect()
n += (x > threshold) as usize; // 1 if kept, 0 if not
out.truncate(n); // cut the tail
So the developer deleted the decision. Always write the number down. Then move a cursor forward by the comparison: one when the number passes, zero when it does not. Cut the leftover tail. Nothing is left to guess, so the timing goes flat. Worst case, about four milliseconds down to one.
It's a trade: keep almost nothing, and the plain version wins
It’s a trade: keep almost nothing, and the plain version wins.
It is a trade. Keep one percent of the numbers, and the plain version wins. Deleting the decision gives up the best case to protect the worst. So save it for a loop you measured and found slow.
The slow part was never the work. It was the guessing
The slow part was never the work. It was the guessing.
The lesson reaches past this filter. Sometimes the slow part of your code is not the work. It is your processor guessing wrong about what comes next.
