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.
Nice! I saw the code and thought, I bet there’s a way to do some SIMD here… never touched intrinsics in Rust before so I really appreciate you writing it up!
Good question. I personally doubt that the compress instruction is easy to coax compilers into generating, as there are many edge cases to consider.
For example, you'll notice here that we perform a full vector store of 8 elements unconditionally, even if only a few of the elements are active. This is safe, though, because the output buffer is as large as the input buffer, and we're chunking by 8, so we'll never trash memory past the end; but this is a tricky analysis. Performance-wise, we rely on the CPU's store buffer to make these overlapping stores cheap.
Instead, you might think that you could just store the elements which are actually active, using a masked store. In fact there is also an intrinsic for this purpose (_mm512_mask_compressstoreu_pd), but it is extremely slow on some CPUs, namely Zen 4, so it's dangerous to use unless you know exactly what CPU you're using. (In my testing, there also seems to be some weird hazard on Zen 5 where multiple memory-destination compress instructions to nearby, even non-overlapping, addresses are serialized. But I haven't looked closer at this.)
I'm apparently not good at spotting it. I was put off by the overly dramatic presentation. It gets tiring that the author apparently finds this more exciting than I do, and writes like it's enthralling. I just assumed it was an excess of enthusiasm or the first experience with this kind of thing. If it's AI, I'm way behind the game noticing it.
"The smoking gun" is right there in the text ;) (but also things like "Same million floats. Same threshold. Same function."). Don't know if other models have that same specific style, but it looks very 'claude-y'.
I wouldn't be surprised though if (especially) non-native speakers unconsciously tart adopting the Claude writing style when they stare all day long at Claude generated text at work.
> I was put off by the overly dramatic presentation. It gets tiring that the author apparently finds this more exciting than I do, and writes like it's enthralling.
That's one of the main tells that AI wrote this. All the stylistic tics that people usually point out combine to make the writing seem more important than it is.
Click on their blog index page, see posts going back to early 2010s and use the same writing style. He must have been time travelling and using AI all this time!
I had a look at their blog page out of curiosity, not that you can prove much from the purported dates and text on a blog, which could be edited at any time.
I think he's asked it to write in his specific style, or possibly he has edited parts of it to his style, or maybe used AI to generate the initial draft.
Something like that anyway. There are some very clear AI tells (smoking guns if you like), but most of it does not read like the prose AI produces by default.
Author if you are here I am curious about your writing process, and why you didn't remove the obvious AI tells.
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.
> I get the impression that CPU designers in the 80s and early 90s massively underestimated just how beneficial even a small predictor can be.
It's got a lot to do with how cpu clock speeds were getting way faster, but ram wasn't. That's what makes deeper pipelines attractive, and if you give a cpu a deeper pipeline, it's gonna want a good branch predictor.
Cortex M0 and microprocessors generally do not. Cortex M3’s looks nothing like the branch prediction you think of when you think consumer or server CPU. Basically branch prediction requires extra power so it’s excluded or greatly simplified in low power use cases.
I'm not sure how your intuition can be that off, if you don't have a branch predictor then any branching code is going to be even slower than it already is, favouring branchless code even more for obvious reasons.
I say this as someone who is interested in a special type of processor architecture that has no branch prediction at all and would need a branchless subset of Rust to meaningfully program it at high performance.
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
This problem is called stream compaction and there is a wealth of research on it. The best methods use prefix scan. They first efficiently compute the index in the output array of each element that satisfies the predicate and then they gather them in one linear operation.
Also, I can tell that you are a good writer. You didn't need the LLM to "polish" your text.
There is clearly LLM-prose involved, but it's pretty well done. Here's one example: "The reallocations were real, but they were never the bottleneck."
LLMs love this pattern. Whether one put it into this text, or the author soaked it up and now used it himself, who knows. But it is one of the few things in the post that gives me the ick.
And then, there's the verbosity.
If I had to guess, an LLM was involved, but the author did a good job with manual writing and editing, too.
I don't know if an optimization is allowed to "invent" a write, but I would be surprised if an optimizer goes that far because I have to believe that the number of cases where more writes improve performance are pretty slim.
Nice post!
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.Nice! I saw the code and thought, I bet there’s a way to do some SIMD here… never touched intrinsics in Rust before so I really appreciate you writing it up!
See the following pdf for example on how to do this with SSSE3 (pages 104-133) or even SSE2 (pages 151-173)
https://deplinenoise.files.wordpress.com/2015/03/gdc2015_afr...
I heard there's a way to arrange code such that the compiler can autobectorize easier. I wonder if there's a way to do that here?
Would probably have to pass `-C target-cpu=native` to cargo so that llvm is allowed to use AVX512.
Good question. I personally doubt that the compress instruction is easy to coax compilers into generating, as there are many edge cases to consider.
For example, you'll notice here that we perform a full vector store of 8 elements unconditionally, even if only a few of the elements are active. This is safe, though, because the output buffer is as large as the input buffer, and we're chunking by 8, so we'll never trash memory past the end; but this is a tricky analysis. Performance-wise, we rely on the CPU's store buffer to make these overlapping stores cheap.
Instead, you might think that you could just store the elements which are actually active, using a masked store. In fact there is also an intrinsic for this purpose (_mm512_mask_compressstoreu_pd), but it is extremely slow on some CPUs, namely Zen 4, so it's dangerous to use unless you know exactly what CPU you're using. (In my testing, there also seems to be some weird hazard on Zen 5 where multiple memory-destination compress instructions to nearby, even non-overlapping, addresses are serialized. But I haven't looked closer at this.)
This article is 100% AI written. The data was interesting, the commentary overly verbose and hard to gain useful insights from.
I'm apparently not good at spotting it. I was put off by the overly dramatic presentation. It gets tiring that the author apparently finds this more exciting than I do, and writes like it's enthralling. I just assumed it was an excess of enthusiasm or the first experience with this kind of thing. If it's AI, I'm way behind the game noticing it.
"The smoking gun" is right there in the text ;) (but also things like "Same million floats. Same threshold. Same function."). Don't know if other models have that same specific style, but it looks very 'claude-y'.
I wouldn't be surprised though if (especially) non-native speakers unconsciously tart adopting the Claude writing style when they stare all day long at Claude generated text at work.
> I was put off by the overly dramatic presentation. It gets tiring that the author apparently finds this more exciting than I do, and writes like it's enthralling.
That's one of the main tells that AI wrote this. All the stylistic tics that people usually point out combine to make the writing seem more important than it is.
Click on their blog index page, see posts going back to early 2010s and use the same writing style. He must have been time travelling and using AI all this time!
I had a look at their blog page out of curiosity, not that you can prove much from the purported dates and text on a blog, which could be edited at any time.
The blog posts from 2010s are in a completely different style and written by a human: https://www.greyblake.com/blog/vim-preview-plugin/ https://www.greyblake.com/blog/how-to-install-firefox-icewea... https://www.greyblake.com/blog/unexpected-ruby-behaviour/ ...
This new blog post is clearly AI edited (probably 'improved' with AI), the old ones are not.
I think he's asked it to write in his specific style, or possibly he has edited parts of it to his style, or maybe used AI to generate the initial draft.
Something like that anyway. There are some very clear AI tells (smoking guns if you like), but most of it does not read like the prose AI produces by default.
Author if you are here I am curious about your writing process, and why you didn't remove the obvious AI tells.
idk why this is getting downvoted, I also got this sense, plugged it into Pangram and indeed, 80% AI-written score.
I guess that's fine, but after awhile I get a spidey-sense reading something that feels like a Claude session.
A good part of the article feels like it was written by Claude indeed:
- "The reallocations were real, but they were never the bottleneck."
- "Note that the villain is not the branch itself. It is the branch that [..]"
- "Same million floats. Same threshold. Same function."
- "Notice the price we paid though."
Sad to see you getting voted down. But I guess both the pro-AI crowd and anti-AI crowd hate Pangram.
I really hope all these guns give up smoking sometime soon...
claude sends its regards
indeed
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.
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.
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.
> I get the impression that CPU designers in the 80s and early 90s massively underestimated just how beneficial even a small predictor can be.
It's got a lot to do with how cpu clock speeds were getting way faster, but ram wasn't. That's what makes deeper pipelines attractive, and if you give a cpu a deeper pipeline, it's gonna want a good branch predictor.
Cortex M0 and microprocessors generally do not. Cortex M3’s looks nothing like the branch prediction you think of when you think consumer or server CPU. Basically branch prediction requires extra power so it’s excluded or greatly simplified in low power use cases.
I'm not sure how your intuition can be that off, if you don't have a branch predictor then any branching code is going to be even slower than it already is, favouring branchless code even more for obvious reasons.
I say this as someone who is interested in a special type of processor architecture that has no branch prediction at all and would need a branchless subset of Rust to meaningfully program it at high performance.
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
This problem is called stream compaction and there is a wealth of research on it. The best methods use prefix scan. They first efficiently compute the index in the output array of each element that satisfies the predicate and then they gather them in one linear operation.
Also, I can tell that you are a good writer. You didn't need the LLM to "polish" your text.
There is clearly LLM-prose involved, but it's pretty well done. Here's one example: "The reallocations were real, but they were never the bottleneck."
LLMs love this pattern. Whether one put it into this text, or the author soaked it up and now used it himself, who knows. But it is one of the few things in the post that gives me the ick.
And then, there's the verbosity.
If I had to guess, an LLM was involved, but the author did a good job with manual writing and editing, too.
Would PGO figure this out?
a simple perf stat should show that the "Keep 50% of random data" case will have insanely more branch mis-predictions that the others.
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
I don't know if an optimization is allowed to "invent" a write, but I would be surprised if an optimizer goes that far because I have to believe that the number of cases where more writes improve performance are pretty slim.
"A branch is cheap. A mispredicted branch is not."
oh hell nah
I've been doing leetcode in Janet in a (sometimes) tacit (variabless), branchless way: