7 ms·

SIMD for C++ Developers [pdf]

129 points by Const-me 6y ago

Const-me 6y ago
Updated my article from 2019. It’s not limited to C++, equally good for C. Over time, the support slowly arrives to other languages too, like C#: https://docs.microsoft.com/en-us/dotnet/api/system.runtime.intrinsics.x86.sse?view=net-5.0 https://docs.microsoft.com/en-us/dotnet/api/system.runtime.i... https://docs.microsoft.com/en-us/dotnet/api/system.runtime.intrinsics.x86.avx?view=net-5.0 https://docs.microsoft.com/en-us/dotnet/api/system.runtime.i...
- bobthedino 6y ago
  SIMD support is also currently in development for Java: https://openjdk.java.net/jeps/338 https://openjdk.java.net/jeps/338
- smhenderson 6y ago
  It's a really well written article, thank you for the work!
- gameswithgo 6y ago
  Rust as well, and the intrinsics are identically named so your tutorial is good for rust as well.
- pjmlp 6y ago
  And D as well, although the support varies a bit across all three backends.
  - MaxBarraclough 6y ago
    How about other languages that use GCC/LLVM, like Zig, Rust, Ada, or for that matter FORTRAN?
    - pjmlp 6y ago
      Fortran for sure, given its use in HPC and GPGPU programming since it exits (we no longer use all caps for its name :) ). Only GNAT Ada uses GCC/LLVM, the other surviving Ada vendors have their own compilers, no idea how much they expose the underlying SIMD intrisics. Rust has some initial support, I don't follow it, last time I checked it was only available on nightly with a very basic subset on stable. Zig no idea, I don't follow it that much, being yet another C just with bounds checking isn't something I care about.
- jpm48 6y ago
  This is really nice, I teach intrinsics to my MSc students so will add this to their reading list. This is a recent set of notes I gave them showing how to go from simple CPU only to Threaded SIMD + OpenGL https://nccastaff.bournemouth.ac.uk/jmacey/post/GridVis/gridvis/ https://nccastaff.bournemouth.ac.uk/jmacey/post/GridVis/grid...
mettamage 6y ago
Probably a HN article on its own, but also related [1]. It's about timestamp parsing using SIMD instructions (among other optimizations). I've noticed when I had a toy HFT project that this type of thinking is needed. [1] https://kholdstare.github.io/technical/2020/05/26/faster-integer-parsing.html https://kholdstare.github.io/technical/2020/05/26/faster-int...
xpuente 6y ago
Why not tools like https://github.com/ispc https://github.com/ispc? This seems really close to the metal, either to have a non-negligible maintenance cost or not being able to fully exploit the hardware at use.
- Scaevolus 6y ago
  Switching compilers is often too high-risk, but there are header-only libraries that get you most of the same benefits with normal C++ and wrappers around the intrinsics: https://github.com/richgel999/CppSPMD_Fast https://github.com/richgel999/CppSPMD_Fast
- vgatherps 6y ago
  I've used ISPC before, as well as enoki (sort of like ISPC-in-c++), and found that they have a lot of sharp performance edges. My experience with both was that as I moved away from the super classic SIMD cases, the more I ran into crazy compiler cliffs where tiny tweaks would blow up the codegen. In each case I gave up, reimplemented what I wanted directly in c++ (the second time using anger fog's wonderful vector class library), and easily got the results I wanted without a ton of finagling the compiler and libraries.
- bjourne 6y ago
  It doesn't always emit optimal SIMD code. Plus, when you get the hang of it, writing your own SIMD library is fairly simple so you don't need a tool for it. C++ templates and operator overloading really shines here. For example, you can write sqrt(x*y+z) and have the the template system select the most optimal SIMD intrinsics depending on whether x, y, and z are int, float, int16, float8, double4, etc.
  - janwas 6y ago
    +1 to intrinsics or wrappers giving us more control over performance. > Plus, when you get the hang of it, writing your own SIMD library is fairly simple hm.. it's indeed easy to start, but maintaining https://github.com/google/highway https://github.com/google/highway (supports clang/gcc/MSVC, x86/ARM/RiscV) is quite time-consuming, especially working around compiler bugs.
dkersten 6y ago
Perfect timing, I was just about to start looking into SIMD again as my toy game engine is almost at a point where I want to see if I can vectorize some of my processing (much of it is already stored in SOA format, so hopefully it won't be too much trouble). I'm thinking especially about tasks like frustum culling, but also other things. We'll see, after I read this :) I've used SIMD intrinsics before, but I could definitely do with a refresher!
- Const-me 6y ago
  For videogame applications, look there before writing these intrinsics: https://github.com/microsoft/DirectXMath/ https://github.com/microsoft/DirectXMath/ That library already implements a lot of complicated things, relatively well. Here’s for frustum culling https://github.com/microsoft/DirectXMath/blob/jan2021/Inc/DirectXCollision.inl#L3070-L3104 https://github.com/microsoft/DirectXMath/blob/jan2021/Inc/Di... Relatively inefficient when you have many boxes to test against same frustum, but (a) compiler may inline and optimize (b) failing that, it’s easy to copy-paste and optimize manually, compute these 6 planes and call BoundingBox::ContainedBy method yourself.
  - dkersten 6y ago
    Thanks, I’ll take a look. Although, it’s a for fun engine so I may try myself anyway just to learn. I’ll see. Either way, thanks for the link, very interesting! As for frustum culling, that code seems to do one bounding box at a time? Or am I misunderstanding? I was planning to try to do 4 (or however many) checks at a time. I’m ok with checking against bounding spheres too if that makes it easier to vectorize.
    - Const-me 6y ago
      > that code seems to do one bounding box at a time? Yep, most parts of that library were designed for doing one thing at a time. Generally speaking, HPC-style SoA approach can be faster especially if you have AVX. But there’s a price for that, most importantly code complexity but some performance-related things as well: RAM access pattern, uploading to VRAM for rendering. > I was planning to try to do 4 (or however many) checks at a time I would start with whatever code is in that library, and only optimize if profiler says so. They have sphere versus frustum test too, similar one i.e. they also testing against these 6 planes, might be slightly more efficient than boxes.
secondcoming 6y ago
What timing! This is probably better for StackOverflow, but is there a way to AND two AVX operands and also get the ZF flag set if the result is zero? It seems like there's one intrinsic to do the AND but this doesn't set ZF. [0] But there's another instrinsic that will set ZF but doesn't actually store the result of the AND operation [1]. [0] vpand ymm, ymm, ymm [1] vtestpd ymm, ymm I'm guessing that either a) I'm missing an instruction, or having to modify EFLAGS from AVX instructions incurs a large penalty and so it's not advisable?
- Const-me 6y ago
  I don’t think you’re missing an instruction. A few comments, still. Bitwise instructions are very cheap, 1 cycle of latency. Skylake can run 3 of them every clock, Zen 2 can run 4 of them per clock. I wouldn’t worry about that extra vpand instruction too much. About vptest, the latency is not great, 6-7 cycles. If you gonna branch on the outcome, and the branch is not predictable (your code takes random branch every time the instruction at specific address is running), you gonna waste time. Sometimes that’s unavoidable, like when your goal is something similar to memchr() function (however I’d recommend _mm256_movemask_epi8 instead for that). But other times it’s possible to rework into something better: mask lanes with _mm256_blendv_[something], zero out stuff with bitwise AND, that kind of stuff.
- deleted 6y ago
  [deleted]
dragontamer 6y ago
https://software.intel.com/sites/landingpage/IntrinsicsGuide/ https://software.intel.com/sites/landingpage/IntrinsicsGuide... Anyone who is using SSE / AVX / AVX512 intrinsics probably should know about Intel's excellent Intrinsics Guide. The Intel guide is a reference. This .pdf topic is a tutorial. So both resources will be helpful to anyone seriously doing SIMD on the CPU.
- mjsir911 6y ago
  I also use this for nice visualizations while learning: https://www.officedaytime.com/simd512e/ https://www.officedaytime.com/simd512e/
- janwas 6y ago
  Nice. For anyone interested in ARM, they also have a guide with diagrams [1] and a searchable reference [2]. 1: https://developer.arm.com/documentation/102159/0400/Permutation---Neon-instructions https://developer.arm.com/documentation/102159/0400/Permutat... 2: https://developer.arm.com/architectures/instruction-sets/simd-isas/neon/intrinsics https://developer.arm.com/architectures/instruction-sets/sim...
andyxor 6y ago
If you liked this post you may also like: SIMD in Java: https://news.ycombinator.com/item?id=14636802 https://news.ycombinator.com/item?id=14636802 (archived version https://archive.is/C5iZA https://archive.is/C5iZA) SIMD in Rust: https://news.ycombinator.com/item?id=10111729 https://news.ycombinator.com/item?id=10111729 SIMD in Python: https://news.ycombinator.com/item?id=10470428 https://news.ycombinator.com/item?id=10470428 SIMD in Javascript: https://news.ycombinator.com/item?id=8533350 https://news.ycombinator.com/item?id=8533350 Using SIMD to aggregate billions of values per second: https://news.ycombinator.com/item?id=22803504 https://news.ycombinator.com/item?id=22803504 Towards fearless SIMD: https://news.ycombinator.com/item?id=18293209 https://news.ycombinator.com/item?id=18293209 First Impressions of ARM SIMD Programming: https://news.ycombinator.com/item?id=19490542 https://news.ycombinator.com/item?id=19490542
kolbe 6y ago
I would at least appreciate a disclaimer that the vast majority of these optimizations could be accomplished by encouraging the compilers to make the assembly vectorized. You said in a footnote that compilers will only do these optimizations when they're extremely simple and rarely on integers, but I have not found that to be the case. -O3 and -mavx do an amazing job for most use cases. And more to the point, there are other tricks that I think it's better to turn to (like using the __restrict key word) before you take these fairly steep steps into coding the SIMD commands yourself. It's cool to learn these things. And it's down right important to learn these things once you're experienced enough, because you have to use them at some point if you're in the game of optimization. But also I would feel pretty bad if some kid out there wasted a week on a project at work (and got reprimanded for it) that could have been accomplished with a couple compiler flags, you know?
- Const-me 6y ago
  They’re getting better over time, especially for floats/doubles, but I still find them limited even for simple use cases. Here’s an example of auto-vectorizer in clang 12, which I believe represents state of the art at the moment: https://godbolt.org/z/6Pe33187W https://godbolt.org/z/6Pe33187W It automatically vectorized the loop and even manually unrolled it, however I think the code bottlenecks on shuffles not on memory loads. Just too many instructions in the loop, and that vpmovzxbq instruction can only run on port 5 on Skylake. Compare the assembly with manually vectorized version from an answer on stackoverflow: https://godbolt.org/z/do5e3- https://godbolt.org/z/do5e3-
- janwas 6y ago
  +1 for restrict, that certainly helps. Out of curiosity, what's your use case where autovectorization works well? Personally, I have often been disappointed. Not much progress in 2 years: http://www.0x80.pl/notesen/2021-01-18-autovectorization-gcc-clang.html http://www.0x80.pl/notesen/2021-01-18-autovectorization-gcc-...
  - kolbe 6y ago
    I'll admit that there are times when I am both stunned at how well the compiler will optimize, and times when I'm stunned at how poorly it does. It would seem you can never make an assumption on what will happen--hence my addiction to godbolt. I don't have my exact code, but I work heavily with math operations, so it may be that I do encounter an especially easy types of loops to vectorize.
janwas 6y ago
Nice writeup with helpful diagrams, thanks for sharing! Readers might also find this short intro [1] helpful, including tips on porting. (Disclosure: author) 1: https://github.com/google/highway/blob/master/g3doc/highway_intro.pdf https://github.com/google/highway/blob/master/g3doc/highway_... > many available instructions are missing from the wrappers Highway can interop with platform-specific intrinsics (on x86/ARM, hwy_vec.raw is the native intrinsic type). > vectorized integer math often treats vectors as having different lanes count on every line of code Fair point, that's a cost of type safety. We usually write `auto` to avoid spelling it out.
elteto 6y ago
If you go to the parent directory [0] there is a similar guide for ARM NEON [1] [0] http://const.me/articles/simd http://const.me/articles/simd [1] http://const.me/articles/simd/NEON.pdf http://const.me/articles/simd/NEON.pdf

129 points by Const-me 6y ago

Updated my article from 2019. It’s not limited to C++, equally good for C. Over time, the support slowly arrives to other languages too, like C#: https://docs.microsoft.com/en-us/dotnet/api/system.runtime.intrinsics.x86.sse?view=net-5.0 https://docs.microsoft.com/en-us/dotnet/api/system.runtime.i... https://docs.microsoft.com/en-us/dotnet/api/system.runtime.intrinsics.x86.avx?view=net-5.0 https://docs.microsoft.com/en-us/dotnet/api/system.runtime.i...

bobthedino 6y ago
SIMD support is also currently in development for Java: https://openjdk.java.net/jeps/338 https://openjdk.java.net/jeps/338
smhenderson 6y ago
It's a really well written article, thank you for the work!
gameswithgo 6y ago
Rust as well, and the intrinsics are identically named so your tutorial is good for rust as well.
pjmlp 6y ago
And D as well, although the support varies a bit across all three backends.
- MaxBarraclough 6y ago
  How about other languages that use GCC/LLVM, like Zig, Rust, Ada, or for that matter FORTRAN?
  - pjmlp 6y ago
    Fortran for sure, given its use in HPC and GPGPU programming since it exits (we no longer use all caps for its name :) ). Only GNAT Ada uses GCC/LLVM, the other surviving Ada vendors have their own compilers, no idea how much they expose the underlying SIMD intrisics. Rust has some initial support, I don't follow it, last time I checked it was only available on nightly with a very basic subset on stable. Zig no idea, I don't follow it that much, being yet another C just with bounds checking isn't something I care about.
jpm48 6y ago
This is really nice, I teach intrinsics to my MSc students so will add this to their reading list. This is a recent set of notes I gave them showing how to go from simple CPU only to Threaded SIMD + OpenGL https://nccastaff.bournemouth.ac.uk/jmacey/post/GridVis/gridvis/ https://nccastaff.bournemouth.ac.uk/jmacey/post/GridVis/grid...

mettamage 6y ago

Probably a HN article on its own, but also related [1]. It's about timestamp parsing using SIMD instructions (among other optimizations). I've noticed when I had a toy HFT project that this type of thinking is needed. [1] https://kholdstare.github.io/technical/2020/05/26/faster-integer-parsing.html https://kholdstare.github.io/technical/2020/05/26/faster-int...

xpuente 6y ago

Why not tools like https://github.com/ispc https://github.com/ispc? This seems really close to the metal, either to have a non-negligible maintenance cost or not being able to fully exploit the hardware at use.

Scaevolus 6y ago
Switching compilers is often too high-risk, but there are header-only libraries that get you most of the same benefits with normal C++ and wrappers around the intrinsics: https://github.com/richgel999/CppSPMD_Fast https://github.com/richgel999/CppSPMD_Fast
vgatherps 6y ago
I've used ISPC before, as well as enoki (sort of like ISPC-in-c++), and found that they have a lot of sharp performance edges. My experience with both was that as I moved away from the super classic SIMD cases, the more I ran into crazy compiler cliffs where tiny tweaks would blow up the codegen. In each case I gave up, reimplemented what I wanted directly in c++ (the second time using anger fog's wonderful vector class library), and easily got the results I wanted without a ton of finagling the compiler and libraries.
bjourne 6y ago
It doesn't always emit optimal SIMD code. Plus, when you get the hang of it, writing your own SIMD library is fairly simple so you don't need a tool for it. C++ templates and operator overloading really shines here. For example, you can write sqrt(x*y+z) and have the the template system select the most optimal SIMD intrinsics depending on whether x, y, and z are int, float, int16, float8, double4, etc.
- janwas 6y ago
  +1 to intrinsics or wrappers giving us more control over performance. > Plus, when you get the hang of it, writing your own SIMD library is fairly simple hm.. it's indeed easy to start, but maintaining https://github.com/google/highway https://github.com/google/highway (supports clang/gcc/MSVC, x86/ARM/RiscV) is quite time-consuming, especially working around compiler bugs.

dkersten 6y ago

Perfect timing, I was just about to start looking into SIMD again as my toy game engine is almost at a point where I want to see if I can vectorize some of my processing (much of it is already stored in SOA format, so hopefully it won't be too much trouble). I'm thinking especially about tasks like frustum culling, but also other things. We'll see, after I read this :) I've used SIMD intrinsics before, but I could definitely do with a refresher!

Const-me 6y ago
For videogame applications, look there before writing these intrinsics: https://github.com/microsoft/DirectXMath/ https://github.com/microsoft/DirectXMath/ That library already implements a lot of complicated things, relatively well. Here’s for frustum culling https://github.com/microsoft/DirectXMath/blob/jan2021/Inc/DirectXCollision.inl#L3070-L3104 https://github.com/microsoft/DirectXMath/blob/jan2021/Inc/Di... Relatively inefficient when you have many boxes to test against same frustum, but (a) compiler may inline and optimize (b) failing that, it’s easy to copy-paste and optimize manually, compute these 6 planes and call BoundingBox::ContainedBy method yourself.
- dkersten 6y ago
  Thanks, I’ll take a look. Although, it’s a for fun engine so I may try myself anyway just to learn. I’ll see. Either way, thanks for the link, very interesting! As for frustum culling, that code seems to do one bounding box at a time? Or am I misunderstanding? I was planning to try to do 4 (or however many) checks at a time. I’m ok with checking against bounding spheres too if that makes it easier to vectorize.
  - Const-me 6y ago
    > that code seems to do one bounding box at a time? Yep, most parts of that library were designed for doing one thing at a time. Generally speaking, HPC-style SoA approach can be faster especially if you have AVX. But there’s a price for that, most importantly code complexity but some performance-related things as well: RAM access pattern, uploading to VRAM for rendering. > I was planning to try to do 4 (or however many) checks at a time I would start with whatever code is in that library, and only optimize if profiler says so. They have sphere versus frustum test too, similar one i.e. they also testing against these 6 planes, might be slightly more efficient than boxes.

secondcoming 6y ago

What timing! This is probably better for StackOverflow, but is there a way to AND two AVX operands and also get the ZF flag set if the result is zero? It seems like there's one intrinsic to do the AND but this doesn't set ZF. [0] But there's another instrinsic that will set ZF but doesn't actually store the result of the AND operation [1]. [0] vpand ymm, ymm, ymm [1] vtestpd ymm, ymm I'm guessing that either a) I'm missing an instruction, or having to modify EFLAGS from AVX instructions incurs a large penalty and so it's not advisable?

Const-me 6y ago
I don’t think you’re missing an instruction. A few comments, still. Bitwise instructions are very cheap, 1 cycle of latency. Skylake can run 3 of them every clock, Zen 2 can run 4 of them per clock. I wouldn’t worry about that extra vpand instruction too much. About vptest, the latency is not great, 6-7 cycles. If you gonna branch on the outcome, and the branch is not predictable (your code takes random branch every time the instruction at specific address is running), you gonna waste time. Sometimes that’s unavoidable, like when your goal is something similar to memchr() function (however I’d recommend _mm256_movemask_epi8 instead for that). But other times it’s possible to rework into something better: mask lanes with _mm256_blendv_[something], zero out stuff with bitwise AND, that kind of stuff.
deleted 6y ago
[deleted]

dragontamer 6y ago

https://software.intel.com/sites/landingpage/IntrinsicsGuide/ https://software.intel.com/sites/landingpage/IntrinsicsGuide... Anyone who is using SSE / AVX / AVX512 intrinsics probably should know about Intel's excellent Intrinsics Guide. The Intel guide is a reference. This .pdf topic is a tutorial. So both resources will be helpful to anyone seriously doing SIMD on the CPU.

mjsir911 6y ago
I also use this for nice visualizations while learning: https://www.officedaytime.com/simd512e/ https://www.officedaytime.com/simd512e/
janwas 6y ago
Nice. For anyone interested in ARM, they also have a guide with diagrams [1] and a searchable reference [2]. 1: https://developer.arm.com/documentation/102159/0400/Permutation---Neon-instructions https://developer.arm.com/documentation/102159/0400/Permutat... 2: https://developer.arm.com/architectures/instruction-sets/simd-isas/neon/intrinsics https://developer.arm.com/architectures/instruction-sets/sim...

andyxor 6y ago

If you liked this post you may also like: SIMD in Java: https://news.ycombinator.com/item?id=14636802 https://news.ycombinator.com/item?id=14636802 (archived version https://archive.is/C5iZA https://archive.is/C5iZA) SIMD in Rust: https://news.ycombinator.com/item?id=10111729 https://news.ycombinator.com/item?id=10111729 SIMD in Python: https://news.ycombinator.com/item?id=10470428 https://news.ycombinator.com/item?id=10470428 SIMD in Javascript: https://news.ycombinator.com/item?id=8533350 https://news.ycombinator.com/item?id=8533350 Using SIMD to aggregate billions of values per second: https://news.ycombinator.com/item?id=22803504 https://news.ycombinator.com/item?id=22803504 Towards fearless SIMD: https://news.ycombinator.com/item?id=18293209 https://news.ycombinator.com/item?id=18293209 First Impressions of ARM SIMD Programming: https://news.ycombinator.com/item?id=19490542 https://news.ycombinator.com/item?id=19490542

kolbe 6y ago

I would at least appreciate a disclaimer that the vast majority of these optimizations could be accomplished by encouraging the compilers to make the assembly vectorized. You said in a footnote that compilers will only do these optimizations when they're extremely simple and rarely on integers, but I have not found that to be the case. -O3 and -mavx do an amazing job for most use cases. And more to the point, there are other tricks that I think it's better to turn to (like using the __restrict key word) before you take these fairly steep steps into coding the SIMD commands yourself. It's cool to learn these things. And it's down right important to learn these things once you're experienced enough, because you have to use them at some point if you're in the game of optimization. But also I would feel pretty bad if some kid out there wasted a week on a project at work (and got reprimanded for it) that could have been accomplished with a couple compiler flags, you know?

Const-me 6y ago
They’re getting better over time, especially for floats/doubles, but I still find them limited even for simple use cases. Here’s an example of auto-vectorizer in clang 12, which I believe represents state of the art at the moment: https://godbolt.org/z/6Pe33187W https://godbolt.org/z/6Pe33187W It automatically vectorized the loop and even manually unrolled it, however I think the code bottlenecks on shuffles not on memory loads. Just too many instructions in the loop, and that vpmovzxbq instruction can only run on port 5 on Skylake. Compare the assembly with manually vectorized version from an answer on stackoverflow: https://godbolt.org/z/do5e3- https://godbolt.org/z/do5e3-
janwas 6y ago
+1 for restrict, that certainly helps. Out of curiosity, what's your use case where autovectorization works well? Personally, I have often been disappointed. Not much progress in 2 years: http://www.0x80.pl/notesen/2021-01-18-autovectorization-gcc-clang.html http://www.0x80.pl/notesen/2021-01-18-autovectorization-gcc-...
- kolbe 6y ago
  I'll admit that there are times when I am both stunned at how well the compiler will optimize, and times when I'm stunned at how poorly it does. It would seem you can never make an assumption on what will happen--hence my addiction to godbolt. I don't have my exact code, but I work heavily with math operations, so it may be that I do encounter an especially easy types of loops to vectorize.

janwas 6y ago

Nice writeup with helpful diagrams, thanks for sharing! Readers might also find this short intro [1] helpful, including tips on porting. (Disclosure: author) 1: https://github.com/google/highway/blob/master/g3doc/highway_intro.pdf https://github.com/google/highway/blob/master/g3doc/highway_... > many available instructions are missing from the wrappers Highway can interop with platform-specific intrinsics (on x86/ARM, hwy_vec.raw is the native intrinsic type). > vectorized integer math often treats vectors as having different lanes count on every line of code Fair point, that's a cost of type safety. We usually write `auto` to avoid spelling it out.

elteto 6y ago

If you go to the parent directory [0] there is a similar guide for ARM NEON [1] [0] http://const.me/articles/simd http://const.me/articles/simd [1] http://const.me/articles/simd/NEON.pdf http://const.me/articles/simd/NEON.pdf