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.
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?
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.
I think the Pentium is more or less the first microprocessor with branch prediction. Certainly the most mainstream.
PowerPC 601 arrived at more or less the same time, and the Alpha 21064 was a year earlier. There were a few minicomputers and mainframes before that with branch predictors.
Arguably the 486 could have done with a branch predictor (even a single entry loop predictor would have helped), and maybe the 386 too. But microcoded CISC designs didn't benefit much from predictors because they have multiple cycles to work it out.
And RISC cpus were in their "branch delay slots are awesome" phase throughout most of the 80s. With a bit of trickery (very simple branch conditions and a 2 phase clock), your classic 5-stage MIPS design can fully hide all branches with just a single branch delay slot, so they were a little slow to adopt predictors.
I get the impression that CPU designers in the 80s and early 90s massively underestimated just how beneficial even a small predictor can be.
Another recent story from github about case folding as part of code search, the simple version of the code had a couple of ifs, and the branchless version was actually slower.
They have a stupendously fast version and it is also branchless, but it just required more than branchless alone.
I'm fuzzy on the details but I think one of the ifs was an early exit, and without that the loop does a memory assignment on every byte instead of skipping most.
The really fast version was also vectorized. The branchless makes it possible to vectorize, but it was the vectorization that actually made it fast.
Worth noting that as written the "trick" results in memory usage proportional to the size of the input rather than the output. If the filter rejects most of the input the difference could be quite noticeable.
Thanks 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
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:
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.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?
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.
If you're running on a very old CPU, yes, the regular algo should be faster.
PowerPC 601 arrived at more or less the same time, and the Alpha 21064 was a year earlier. There were a few minicomputers and mainframes before that with branch predictors.
Arguably the 486 could have done with a branch predictor (even a single entry loop predictor would have helped), and maybe the 386 too. But microcoded CISC designs didn't benefit much from predictors because they have multiple cycles to work it out.
And RISC cpus were in their "branch delay slots are awesome" phase throughout most of the 80s. With a bit of trickery (very simple branch conditions and a 2 phase clock), your classic 5-stage MIPS design can fully hide all branches with just a single branch delay slot, so they were a little slow to adopt predictors.
I get the impression that CPU designers in the 80s and early 90s massively underestimated just how beneficial even a small predictor can be.
They have a stupendously fast version and it is also branchless, but it just required more than branchless alone.
I'm fuzzy on the details but I think one of the ifs was an early exit, and without that the loop does a memory assignment on every byte instead of skipping most.
The really fast version was also vectorized. The branchless makes it possible to vectorize, but it was the vectorization that actually made it fast.
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
I guess that's fine, but after awhile I get a spidey-sense reading something that feels like a Claude session.