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

21–30 of 124 posts

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

#21

Post by vlovich123 »

nvme0n1p1 wrote: post #5
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…

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.

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.

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

#22

Post by marsven_422 »

anematode wrote: post #13

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: pub fn filter_compress(input: &[f64], threshold: f64) -> Vec { use std::arch::x86_…

[dead]

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

#23

Post by ashton314 »

anematode wrote: post #13

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: pub fn filter_compress(input: &[f64], threshold: f64) -> Vec { use std::arch::x86_…

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!

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

#24

Post by [deleted] »

gblargg wrote: post #18
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.

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.

[deleted]

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

#25

Post by toast0 »

phire wrote: post #15
nvme0n1p1 wrote: post #5

Earlier quoted context omitted.

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…

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

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

#26

Post by dxdm »

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.

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.

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

#29

Post by altmanaltman »

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.

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!
Post reply on HN