6 ms·

Writing x86 SIMD using x86inc.asm (2017)

81 points by transpute 3y ago

exDM69 3y ago
There is a fourth way of writing SIMD code that is not among the three mentioned in the article: using language built-in features for SIMD. For C and C++ this is GCC vector extensions (also available in Clang), for Rust (nightly) it's std::simd. Compared to other methods, this gives portability to different CPU architectures, ability to use basic arithmetic operators (+, -, *, /), vector widths wider than the CPU supports and compiler optimizations that would be inhibited by inline assembly. It may not cover every instruction available in the CPU, but there is a zero cost fallback to intrinsics when you need a particular CPU instruction (e.g. __mm_rcp_ps). I've written a significant amount of SIMD code in C, C++ and Rust using builtins and it's quite a pleasant experience compared to other methods.
- unwind 3y ago
  Very good point, thanks! The ever-popular Mr Lemire often uses this technique, I think it's way easier to follow than straight up assembly. See for instance [1], his post about prefix-recognition in strings (not randomly chosen, it was simply the first post with code that I found when I searched for "simd"). [1]: https://lemire.me/blog/2023/07/14/recognizing-string-prefixes-with-simd-instructions/ https://lemire.me/blog/2023/07/14/recognizing-string-prefixe...
  - exDM69 3y ago
    The article you link to uses Intel intrinsics, not built-in vector extensions. Intrinsics are probably the most popular method of doing SIMD but they are not portable to other CPUs and are quite difficult to discover due to shorthand naming conventions and lack of general level documentation. Each of the Intel intrinsic functions are well documented but figuring out which ones you need out of the 600 or so available functions is not easy. Situation is worse for ARM.
    - unwind 3y ago
      Oops, that's true! I should have dug harder. Thanks for pointing that out.
    - janwas 3y ago
      I believe these drawbacks are mostly solved with our github.com/google/highway library which provides portable intrinsics, reasonably documented and grouped into categories :)
    - Galanwe 3y ago
      > Each of the Intel intrinsic functions are well documented but figuring out which ones you need out of the 600 or so available functions is not easy. So true. One of the most valuable skill to grow when using Intel intrinsics is a fluent navigation and intuition of the intrinsics library. Nowadays things are much easier though, there are a lot of indexing websites and softwares where you can query, search, find intrinsics very quickly. Intel had an interactive intrinsics doc already 10 years ago.
- taminka 3y ago
  aren’t compiler built in simd vector types practically equivalent to what the compiler would vectorise scalar code to anyway
  - huppeldepup 3y ago
    It’s been a while (10 years?) since I wrote NEON and vf code (different arch but sentiment remains) and every now and then I used to run a quick disassembly to verify that my optimisation hadn’t been undone by the compiler. The first time it happens you kinda lose faith in the compiler.
  - exDM69 3y ago
    No, compilers may be able to vectorize basic loops, but they won't for example turn four adjacent additions into a vector addition.
    - JonChesterfield 3y ago
      There's (at least) two vectorisers in LLVM. One does loops, the other acts on basic blocks. https://llvm.org/docs/Vectorizers.html#the-slp-vectorizer https://llvm.org/docs/Vectorizers.html#the-slp-vectorizer. Both really like alignment metadata on pointers. They certainly have limitations but the hit rate is reasonably good.
  - astrange 3y ago
    No, autovectorization is a lie and doesn't work. We're not stupid, we did it the way the article does it for a reason. The main problems preventing it from working are that the compiler doesn't have enough information about alignment (especially if it's intentionally unaligned) or aliasing. It tends to get things especially wrong when it autovectorizes code that was already partly hand vectorized; it ends up emitting the preludes (which correct for misalignment) twice. It does work better for languages like Fortran made for it - contrary to popular belief C is not actually a low level language and isn't that easy to optimize.
- aengelke 3y ago
  It works and is easier to read, but there's an important catch: it is not obvious when the compiler falls back to an inefficient scalar implementation that might even be less efficient than not using SIMD at all. Example: https://godbolt.org/z/McKfxjbaj https://godbolt.org/z/McKfxjbaj
  - exDM69 3y ago
    The example you show has integer division and multiplication. SSE or AVX instructions don't have an integer division instruction so neither GCC or Clang will emit SIMD code for the division. For the multiplication you need to bump up GCC to `-O3` optimization to get SIMD instruction but Clang will give the correct answer even on `-O2`. Both emit a `vpmullq` instruction. At a general level, I agree with you: when writing SIMD code you need to keep an eye on your benchmark results and/or the compiler generated assembly. Typically you're doing some optimization work when working with SIMD so keeping a close eye one the performance is a good idea anyways.
- pjmlp 3y ago
  .NET and Java (in preview) also have SIMD support.
- neonsunset 3y ago
  C# has stable cross-platform SIMD API since .NET 7 (mind you, it had x86 and ARM intrinsics even before, including SIMD, but version 7 added API unification of Vector128/256/512(8) to have a single code path for multiple platforms). It is very nice to use and produces readable(!) code.
JonChesterfield 3y ago
This turns out to be a lot of assembly macros to help write one x86 assembly. https://github.com/FFmpeg/FFmpeg/blob/master/libavutil/x86/x86inc.asm https://github.com/FFmpeg/FFmpeg/blob/master/libavutil/x86/x... The sibling comment recommending compiler intrinsics is probably the best way to go for writing SIMD code. A mixture of `<i32 x 16>` style types and intrinsics to specify instructions is a solid 90% solution compared to assembly. If you want that last 10%, I think macros are putting the emphasis in the wrong place. They're a somewhat easy way to build up a language abstraction which will work if held carefully, but I'm confident the dev experience using this abstraction when you write invalid code will be deeply confusing. I would suggest to write a parser instead of the macros. That'll tell you clearly when the syntax is invalid (though possibly not with much precision) and it'll give you a place to put semantic analysis for where valid syntax encodes nonsense. Do the equivalent of the macro expansions on the parsed tree instead of on the text. Emit asm as the "back end".
- anonymoushn 3y ago
  So far intrinsics supplemented with functions that wrap single instructions cover my needs. The thing I occasionally want to be easier is manually configurable unrolling. For example if you have some kernel that processes the input in 3 streams, or that loads 5 registers worth of input from a single stream and processes all of those in the same way, the resulting code duplication is a useless place where typos can give you a bad time. A macro system slightly different from the one C actually has could let you get rid of the duplication and just change the constant to control the unrolling.
p0nce 3y ago
Nowadays this is a fringe way to write SIMD code, if you use something like simd-everywhere you will be able to write SIMD code for ARM, x86, RISC-V... who share quite a bit of common ground. It's easy to think we can schedule instructions and spill registers better than compilers but only is some extreme cases. Assembly is also longer to write than intrinsics and harder to read, and doesn't get better over time as the compiler improves.
- astrange 3y ago
  > Assembly is also longer to write than intrinsics and harder to read, and doesn't get better over time as the compiler improves. Intel intrinsics are actually kind of horrible to read, because they use Hungarian notation which is one of those strange galapagos Microsoft ideas. One reason we used assembly is that it's easier. > It's easy to think we can schedule instructions and spill registers better than compilers but only is some extreme cases. With GCC it used to happen every time. Modern compilers do it slightly less than every time, but they will still get the memory accesses wrong. (as I said in every other comment, C doesn't have enough information about memory alignment or aliasing.)
Glacia 3y ago
It's funny reading comments here, Hackernews bros really think they're smarter than the guys who made ffmpeg/x264/x265 etc. Dunning–Kruger effect in action.
- janwas 3y ago
  FWIW I have been writing SIMD since 20+ years and worked on JPEG XL, which also contains a good bit of vector code. BTW one anecdote: a colleague mentioned what should have been a quick 20 min patch to ffmpeg took a day because it was written in assembly.
  - Glacia 3y ago
    Here is the old archived blog post where x264 team answered in the comments why they do it that way. https://web.archive.org/web/20091223024333/http://x264dev.multimedia.cx/?p=191#comments https://web.archive.org/web/20091223024333/http://x264dev.mu...
    - exDM69 3y ago
      This is dated to 2009. Probably sound advise back then. Compilers are much much better with SIMD code than they were then. Today you'll have to work real hard to beat LLVM in optimizing basic SIMD code (edit: when given SIMD code as input, see comment below). I happen to know because this "hacker news bro" has been dealing with SIMD code for longer than that.
      - kierank 3y ago
        FFmpeg code by definition is not "basic SIMD code". And it supports numerous other compilers other than LLVM.
      - jbk 3y ago
        > Today you'll have to work real hard to beat LLVM in optimizing basic SIMD code. On dav1d, we see just a 800% increase… I know it’s negligible, but…
neonsunset 3y ago
Sad to not see C# being mentioned here. It is one of the most convenient languages to write bespoke SIMD code in today. Examples: - https://github.com/dotnet/runtime/blob/main/src/libraries/System.Private.CoreLib/src/System/Buffers/Text/Base64Encoder.cs#L250-L319 https://github.com/dotnet/runtime/blob/main/src/libraries/Sy... - https://github.com/dotnet/runtime/blob/b432fc66fe59873b2b2ad584c04eaf1e4b11d611/src/libraries/System.Private.CoreLib/src/System/SearchValues/ProbabilisticMap.cs#L243-L265 https://github.com/dotnet/runtime/blob/b432fc66fe59873b2b2ad... - https://github.com/bepu/bepuphysics2/blob/05e3e8d33f5cbfd78064182313f9ad416cff9276/BepuUtilities/Collections/VectorizedSorts.cs#L24-L120 https://github.com/bepu/bepuphysics2/blob/05e3e8d33f5cbfd780... - https://github.com/U8String/U8String/blob/main/Sources/U8String/CaseConverters/U8AsciiCaseConverter.cs#L69-L90 https://github.com/U8String/U8String/blob/main/Sources/U8Str...
Const-me 3y ago
Note assembly language is OS-specific because different OSes have different ABI. Unfortunately, this is very relevant to SIMD https://learn.microsoft.com/en-us/cpp/build/x64-software-conventions?view=msvc-170#register-volatility-and-preservation https://learn.microsoft.com/en-us/cpp/build/x64-software-con... And causes real-life bugs in the software with pieces written in assembly. I think this makes assembly poor choice for writing software in modern ecosystem. Modern C and C++ compilers have SIMD intrinsics. SIMD intrinsics are OS agnostic, modern compilers follow these ABI conventions carefully. SIMD intrinsics are ISA-specific just like assembly. Unlike higher-level abstraction libraries or automatic vectorizers, SIMD intrinsics allow to match performance of the assembly.
- kierank 3y ago
  x86inc.asm takes care of the different OS ABI differences for you.
kookamamie 3y ago
Or, instead of this pretty arcane "templating" for different instruction sets, one could write some ISPC.
- astrange 3y ago
  ISPC is a better solution than autovectorization for sure, but it still wouldn't work well enough.
vkaku 3y ago
This ffmpeg stuff is great. Recently they highlighted the need [1] for next gen of low level developers, so this is a good opportunity for those who want to embrace this. Getting closer to the machine is the best way to improve speed of today's software. 1 - https://twitter.com/FFmpeg/status/1772063313452466239?s=19 https://twitter.com/FFmpeg/status/1772063313452466239?s=19
- natsch 3y ago
  While I agree with the sentiment, I also feel the reverse is true. A lot of companies are hiring specifically for AI/ML at the moment, because it's the current thing. Performance and efficiency of their applications are somehow seldom prioritized.

81 points by transpute 3y ago

There is a fourth way of writing SIMD code that is not among the three mentioned in the article: using language built-in features for SIMD. For C and C++ this is GCC vector extensions (also available in Clang), for Rust (nightly) it's std::simd. Compared to other methods, this gives portability to different CPU architectures, ability to use basic arithmetic operators (+, -, *, /), vector widths wider than the CPU supports and compiler optimizations that would be inhibited by inline assembly. It may not cover every instruction available in the CPU, but there is a zero cost fallback to intrinsics when you need a particular CPU instruction (e.g. __mm_rcp_ps). I've written a significant amount of SIMD code in C, C++ and Rust using builtins and it's quite a pleasant experience compared to other methods.

unwind 3y ago
Very good point, thanks! The ever-popular Mr Lemire often uses this technique, I think it's way easier to follow than straight up assembly. See for instance [1], his post about prefix-recognition in strings (not randomly chosen, it was simply the first post with code that I found when I searched for "simd"). [1]: https://lemire.me/blog/2023/07/14/recognizing-string-prefixes-with-simd-instructions/ https://lemire.me/blog/2023/07/14/recognizing-string-prefixe...
- exDM69 3y ago
  The article you link to uses Intel intrinsics, not built-in vector extensions. Intrinsics are probably the most popular method of doing SIMD but they are not portable to other CPUs and are quite difficult to discover due to shorthand naming conventions and lack of general level documentation. Each of the Intel intrinsic functions are well documented but figuring out which ones you need out of the 600 or so available functions is not easy. Situation is worse for ARM.
  - unwind 3y ago
    Oops, that's true! I should have dug harder. Thanks for pointing that out.
  - janwas 3y ago
    I believe these drawbacks are mostly solved with our github.com/google/highway library which provides portable intrinsics, reasonably documented and grouped into categories :)
  - Galanwe 3y ago
    > Each of the Intel intrinsic functions are well documented but figuring out which ones you need out of the 600 or so available functions is not easy. So true. One of the most valuable skill to grow when using Intel intrinsics is a fluent navigation and intuition of the intrinsics library. Nowadays things are much easier though, there are a lot of indexing websites and softwares where you can query, search, find intrinsics very quickly. Intel had an interactive intrinsics doc already 10 years ago.
taminka 3y ago
aren’t compiler built in simd vector types practically equivalent to what the compiler would vectorise scalar code to anyway
- huppeldepup 3y ago
  It’s been a while (10 years?) since I wrote NEON and vf code (different arch but sentiment remains) and every now and then I used to run a quick disassembly to verify that my optimisation hadn’t been undone by the compiler. The first time it happens you kinda lose faith in the compiler.
- exDM69 3y ago
  No, compilers may be able to vectorize basic loops, but they won't for example turn four adjacent additions into a vector addition.
  - JonChesterfield 3y ago
    There's (at least) two vectorisers in LLVM. One does loops, the other acts on basic blocks. https://llvm.org/docs/Vectorizers.html#the-slp-vectorizer https://llvm.org/docs/Vectorizers.html#the-slp-vectorizer. Both really like alignment metadata on pointers. They certainly have limitations but the hit rate is reasonably good.
- astrange 3y ago
  No, autovectorization is a lie and doesn't work. We're not stupid, we did it the way the article does it for a reason. The main problems preventing it from working are that the compiler doesn't have enough information about alignment (especially if it's intentionally unaligned) or aliasing. It tends to get things especially wrong when it autovectorizes code that was already partly hand vectorized; it ends up emitting the preludes (which correct for misalignment) twice. It does work better for languages like Fortran made for it - contrary to popular belief C is not actually a low level language and isn't that easy to optimize.
aengelke 3y ago
It works and is easier to read, but there's an important catch: it is not obvious when the compiler falls back to an inefficient scalar implementation that might even be less efficient than not using SIMD at all. Example: https://godbolt.org/z/McKfxjbaj https://godbolt.org/z/McKfxjbaj
- exDM69 3y ago
  The example you show has integer division and multiplication. SSE or AVX instructions don't have an integer division instruction so neither GCC or Clang will emit SIMD code for the division. For the multiplication you need to bump up GCC to `-O3` optimization to get SIMD instruction but Clang will give the correct answer even on `-O2`. Both emit a `vpmullq` instruction. At a general level, I agree with you: when writing SIMD code you need to keep an eye on your benchmark results and/or the compiler generated assembly. Typically you're doing some optimization work when working with SIMD so keeping a close eye one the performance is a good idea anyways.
pjmlp 3y ago
.NET and Java (in preview) also have SIMD support.
neonsunset 3y ago
C# has stable cross-platform SIMD API since .NET 7 (mind you, it had x86 and ARM intrinsics even before, including SIMD, but version 7 added API unification of Vector128/256/512(8) to have a single code path for multiple platforms). It is very nice to use and produces readable(!) code.

JonChesterfield 3y ago

This turns out to be a lot of assembly macros to help write one x86 assembly. https://github.com/FFmpeg/FFmpeg/blob/master/libavutil/x86/x86inc.asm https://github.com/FFmpeg/FFmpeg/blob/master/libavutil/x86/x... The sibling comment recommending compiler intrinsics is probably the best way to go for writing SIMD code. A mixture of `<i32 x 16>` style types and intrinsics to specify instructions is a solid 90% solution compared to assembly. If you want that last 10%, I think macros are putting the emphasis in the wrong place. They're a somewhat easy way to build up a language abstraction which will work if held carefully, but I'm confident the dev experience using this abstraction when you write invalid code will be deeply confusing. I would suggest to write a parser instead of the macros. That'll tell you clearly when the syntax is invalid (though possibly not with much precision) and it'll give you a place to put semantic analysis for where valid syntax encodes nonsense. Do the equivalent of the macro expansions on the parsed tree instead of on the text. Emit asm as the "back end".

anonymoushn 3y ago
So far intrinsics supplemented with functions that wrap single instructions cover my needs. The thing I occasionally want to be easier is manually configurable unrolling. For example if you have some kernel that processes the input in 3 streams, or that loads 5 registers worth of input from a single stream and processes all of those in the same way, the resulting code duplication is a useless place where typos can give you a bad time. A macro system slightly different from the one C actually has could let you get rid of the duplication and just change the constant to control the unrolling.

p0nce 3y ago

Nowadays this is a fringe way to write SIMD code, if you use something like simd-everywhere you will be able to write SIMD code for ARM, x86, RISC-V... who share quite a bit of common ground. It's easy to think we can schedule instructions and spill registers better than compilers but only is some extreme cases. Assembly is also longer to write than intrinsics and harder to read, and doesn't get better over time as the compiler improves.

astrange 3y ago
> Assembly is also longer to write than intrinsics and harder to read, and doesn't get better over time as the compiler improves. Intel intrinsics are actually kind of horrible to read, because they use Hungarian notation which is one of those strange galapagos Microsoft ideas. One reason we used assembly is that it's easier. > It's easy to think we can schedule instructions and spill registers better than compilers but only is some extreme cases. With GCC it used to happen every time. Modern compilers do it slightly less than every time, but they will still get the memory accesses wrong. (as I said in every other comment, C doesn't have enough information about memory alignment or aliasing.)

Glacia 3y ago

It's funny reading comments here, Hackernews bros really think they're smarter than the guys who made ffmpeg/x264/x265 etc. Dunning–Kruger effect in action.

janwas 3y ago
FWIW I have been writing SIMD since 20+ years and worked on JPEG XL, which also contains a good bit of vector code. BTW one anecdote: a colleague mentioned what should have been a quick 20 min patch to ffmpeg took a day because it was written in assembly.
- Glacia 3y ago
  Here is the old archived blog post where x264 team answered in the comments why they do it that way. https://web.archive.org/web/20091223024333/http://x264dev.multimedia.cx/?p=191#comments https://web.archive.org/web/20091223024333/http://x264dev.mu...
  - exDM69 3y ago
    This is dated to 2009. Probably sound advise back then. Compilers are much much better with SIMD code than they were then. Today you'll have to work real hard to beat LLVM in optimizing basic SIMD code (edit: when given SIMD code as input, see comment below). I happen to know because this "hacker news bro" has been dealing with SIMD code for longer than that.
    - kierank 3y ago
      FFmpeg code by definition is not "basic SIMD code". And it supports numerous other compilers other than LLVM.
    - jbk 3y ago
      > Today you'll have to work real hard to beat LLVM in optimizing basic SIMD code. On dav1d, we see just a 800% increase… I know it’s negligible, but…

neonsunset 3y ago

Sad to not see C# being mentioned here. It is one of the most convenient languages to write bespoke SIMD code in today. Examples: - https://github.com/dotnet/runtime/blob/main/src/libraries/System.Private.CoreLib/src/System/Buffers/Text/Base64Encoder.cs#L250-L319 https://github.com/dotnet/runtime/blob/main/src/libraries/Sy... - https://github.com/dotnet/runtime/blob/b432fc66fe59873b2b2ad584c04eaf1e4b11d611/src/libraries/System.Private.CoreLib/src/System/SearchValues/ProbabilisticMap.cs#L243-L265 https://github.com/dotnet/runtime/blob/b432fc66fe59873b2b2ad... - https://github.com/bepu/bepuphysics2/blob/05e3e8d33f5cbfd78064182313f9ad416cff9276/BepuUtilities/Collections/VectorizedSorts.cs#L24-L120 https://github.com/bepu/bepuphysics2/blob/05e3e8d33f5cbfd780... - https://github.com/U8String/U8String/blob/main/Sources/U8String/CaseConverters/U8AsciiCaseConverter.cs#L69-L90 https://github.com/U8String/U8String/blob/main/Sources/U8Str...

Const-me 3y ago

Note assembly language is OS-specific because different OSes have different ABI. Unfortunately, this is very relevant to SIMD https://learn.microsoft.com/en-us/cpp/build/x64-software-conventions?view=msvc-170#register-volatility-and-preservation https://learn.microsoft.com/en-us/cpp/build/x64-software-con... And causes real-life bugs in the software with pieces written in assembly. I think this makes assembly poor choice for writing software in modern ecosystem. Modern C and C++ compilers have SIMD intrinsics. SIMD intrinsics are OS agnostic, modern compilers follow these ABI conventions carefully. SIMD intrinsics are ISA-specific just like assembly. Unlike higher-level abstraction libraries or automatic vectorizers, SIMD intrinsics allow to match performance of the assembly.

kierank 3y ago
x86inc.asm takes care of the different OS ABI differences for you.

kookamamie 3y ago

Or, instead of this pretty arcane "templating" for different instruction sets, one could write some ISPC.

astrange 3y ago
ISPC is a better solution than autovectorization for sure, but it still wouldn't work well enough.

vkaku 3y ago

This ffmpeg stuff is great. Recently they highlighted the need [1] for next gen of low level developers, so this is a good opportunity for those who want to embrace this. Getting closer to the machine is the best way to improve speed of today's software. 1 - https://twitter.com/FFmpeg/status/1772063313452466239?s=19 https://twitter.com/FFmpeg/status/1772063313452466239?s=19

natsch 3y ago
While I agree with the sentiment, I also feel the reverse is true. A lot of companies are hiring specifically for AI/ML at the moment, because it's the current thing. Performance and efficiency of their applications are somehow seldom prioritized.