10 ms·

The messy reality of SIMD (vector) functions

120 points by mfiguiere 1y ago

kookamamie 1y ago
I don't think the native C++, even when bundled with OMP, goes far enough. In my experience, ISPC and Google's Highway project lead to better results in practice - this mostly due to their dynamic dispatching features.
- William_BB 1y ago
  Could you elaborate on the dynamic dispatching features a bit more? Is that for portability?
  - camel-cdr 1y ago
    Here is an example using google highway: https://godbolt.org/z/Y8vsonTb8 https://godbolt.org/z/Y8vsonTb8 See how the code has only been written once, but multiple versions of the same functions where generated targeting different hardware features (e.g. SSE, AVX, AVX512). Then `HWY_DYNAMIC_DISPATCH` can be used to dynamically call the fastest one matching your CPU at runtime.
    - William_BB 1y ago
      Thank you so much, this explains it well. I was initially afraid that the dispatch would be costly, but from what I understand it's (almost) zero cost after the first call. I only code for x86 with vectorclass library, so I never had to worry about portability. In practice, is it really possible to write generic SIMD code like the example using Highway? Or could you often find optimization opportunities if you targeted a particular architecture?
      - ashvardanian 1y ago
        You can go quite far with such libraries if you only perform data-parallel numerics on the CPU. However, if you work on complex algorithms or exotic data structures, there's almost always more upside in avoiding them and writing specialized code for each platform of interest.
        janwas 1y ago
        I don't understand why it helps to "avoid them" entirely. For the (in my experience) >90% of shared code, we can gain the convenience of the wrapper library. For the rest, Highway allows target-specific specializations amidst your otherwise portable code: `#if HWY_TARGET == HWY_AVX2 ...`
    - jeffreygoesto 1y ago
      Nice. First time that I saw this dynamic dispatch was in FFTW.
  - ashvardanian 1y ago
    Here's an explanation from one of my repos: <https://github.com/ashvardanian/simsimd?tab=readme-ov-file#dynamic-dispatch https://github.com/ashvardanian/simsimd?tab=readme-ov-file#d...>
exDM69 1y ago
This right here illustrates why I think there should be better first class SIMD in languages and why intrinsics are limited. When using GCC/clang SIMD extensions in C (or Rust nightly), the implementation of sin4f and sin8f are line by line equal, with the exception of types. You can work around this with templates/generics. The sin function is entirely basic arithmetic operations, no fancy instructions are needed (at least for the "computer graphics quality" 32 bit sine function I am using). Contrast this with intrinsics where the programmer needs to explicitly choose the mm128 or mm256 instruction even for trivial stuff like addition and other arithmetic. Similarly, a 4x4 matrix multiplication function is the exact same code for 64 bit double and 32 bit float if you're using built in SIMD. A bit of generics and no duplication is needed. Where as intrinsics again needs two separate implementations. I understand that there are cases where intrinsics are required, or can deliver better performance but both C/C++ and Rust have zero cost fallback to intrinsics. You can "convert" between f32x4 and mm128 at zero cost (no instructions emitted, just compiler type information). I do use some intrinsics in my SIMD code this way (rsqrt, rcp, ...). The CPU specific code is just a few percent of the overall lines of code, and that's for Arm and x86 combined. The killer feature is that my code will compile into x86_64/SSE and Aarch64/neon. And I can use wider vectors than the CPU actually supports, the compiler knows how to break it down to what the target CPU supports. I'm hoping that Rust std::simd would get stabilized soon, I've used it for many years and it works great. And when it doesn't I have a zero cost fallback to intrinsics. Some very respected people have the opinion that std::simd or its C equivalent suffer from a "least common denominator problem". I don't disagree with the issue but I don't think it really matters when we have a zero cost fallback available.
- camel-cdr 1y ago
  My personal gripe with Rust's std::simd in its current form is that it makes writing portable SIMD hard while making non-portable SIMD easy. [0] > the implementation of sin4f and sin8f are line by line equal, with the exception of types. You can work around this with templates/generics This is true, I think most SIMD algorithms can be written in such a vector length-agnostic way, however almost all code using std::simd specifies a specific lane count instead of using the native vector length. This is because the API favors the use of fixed-size types (e.g. f32x4), which are exclusively used in all documentation and example code. If I search github for `f32x4 language:Rust` I get 6.4k results, with `"Simd<f32," language:Rust NOT "Simd<f32, 2" NOT "Simd<f32, 4" NOT "Simd<f32, 8"` I get 209. I'm not even aware of a way to detect the native vector length using std::simd. You have to use the target-feature or multiversion crate, as shown as the last part of the rust-simd-book [1]. Well, kind of like that, because their suggestion using "suggested_vector_width", which doesn't exist. I could only find a suggested_simd_width. Searching for "suggested_simd_width language:Rust", we are now down to 8 results, 3 of which are from the target-feature/multiversion crates. --- What I'm trying to say is that, while being able to specify a fixed SIMD width can be useful, the encouraged default should be "give me a SIMD vector of the specified type corresponding to the SIMD register size". If your problem can only be solved with a specific vector length, great, then hard-code the lane count, but otherwise don't. See [0] for more examples of this. [0] https://github.com/rust-lang/portable-simd/issues/364#issuecomment-2953264682 https://github.com/rust-lang/portable-simd/issues/364#issuec... [1] https://calebzulawski.github.io/rust-simd-book/4.2-native-vector-width.html https://calebzulawski.github.io/rust-simd-book/4.2-native-ve...
dwattttt 1y ago
> Function calls also have that negative property that the compiler doesn’t know what happens after calling them so it needs to assume the worst happens. And by the worst, it has to assume that the function can change any memory location and optimize for such a case. So it omits many useful compiler optimizations. This is not the case in C. It might be technically possible for a function to modify any memory, but it wouldn't be legal, and compilers don't need to optimise for the illegal cases.
- RossBencina 1y ago
  Sounds like the author hasn't heard of full program optimisation. EDIT: except they explicitly mention LTO near the end.
  - deleted 1y ago
    [deleted]
mattmaynes 1y ago
This is where the power and expressiveness of kdb+ shines. It has SIMD primitives out of the box and can optimize your code based on data types to take advantage of it. https://kx.com/blog/what-makes-time-series-database-kdb-so-fast/ https://kx.com/blog/what-makes-time-series-database-kdb-so-f...
- MangoToupe 1y ago
  Time series is vector processing on easy mode, though. The hard part is applying SIMD to problems that aren't shaped to be easily processed in parallel.
  - jgalt212 1y ago
    Fine. What's canonical or most basic example of where SIMD should be applied, but isn't because it's too tricky to do so? In our shop, we never look to vectorize any function or process unless it's called inside a loop many times.
    - MangoToupe 1y ago
      > What's canonical or most basic example of where SIMD should be applied, but isn't because it's too tricky to do so? There is none. That's a contradiction in terms. SIMD either fits the shape or it doesn't.
      - krapht 1y ago
        Variable length parallelism is hard. You can go to highload.fun (SIMD competition site) for problems that are only parallelized after significant effort. Try problem #1, parsing numbers.
    - ashvardanian 1y ago
      Text processing. Loading/branching/storing content 1 byte at a time is the CPUs worst nightmare, but most text processing is quite tricky in SIMD.
deleted 1y ago
[deleted]
fancyfredbot 1y ago
CUDA got writing SIMD functions right. You never have to say "_m1024ps" in CUDA, you just say float. CUDA has been a huge success but somehow nobody has really copied this paradigm. It's just weird.
- smallmancontrov 1y ago
  Yes!!! 20 years ago, it was extremely obvious to anyone who had to write forward/backward compatible parallelism that the-thing-nvidia-calls-SIMT was the correct approach. I thought CPU hardware manufacturers and language/compiler writers were so excessively stubborn that it would take them a decade to catch up. I was wrong. 20 years on, they still refuse to copy what works. They search every corner of the earth for a clue, from the sulfur vents at the bottom of the ocean to tallest mountains, all very impressive as feats of exploration -- but they are still suffering for want of a clue when clue city is right there next to them, bustling with happy successful inhabitants, and they refuse to look at it. Look, guys, I'm glad you gave a chance to alternatives, sometimes they just need a bit of love to bloom, but you gave them that love, they didn't bloom, and it's time to move on. Do what works and spend your creative energy on a different problem, of which there are plenty.
  - vlovich123 1y ago
    Because SIMT is not a general programming framework like CPUs are. It’s a technique for a dedicated accelerator for a specific kind of problem. SIMD on the other hand lets you get meaningful speed up inline with traditional code.
    - smallmancontrov 1y ago
      No no no! The programming model "meets you where you are" in exactly the way that an auto-vectorizer does. You write unconstrained single-threaded code, the compiler tries to make it parallel, and if it fails your code still works, just slowly. The difference is a few abstractions and social contract tweaks to make the auto-vectorizer reliable and easy to think about. These tweaks "smell like" hacks, but CPU folks have spent 20 years trying to do better and their auto-vectorizers are still failing at the basics so it's past time to copy what works and move on.
forrestthewoods 1y ago
> Not many compilers support vector functions Hrm. Anyone who has spent time writing SIMD optimizations know not to trust the compiler. If you want to write SIMD then… just use intrinsics? It’s a bit annoying to create a wrapper that supports x64 SSE/AVX and also Arm NEON. But that’s what we’ve been doing for decades.
- janwas 1y ago
  Mature such wrappers exist, for example our Highway library :)
kragen 1y ago
This is pretty good stuff. I've only done the barest minimum of SIMD programming, so things like the variable/uniform/linear trichotomy and the discussion of how OpenMP relates to GCC function attributes are very valuable to me.

120 points by mfiguiere 1y ago

I don't think the native C++, even when bundled with OMP, goes far enough. In my experience, ISPC and Google's Highway project lead to better results in practice - this mostly due to their dynamic dispatching features.

William_BB 1y ago
Could you elaborate on the dynamic dispatching features a bit more? Is that for portability?
- camel-cdr 1y ago
  Here is an example using google highway: https://godbolt.org/z/Y8vsonTb8 https://godbolt.org/z/Y8vsonTb8 See how the code has only been written once, but multiple versions of the same functions where generated targeting different hardware features (e.g. SSE, AVX, AVX512). Then `HWY_DYNAMIC_DISPATCH` can be used to dynamically call the fastest one matching your CPU at runtime.
  - William_BB 1y ago
    Thank you so much, this explains it well. I was initially afraid that the dispatch would be costly, but from what I understand it's (almost) zero cost after the first call. I only code for x86 with vectorclass library, so I never had to worry about portability. In practice, is it really possible to write generic SIMD code like the example using Highway? Or could you often find optimization opportunities if you targeted a particular architecture?
    - ashvardanian 1y ago
      You can go quite far with such libraries if you only perform data-parallel numerics on the CPU. However, if you work on complex algorithms or exotic data structures, there's almost always more upside in avoiding them and writing specialized code for each platform of interest.
      - janwas 1y ago
        I don't understand why it helps to "avoid them" entirely. For the (in my experience) >90% of shared code, we can gain the convenience of the wrapper library. For the rest, Highway allows target-specific specializations amidst your otherwise portable code: `#if HWY_TARGET == HWY_AVX2 ...`
  - jeffreygoesto 1y ago
    Nice. First time that I saw this dynamic dispatch was in FFTW.
- ashvardanian 1y ago
  Here's an explanation from one of my repos: <https://github.com/ashvardanian/simsimd?tab=readme-ov-file#dynamic-dispatch https://github.com/ashvardanian/simsimd?tab=readme-ov-file#d...>

exDM69 1y ago

This right here illustrates why I think there should be better first class SIMD in languages and why intrinsics are limited. When using GCC/clang SIMD extensions in C (or Rust nightly), the implementation of sin4f and sin8f are line by line equal, with the exception of types. You can work around this with templates/generics. The sin function is entirely basic arithmetic operations, no fancy instructions are needed (at least for the "computer graphics quality" 32 bit sine function I am using). Contrast this with intrinsics where the programmer needs to explicitly choose the mm128 or mm256 instruction even for trivial stuff like addition and other arithmetic. Similarly, a 4x4 matrix multiplication function is the exact same code for 64 bit double and 32 bit float if you're using built in SIMD. A bit of generics and no duplication is needed. Where as intrinsics again needs two separate implementations. I understand that there are cases where intrinsics are required, or can deliver better performance but both C/C++ and Rust have zero cost fallback to intrinsics. You can "convert" between f32x4 and mm128 at zero cost (no instructions emitted, just compiler type information). I do use some intrinsics in my SIMD code this way (rsqrt, rcp, ...). The CPU specific code is just a few percent of the overall lines of code, and that's for Arm and x86 combined. The killer feature is that my code will compile into x86_64/SSE and Aarch64/neon. And I can use wider vectors than the CPU actually supports, the compiler knows how to break it down to what the target CPU supports. I'm hoping that Rust std::simd would get stabilized soon, I've used it for many years and it works great. And when it doesn't I have a zero cost fallback to intrinsics. Some very respected people have the opinion that std::simd or its C equivalent suffer from a "least common denominator problem". I don't disagree with the issue but I don't think it really matters when we have a zero cost fallback available.

camel-cdr 1y ago
My personal gripe with Rust's std::simd in its current form is that it makes writing portable SIMD hard while making non-portable SIMD easy. [0] > the implementation of sin4f and sin8f are line by line equal, with the exception of types. You can work around this with templates/generics This is true, I think most SIMD algorithms can be written in such a vector length-agnostic way, however almost all code using std::simd specifies a specific lane count instead of using the native vector length. This is because the API favors the use of fixed-size types (e.g. f32x4), which are exclusively used in all documentation and example code. If I search github for `f32x4 language:Rust` I get 6.4k results, with `"Simd<f32," language:Rust NOT "Simd<f32, 2" NOT "Simd<f32, 4" NOT "Simd<f32, 8"` I get 209. I'm not even aware of a way to detect the native vector length using std::simd. You have to use the target-feature or multiversion crate, as shown as the last part of the rust-simd-book [1]. Well, kind of like that, because their suggestion using "suggested_vector_width", which doesn't exist. I could only find a suggested_simd_width. Searching for "suggested_simd_width language:Rust", we are now down to 8 results, 3 of which are from the target-feature/multiversion crates. --- What I'm trying to say is that, while being able to specify a fixed SIMD width can be useful, the encouraged default should be "give me a SIMD vector of the specified type corresponding to the SIMD register size". If your problem can only be solved with a specific vector length, great, then hard-code the lane count, but otherwise don't. See [0] for more examples of this. [0] https://github.com/rust-lang/portable-simd/issues/364#issuecomment-2953264682 https://github.com/rust-lang/portable-simd/issues/364#issuec... [1] https://calebzulawski.github.io/rust-simd-book/4.2-native-vector-width.html https://calebzulawski.github.io/rust-simd-book/4.2-native-ve...

dwattttt 1y ago

> Function calls also have that negative property that the compiler doesn’t know what happens after calling them so it needs to assume the worst happens. And by the worst, it has to assume that the function can change any memory location and optimize for such a case. So it omits many useful compiler optimizations. This is not the case in C. It might be technically possible for a function to modify any memory, but it wouldn't be legal, and compilers don't need to optimise for the illegal cases.

RossBencina 1y ago
Sounds like the author hasn't heard of full program optimisation. EDIT: except they explicitly mention LTO near the end.
- deleted 1y ago
  [deleted]

mattmaynes 1y ago

This is where the power and expressiveness of kdb+ shines. It has SIMD primitives out of the box and can optimize your code based on data types to take advantage of it. https://kx.com/blog/what-makes-time-series-database-kdb-so-fast/ https://kx.com/blog/what-makes-time-series-database-kdb-so-f...

MangoToupe 1y ago
Time series is vector processing on easy mode, though. The hard part is applying SIMD to problems that aren't shaped to be easily processed in parallel.
- jgalt212 1y ago
  Fine. What's canonical or most basic example of where SIMD should be applied, but isn't because it's too tricky to do so? In our shop, we never look to vectorize any function or process unless it's called inside a loop many times.
  - MangoToupe 1y ago
    > What's canonical or most basic example of where SIMD should be applied, but isn't because it's too tricky to do so? There is none. That's a contradiction in terms. SIMD either fits the shape or it doesn't.
    - krapht 1y ago
      Variable length parallelism is hard. You can go to highload.fun (SIMD competition site) for problems that are only parallelized after significant effort. Try problem #1, parsing numbers.
  - ashvardanian 1y ago
    Text processing. Loading/branching/storing content 1 byte at a time is the CPUs worst nightmare, but most text processing is quite tricky in SIMD.

deleted 1y ago

[deleted]

fancyfredbot 1y ago

CUDA got writing SIMD functions right. You never have to say "_m1024ps" in CUDA, you just say float. CUDA has been a huge success but somehow nobody has really copied this paradigm. It's just weird.

smallmancontrov 1y ago
Yes!!! 20 years ago, it was extremely obvious to anyone who had to write forward/backward compatible parallelism that the-thing-nvidia-calls-SIMT was the correct approach. I thought CPU hardware manufacturers and language/compiler writers were so excessively stubborn that it would take them a decade to catch up. I was wrong. 20 years on, they still refuse to copy what works. They search every corner of the earth for a clue, from the sulfur vents at the bottom of the ocean to tallest mountains, all very impressive as feats of exploration -- but they are still suffering for want of a clue when clue city is right there next to them, bustling with happy successful inhabitants, and they refuse to look at it. Look, guys, I'm glad you gave a chance to alternatives, sometimes they just need a bit of love to bloom, but you gave them that love, they didn't bloom, and it's time to move on. Do what works and spend your creative energy on a different problem, of which there are plenty.
- vlovich123 1y ago
  Because SIMT is not a general programming framework like CPUs are. It’s a technique for a dedicated accelerator for a specific kind of problem. SIMD on the other hand lets you get meaningful speed up inline with traditional code.
  - smallmancontrov 1y ago
    No no no! The programming model "meets you where you are" in exactly the way that an auto-vectorizer does. You write unconstrained single-threaded code, the compiler tries to make it parallel, and if it fails your code still works, just slowly. The difference is a few abstractions and social contract tweaks to make the auto-vectorizer reliable and easy to think about. These tweaks "smell like" hacks, but CPU folks have spent 20 years trying to do better and their auto-vectorizers are still failing at the basics so it's past time to copy what works and move on.

forrestthewoods 1y ago

> Not many compilers support vector functions Hrm. Anyone who has spent time writing SIMD optimizations know not to trust the compiler. If you want to write SIMD then… just use intrinsics? It’s a bit annoying to create a wrapper that supports x64 SSE/AVX and also Arm NEON. But that’s what we’ve been doing for decades.

janwas 1y ago
Mature such wrappers exist, for example our Highway library :)

kragen 1y ago

This is pretty good stuff. I've only done the barest minimum of SIMD programming, so things like the variable/uniform/linear trichotomy and the discussion of how OpenMP relates to GCC function attributes are very valuable to me.