News for hackers. Stuff that matters.
Re:Static search trees: 40x faster than binary search by skrebbel on Wednesday January 01, 2025 @10:47AM (#42566702)
Nah just the final bits, stuff like `Simd::<u32, 8>::splat(q)`, I'm not sure what splatting is or how Rust's Simd library works or, admittedly, how SIMD works in detail at all. So eg I'm not sure what that 8 is doing there in the type parameters, details like that. Maybe this isn't a Rust thing but a SIMD thing, btw, I don't know much Rust but I also never wrote any SIMD code ever. I don't know how the article could be clearer, IMO once you go into the deep nitty gritty optimization stuff you just gotta assume the reader knows the tools you're using. I'm OK with dropping out halfway cause the core idea is there even before you squeeze out all the perf.
Re:Static search trees: 40x faster than binary search by burntsushi on Wednesday January 01, 2025 @11:13AM (#42566912)
`Simd::<u32, 8>` is describing a vector with 8 lanes, where the width of each lane is 32-bits. For targets that support it, that should get you a 256-bit register.

The `splat(q)` constructor is just saying, "populate each lane with `q`." That is, the value is "splatted" across every lane in the vector.

The main idea of SIMD is simple: you represent multiple points of data in the same register and use specialized CPU instructions to operate on those points simultaneously. The difficulty of SIMD is coming up with clever algorithms that use the available instructions in an efficient way.

Re:Static search trees: 40x faster than binary search by skrebbel on Wednesday January 01, 2025 @11:49AM (#42567177)
Ahh right, I've been doing too much TypeScript lately. I thought a type parameter couldn't impact behavior but only typechecking but clearly in Rust (like in C++) it can. Thanks for the explanation!

Ah so splat is like a memset for the entire vector to the same value. OK makes sense, I bet that wasn't actually a Rust-ism at all, just basic SIMD lingo I didn't know. Thanks again!

Re:Static search trees: 40x faster than binary search by shawn_w on Wednesday January 01, 2025 @11:30PM (#42571640)
It's the Intel intrinsic `_mm256_set1_epi32()` except with an amusing name. Got to give Rust the win here.
Re:Static search trees: 40x faster than binary search by skrebbel on Thursday January 02, 2025 @03:08PM (#42578265)
wow yeah, i way prefer Rust's notation there! but i assume you could make a similar zero-cost abstraction with some mildly crazy C++ template programming.
Re:Static search trees: 40x faster than binary search by bennythomsson on Wednesday January 01, 2025 @12:03PM (#42567308)
Nice to see other real experts (and a bit of celebrities) in here.

(For the uninitiated: Burntsushi of ripgrep fame.)

Re:Static search trees: 40x faster than binary search by skrebbel on Wednesday January 01, 2025 @12:54PM (#42567700)
yeah tbh i was a bit starstruck that burntsushi would reply to my comment explaining what i assume is utter SIMD basics. that must be how swifties feel when she (or, likelier, her PR drones) click "like" on their insta comments.
Re:Static search trees: 40x faster than binary search by freeopinion on Wednesday January 01, 2025 @04:44PM (#42569577)
Does burntsushi have PR drones (who can explain SIMD)? :)