5 ms·

Rust has had a stable SIMD vector API[1] for a long time. But, it's architecture specific. The portable API[2] isn't stable yet, but you probably can't use the

Rust has had a stable SIMD vector API[1] for a long time. But, it's architecture specific. The portable API[2] isn't stable yet, but you probably can't use the portable API for some of the more exotic uses of SIMD anyway. Indeed, that's true in .NET's case too[3]. So .NET has to rely on "manually vectorized with intrisics for each individual platform" as well. Rust does all this SIMD too. It just isn't in the standard library. But the regex crate does it. Indeed, this is where .NET got its SIMD approach for multiple substring search from in the first place[4]. ;-) You're right that Rust's standard library is conservatively vectorized though[5]. The main thing blocking this isn't the lack of SIMD availability. It's more about how the standard library is internally structured, and the fact that things like substring search are not actually defined in `std` directly, but rather, in `core`. There are plans to fix this[6]. With all that said, I wouldn't necessarily disagree with the broader point in this thread. .NET's regex engine performance is quite impressive[7]. (And I still have to merge the PR updating to .NET 8.) I'm really only replying here to correct more narrow points. [1]: https://doc.rust-lang.org/std/arch/index.html https://doc.rust-lang.org/std/arch/index.html [2]: https://doc.rust-lang.org/std/simd/index.html https://doc.rust-lang.org/std/simd/index.html [3]: https://github.com/dotnet/runtime/blob/72fae0073b35a404f03c3b60224fc13a775ef364/src/libraries/System.Private.CoreLib/src/System/SearchValues/Strings/Helpers/TeddyHelper.cs https://github.com/dotnet/runtime/blob/72fae0073b35a404f03c3... [4]: https://github.com/dotnet/runtime/pull/88394#issuecomment-1621703161 https://github.com/dotnet/runtime/pull/88394#issuecomment-16... [5]: https://github.com/BurntSushi/memchr#why-is-the-standard-librarys-substring-search-so-much-slower https://github.com/BurntSushi/memchr#why-is-the-standard-lib... [6]: https://github.com/rust-lang/rfcs/pull/3469 https://github.com/rust-lang/rfcs/pull/3469 [7]: https://github.com/BurntSushi/rebar#summary https://github.com/BurntSushi/rebar#summary

neonsunset 3y ago
Getting clarifications from the OG himself! :) Indeed, I meant to say "portable SIMD API" but it got lost somewhere in the stream of consciousness - sorry. As for limitations of using such APIs in the standard library - in case of .NET platform-specific paths mainly exist for the following reasons: - To achieve optimal codegen with more specific instructions - To account for platform differences that are not expressible through crossplat vectors (vpternlog on x86, tbl/tbx on Aarch64) - The code was written before crossplat API was available and has not been updated yet Another aspect of such API is that all intrinsics still consume the same unified group of Vector128/256/512<T> so that writing scenario-specific helper is still relatively easy, which is what bits of standard library often opt into.
- burntsushi 3y ago
  Right. I pointed it out because it isn't just about having portable SIMD that makes SIMD optimizations possible. Therefore, the lack of one in Rust doesn't have much explanatory power for why Rust's standard library doesn't contain SIMD. (It does have some.) It's good enough for things like memchr (well, kinda, NEON doesn't have `movemask`[1,2]), but not for things like Teddy that do multi-substring search. When you do want to write SIMD across platforms, it's not too hard to define your own bespoke portable API[3]. I'm basically just pointing out that a portable API is somewhat oversold, because it's not uncommon to need to abandon it, especially for string related ops that make creative use of ISA extensions. And additionally, that Rust unfortunately has other reasons for why std doesn't make as much use of SIMD as it probably should (the core/alloc/std split). [1]: https://github.com/BurntSushi/memchr/blob/c6b885b870b6f1b9bfae2de482e1264d6c7aa040/src/vector.rs#L326-L333 https://github.com/BurntSushi/memchr/blob/c6b885b870b6f1b9bf... [2]: https://github.com/BurntSushi/memchr/blob/c6b885b870b6f1b9bfae2de482e1264d6c7aa040/src/vector.rs#L363-L379 https://github.com/BurntSushi/memchr/blob/c6b885b870b6f1b9bf... [3]: https://github.com/BurntSushi/aho-corasick/blob/f227162f7c56b3f28e9dd69a655316af0107b29b/src/packed/vector.rs https://github.com/BurntSushi/aho-corasick/blob/f227162f7c56...
  - neonsunset 3y ago
    Heh, movemask keeps coming back. Rather than emulating it, it appears to be more efficient to separately handle IndexOfMatch, LastIndexOfMatch and GetMatchCount scenarios it is used for most of the time: - https://github.com/dotnet/runtime/pull/94472/files#diff-58242a9637faae8972d2b49c63a1a17a582b4198f9e0bed27b6615cb47f068fdR3061-R3069 https://github.com/dotnet/runtime/pull/94472/files#diff-5824... (it's closed for now but I'm hoping to get back to it at some point) - https://github.com/jprochazk/tmi-rs/blob/ac3ce6aee8bbe038a983ed9ce41b67c34ce3e4c9/src/irc/simd/arm_neon.rs#L236 https://github.com/jprochazk/tmi-rs/blob/ac3ce6aee8bbe038a98... It can account for good 30% performance variance depending on the use case (on Apple's M-series cores).
    - burntsushi 3y ago
      That's what the `memchr` crate does. It uses `vshrn` just like in your links. And vpmaxq before even bothering with vshrn: https://github.com/BurntSushi/memchr/blob/c6b885b870b6f1b9bfae2de482e1264d6c7aa040/src/vector.rs#L357-L360 https://github.com/BurntSushi/memchr/blob/c6b885b870b6f1b9bf...

neonsunset 3y ago

Getting clarifications from the OG himself! :) Indeed, I meant to say "portable SIMD API" but it got lost somewhere in the stream of consciousness - sorry. As for limitations of using such APIs in the standard library - in case of .NET platform-specific paths mainly exist for the following reasons: - To achieve optimal codegen with more specific instructions - To account for platform differences that are not expressible through crossplat vectors (vpternlog on x86, tbl/tbx on Aarch64) - The code was written before crossplat API was available and has not been updated yet Another aspect of such API is that all intrinsics still consume the same unified group of Vector128/256/512<T> so that writing scenario-specific helper is still relatively easy, which is what bits of standard library often opt into.

burntsushi 3y ago
Right. I pointed it out because it isn't just about having portable SIMD that makes SIMD optimizations possible. Therefore, the lack of one in Rust doesn't have much explanatory power for why Rust's standard library doesn't contain SIMD. (It does have some.) It's good enough for things like memchr (well, kinda, NEON doesn't have `movemask`[1,2]), but not for things like Teddy that do multi-substring search. When you do want to write SIMD across platforms, it's not too hard to define your own bespoke portable API[3]. I'm basically just pointing out that a portable API is somewhat oversold, because it's not uncommon to need to abandon it, especially for string related ops that make creative use of ISA extensions. And additionally, that Rust unfortunately has other reasons for why std doesn't make as much use of SIMD as it probably should (the core/alloc/std split). [1]: https://github.com/BurntSushi/memchr/blob/c6b885b870b6f1b9bfae2de482e1264d6c7aa040/src/vector.rs#L326-L333 https://github.com/BurntSushi/memchr/blob/c6b885b870b6f1b9bf... [2]: https://github.com/BurntSushi/memchr/blob/c6b885b870b6f1b9bfae2de482e1264d6c7aa040/src/vector.rs#L363-L379 https://github.com/BurntSushi/memchr/blob/c6b885b870b6f1b9bf... [3]: https://github.com/BurntSushi/aho-corasick/blob/f227162f7c56b3f28e9dd69a655316af0107b29b/src/packed/vector.rs https://github.com/BurntSushi/aho-corasick/blob/f227162f7c56...
- neonsunset 3y ago
  Heh, movemask keeps coming back. Rather than emulating it, it appears to be more efficient to separately handle IndexOfMatch, LastIndexOfMatch and GetMatchCount scenarios it is used for most of the time: - https://github.com/dotnet/runtime/pull/94472/files#diff-58242a9637faae8972d2b49c63a1a17a582b4198f9e0bed27b6615cb47f068fdR3061-R3069 https://github.com/dotnet/runtime/pull/94472/files#diff-5824... (it's closed for now but I'm hoping to get back to it at some point) - https://github.com/jprochazk/tmi-rs/blob/ac3ce6aee8bbe038a983ed9ce41b67c34ce3e4c9/src/irc/simd/arm_neon.rs#L236 https://github.com/jprochazk/tmi-rs/blob/ac3ce6aee8bbe038a98... It can account for good 30% performance variance depending on the use case (on Apple's M-series cores).
  - burntsushi 3y ago
    That's what the `memchr` crate does. It uses `vshrn` just like in your links. And vpmaxq before even bothering with vshrn: https://github.com/BurntSushi/memchr/blob/c6b885b870b6f1b9bfae2de482e1264d6c7aa040/src/vector.rs#L357-L360 https://github.com/BurntSushi/memchr/blob/c6b885b870b6f1b9bf...