This is a common pattern a compiler should recognise and optimise into an efficient data and control flow. So much for a sufficiently smart compiler. shrug
Branchless Rust: Making a Filter 4x Faster by Removing an If
71–80 of 124 posts
Re: Branchless Rust: Making a Filter 4x Faster by Removing an If
#72Earlier quoted context omitted.
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 start adopting the Claude writing style when they stare all day long at Claude generated text at work.
I would assume non-native speakers talk to Claude in their own language. Now I'm curious if Claude's weird quirks of speech are unique in each language or if they carry over!
Re: Branchless Rust: Making a Filter 4x Faster by Removing an If
#73Nice 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: pub fn filter_compress(input: &[f64], threshold: f64) -> Vec { use std::arch::x86_…
Thank you for sharing this. How would you emulate this kind of operation on avx2?
Re: Branchless Rust: Making a Filter 4x Faster by Removing an If
#74Worth 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.
I disagree in the sense that you can rewrite the code to use the trick and also not allocate in advance. Nothing about the trick requires you to allocate up front: before writing to out[n] you can extend the vector if it’s out of bounds. Or, after incrementing n, do out.push(0).
You should try writing it out. Doing it without introducing another unpredictable branch is harder than it looks.
I discussed this with a coworker earlier this week and the best they were able to come up with was
for &x in input {
out.push(x);
n += (x > threshold) as usize;
out.truncate(n);
}
Re: Branchless Rust: Making a Filter 4x Faster by Removing an If
#75Earlier quoted context omitted.
"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 start adopting the Claude writing style when they stare all day long at Claude generated text at work.
I would assume non-native speakers talk to Claude in their own language. Now I'm curious if Claude's weird quirks of speech are unique in each language or if they carry over!
This isn't a necessarily true assumption. I my social circles of non native English speakers, most of us use English to talk with models.
Re: Branchless Rust: Making a Filter 4x Faster by Removing an If
#76I like how we have pretty much established how branchless coding is superior to branched coding. However I wonder if the compiler itself could recognize these patterns and turn branches into branchless instead, rather than making the code harder to read? as removing if conditions of course have a readability impact on the code.
Branchless coding is superior to branched coding whenever the branches are more or less random, which happens frequently when checking some properties of input numbers, like their sign or whether they fall inside certain intervals, or when sorting an array that comes in random order. When a branch alternative will be taken much more frequently than the other, then branched coding with an "if" becomes superior. So nei…
This is true, but the example given yesterday showed that even if branches can be very well predicted (e.g. processing UTF-8 text which is 99.9999% ASCII), branchless code can result in speedup by making autovectorisation possible.
If the branchless code didn't transform to vector instructions, it would be strictly slower. But if it does, it allows the CPU to work on 16 bytes at a time instead of 1 at a time.
https://github.blog/engineering/architecture-optimization/do...
Re: Branchless Rust: Making a Filter 4x Faster by Removing an If
#77Earlier quoted context omitted.
"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 start adopting the Claude writing style when they stare all day long at Claude generated text at work.
I would assume non-native speakers talk to Claude in their own language. Now I'm curious if Claude's weird quirks of speech are unique in each language or if they carry over!
I'm German but still do all my computing in English (partly out of habbit, but also because Germanized technical text is usually painful to work with because it's full of anglizisms (is that actually an English word?)).
Re: Branchless Rust: Making a Filter 4x Faster by Removing an If
#78A much clearer article from yesterday on making casefolding 15x faster by removing an if:
https://github.blog/engineering/architecture-optimization/do...
Discussion: https://news.ycombinator.com/item?id=49127983
Re: Branchless Rust: Making a Filter 4x Faster by Removing an If
#79Earlier quoted context omitted.
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 tra…
I believe the bounds check, in particular, is devastating for autovectorization. There are ways around it, but it requires additional code in safe rust.
Edit: actually looks like autovectorization is in play here [1]. Doesn't look like the bounds check gets in the way at all.
Re: Branchless Rust: Making a Filter 4x Faster by Removing an If
#80Earlier quoted context omitted.
I would assume non-native speakers talk to Claude in their own language. Now I'm curious if Claude's weird quirks of speech are unique in each language or if they carry over!
This isn't a necessarily true assumption. I my social circles of non native English speakers, most of us use English to talk with models.
I switch languages randomly.