Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Branchless Rust: Making a Filter 4x Faster by Removing an If

greyblake.com

Post reply on HN
Print view View original

61–70 of 124 posts

Re: Branchless Rust: Making a Filter 4x Faster by Removing an If

#61

Post by tialaramex »

adrian_b wrote: post #55
yturijea wrote: post #53

I 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…

For sorting, conveniently we always definitely need to look at all the elements at least once anyway, so although even the early introspective sorts from the end of last century aren't designed this way both the Timsort and a modern sort like a PDQ sort will end up making that decision early.

"Oh, this was mostly already sorted, done"

If you meant exactly rather than almost then you can still squeak a small win from having an algorithm which is optimised for this case but the vast bulk of your runtime is eaten by the unavoidable work of checking. "Don't check" is faster but then you're not a sort algorithm at all.

Re: Branchless Rust: Making a Filter 4x Faster by Removing an If

#62

Post by returningfory2 »

khuey wrote: post #14

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.

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).

Re: Branchless Rust: Making a Filter 4x Faster by Removing an If

#63

Post by llama_drama »

Branchless code can indeed sometimes be slower than conventional one, but in this particular case, the article comes to the wrong conclusion. At a 1% kept, the branchless version is slower because it pays the cost of zero-initializing 8 MB of memory when allocating the Vec. This can be easily demonstrated by comparing it with a version that allocates uninitialized memory.

Re: Branchless Rust: Making a Filter 4x Faster by Removing an If

#64

Post by flohofwoe »

HackerThemAll wrote: post #52
Retro_Dev wrote: post #10

This article is 100% AI written. The data was interesting, the commentary overly verbose and hard to gain useful insights from.

It was fun to read and insightful for me, not too artificial, and not too verbose. I'm glad my internal AI detector doesn't win over my curiosity to learn.

The main problem with the article is that the idea to influence backend code generation decisions via specific highlevel code constructs is mostly just mystical bullshit (some compilers do detect specific patterns - usually for bit twiddling hacks, but not on a basic level like control flow optimization).

Using a highlevel language construct like "y += (x > 0) as usize;" doesn't "switch on" branchless code just because the source code looks branchless, compilers are not that dumb anymore.

E.g. I bet that writing

    if (x > 0) {
        y += 1;
    }
...generates the exact same code after optimization, otherwise I would consider that an LLVM bug.

The only reliable way is to mostly bypass the optimizer via simd intrinsics, or drop down to assembler, everything else is just cargo culting.

(fwiw I can't shake the feeling now that the article is recycled, I'm pretty sure I saw those exact same code examples in another "branchless" blog post, but maybe for a different language - because the next question was ineviatably "then why is the code using "if" slower? answer: because it also behaves differently). Or maybe I'm just having a strong dejavu ;)

Re: Branchless Rust: Making a Filter 4x Faster by Removing an If

#66

Post by benj111 »

imtringued wrote: post #33
bormaj wrote: post #3

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…

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 perform…

Why no branch predictor at all? Even a brain-dead one that predicts all branches always/never taken is going to provide some benefit, it's not as if the processor can do anything else while it's waiting.

Or am I missing something?

I note the hazard 3 on the pi Pico rp2350 only predicts a branch if it's the last branch and was taken, ie a single loop. Which seems weird to me, so I'm probably lacking understanding somewhere.

Re: Branchless Rust: Making a Filter 4x Faster by Removing an If

#68

Post by claudetard »

flohofwoe wrote: post #64
HackerThemAll wrote: post #52

Earlier quoted context omitted.

It was fun to read and insightful for me, not too artificial, and not too verbose. I'm glad my internal AI detector doesn't win over my curiosity to learn.

The main problem with the article is that the idea to influence backend code generation decisions via specific highlevel code constructs is mostly just mystical bullshit (some compilers do detect specific patterns - usually for bit twiddling hacks, but not on a basic level like control flow optimization). Using a highlevel language construct like "y += (x > 0) as usize;" doesn't "switch on" branchless code just becau…

And, on some architectures, y+=(x>0) is branchful!

Re: Branchless Rust: Making a Filter 4x Faster by Removing an If

#69

Post by claudetard »

bjourne wrote: post #16

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.

If your objects are large, I can see why you would compute indices first. But why do that for floats?

Re: Branchless Rust: Making a Filter 4x Faster by Removing an If

#70

Post by vips7L »

Seattle3503 wrote: post #41
aduffy wrote: post #12

Earlier quoted context omitted.

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.

Sad to see you getting voted down. But I guess both the pro-AI crowd and anti-AI crowd hate Pangram.

Sad little world we live in tbh.
Post reply on HN