Branchless Rust: Making a Filter 4x Faster by Removing an If
1–10 of 124 posts
Re: Branchless Rust: Making a Filter 4x Faster by Removing an If
#2Thanks for sharing, optimisations like these are what keeps the fun in programming. I have been optimising my JSONLogic evaluator in rust and used arena allocator and preallocation tricks that gave me good jump in tuning. Let me see if branchless programming techniques can get any further in my case
Re: Branchless Rust: Making a Filter 4x Faster by Removing an If
#3Great 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?
Re: Branchless Rust: Making a Filter 4x Faster by Removing an If
#4Would PGO figure this out?
Re: Branchless Rust: Making a Filter 4x Faster by Removing an If
#5Great 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…
Virtually every CPU has branch prediction, going back to at least the original Pentium (1993), maybe earlier.
If you're running on a very old CPU, yes, the regular algo should be faster.
Re: Branchless Rust: Making a Filter 4x Faster by Removing an If
#6I'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 |( numbs))
(map - numbs (accumulate2 min numbs)))))Re: Branchless Rust: Making a Filter 4x Faster by Removing an If
#7Would PGO figure this out?
They could.
but.... running PGO is just too much pain.
We can't do it "incrementally", can we? How about combining with LTO?
edit: I was thinking profiling individual module on a test driver and link them after PGO
Re: Branchless Rust: Making a Filter 4x Faster by Removing an If
#8Great 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…
Virtually every CPU has branch prediction, going back to at least the original Pentium (1993), maybe earlier. If you're running on a very old CPU, yes, the regular algo should be faster.
[deleted]
Re: Branchless Rust: Making a Filter 4x Faster by Removing an If
#9Great 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…
CPUs aren't black boxes. They are actually much better documented than almost all the software that runs on them.
If you want to treat the CPU as a black box, trust me you do not want to use a CPU with out a branch predictor, your slow code will run like molasses frozen in antarctica.
The regular algo will be lightyears slower on any CPU that does not have a branch predictor.
Re: Branchless Rust: Making a Filter 4x Faster by Removing an If
#10This article is 100% AI written. The data was interesting, the commentary overly verbose and hard to gain useful insights from.