6 ms·

I haven't (yet) read the article, but I will. But the headline... > Optimizing compilers reload vector constants needlessly ...is absolutely true. I wrote som

I haven't (yet) read the article, but I will. But the headline... > Optimizing compilers reload vector constants needlessly ...is absolutely true. I wrote some code that just does bit management (shifting, or, and, xor, popcount) on a byte-level. Compiler produced vectorized instructions that provided about a 30% speed-up. But when I looked at it... it was definitely not as good as it could be, and one of the big things was frequently reloading/broadcasting constants like 0x0F or 0xCC or similar. Another thing it would do is to sometimes drop down to normal (not-SIMD) instructions. This was with both `-O2` and `-O3`, and also with `-march=native` I ended up learning how to use SIMD intrinsics and hand-wrote it all... and achieved about a 600% speedup. The code reached about 90% of the performance of the bus to RAM which was what I theorized "should" be the limiting factor: bitwise operations like this are extremely fast and the slowest point point was popcount which didn't have a native instruction on the hardware I was targeting (AVX2). This was with GCC 6.3 if I recall, about 5 years ago.

jeffreyrogers 4y ago
That's basically the problem the article describes although he's using vector intrinsics too and it still reloads and broadcasts the constant before each loop.
- pclmulqdq 4y ago
  When I have used intrinsics, the compiler at least has a hope of getting this right, particularly when you use patterns like: __m256i mask = _mm256_set1_epi8(0x0f) If you just used the intrinsic that sets the register to a constant over and over, it often repeats the instruction. The compilers just aren't that smart about SIMD yet.
  - jeffreyrogers 4y ago
    He sets it once like this before the loops. __m256i c = _mm256_set1_epi32(10001); And then the disassembly has mov eax, 10001 vpbroadcastd ymm1, eax before each loop.
    - pclmulqdq 4y ago
      Yeah, if the compiler runs out of registers it will do this - it's better than spilling the constant to memory. Register allocation is one thing that compilers are still much worse at than humans, and you see it in SIMD code a lot.
      - DannyBee 4y ago
        Eh. Compilers are only worse because we don't care. Optimal register allocation + spilling is easily doable now on today's machines/algorithms. We just don't bother because it's not truly worth it in most cases (IE we get most of the performance for a very low cost)
- DannyBee 4y ago
  There are three reasons it reloads constants: 1. It thinks it is cheaper than keeping them in a register ( this is known as rematerialization). It will reload constants that it lets it keep something else in a register, and it's cheaper to do this. 2. It thinks something could affect the constant. 3. It thinks it must move it through memory to use it, and then it thinks the memory was clobbered. In this case, it definitely knows it is a constant, and it can't prove that both loops always execute, so it places it in the path where it is only executed once per loop, because it believes it will be cheaper. I can still make at least gcc do weird things if i prove to it the loop executes once. In that case, what is happening in gcc is that constant propagation is propagating the vector constant forward into both loops. Something later (that has a machine cost model) is expected to commonize it if it is cheaper, but never does.
  - DannyBee 4y ago
    You can see it get propagated through as a constant at the high level here: https://godbolt.org/z/jxWKcnTT1 https://godbolt.org/z/jxWKcnTT1 That is normal and what i would expect to happen. You can see in lower level RTL dumps, nothing chooses to commonize it. That seems a bit weird, since it should have a cost model that says this isn't free.
    - caf 4y ago
      I believe it's possible to report this as a "missed optimisation" bug.
      - DannyBee 4y ago
        Yes. A lot of the intrinsics also look like (at least in gcc), they are marked always inline but not pure/const. it's probably worthwhile marking those that take memory as pure/const. That way, it's obvious the value is readonly even when it's inlined. (otherwise, the compiler will have to prove it in the inlined code, which is not always possible)
deleted 4y ago
[deleted]
phkahler 4y ago
>> This was with both `-O2` and `-O3`, and also with `-march=native` Until very recently GCC didn't do vectorization at -O2 usless you told it to.
- inetknght 4y ago
  That's true. I definitely omitted a bunch of other flags that were added including the flags to turn on vectorizations
an1sotropy 4y ago
Can you recommend any favorite resources for learning how to use SIMD intrinsics?
- teux 4y ago
  Not OP but also work with this. There’s some tutorials but honestly the best thing is to just use them. Write an image processing routine that does something like apply a gaussian blur to a black and white image. The c++ code for this is everywhere. You have a fixed kernel (2d matrix) and you have to do repeat multiplication and addition to each pixel for each element in the kernel. Write it in C++ or Rust. Then read the Arm SIMD manual, find the instructions that do the math you want, and switch it over to intrinsics. You are doing the same exact operations with the intrinsics as the raw c++. Just 8 or 16 of them at a single time. Run them side by side for parity and to check speed, tweak the simd, etc. Arm has good (well ,okay) documentation https://developer.arm.com/documentation/den0018/a/?lang=en https://developer.arm.com/documentation/den0018/a/?lang=en https://arm-software.github.io/acle/neon_intrinsics/advsimd.html https://arm-software.github.io/acle/neon_intrinsics/advsimd.... * Edit: you also have to do this on a supported architecture. Raspberry pi’s have a neon core at least in the 3’s. Not sure about the 4’s but I believe so too!
  - corysama 4y ago
    Adding on: Go to https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html# https://www.intel.com/content/www/us/en/docs/intrinsics-guid... Start with SSE, SSE2, SSE3 Write small functions in https://godbolt.org/ https://godbolt.org/ . Watch the assembly and the program output.
    - inetknght 4y ago
      > https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html# https://www.intel.com/content/www/us/en/docs/intrinsics-guid... Intel's Intrinsics Guide is exactly what I used and it was before I learned about Compiler Explorer. I already had a large and thorough suite of unit tests for inputs and expected outputs, including happy and sad paths. So it was pretty easy to poke around and learn what works, what doesn't. It was definitely time intensive (took about three months for about 50 lines of code) but it also saved the company a few million dollars in hardware (DNA analysis software to compare a couple TiB of data requires a _lot_ of performance). I have since moved to a different company, partly because I never saw a bonus for saving all that money. The intrinsics guide does good to show what's available but it does not do a good job of documenting how each instruction actually works... many intrinsics are missing pseudocode and some pseudocode can have ambiguous cases. I used GDB in assembly mode to compare that table against the register content instruction-by-instruction to figure out where I misunderstood something if something went awry. Frustratingly, some operations are available in 64-bits but not bigger, some in 128-bits but not bigger, etc. So I wrote up a rough draft in LibreOffice Calc with 64, 128, and 256 columns to follow the bits around every intended operation. I then correlated against the intrinsics guide to determine what instructions are available to me in what bit sizes. For a given test run, each row in the spreadsheet was colored by what the original data contained, another row for what I needed the answer to be for that test case, then auto-color another row's cell green or red if the register after a candidate set of instructions did or didn't match the desired output. Any time I had to move columns around (the data was 4-bits wide), I'd color a set of 4 columns to follow where they go during swizzling.
teux 4y ago
I often hand write neon (and other vectorised architecture) intrinsics/assembly for my job, optimising image and signal processing routines. We have seen many many 3 digit percentage speedups from bare c/c++ code. I got into the nastiest discussion on reddit where people were swearing up and down it was impossible to beat the compiler, and handwritten assembly was useless/pretentious/dangerous. I was downvoted massively. Sigh. Anyways, that was a year ago. Thanks for another point of validation for that. It clearly didn’t hurt my feelings. :) I never come across people in the wild that actually do this also, it’s such a niche area of expertise.
- astrange 4y ago
  Tell them to read the ffmpeg code. All the platform-specific/SIMD stuff is done in asm. This isn't only because it's faster, it's honestly easier to read than intrinsics anyway. What it does lack is debugability.
  - teux 4y ago
    For debugging you can actually use gdb in assembly tui mode and step through the instructions! You can even get it hooked up in vs code and remote debug an embedded target using the full IDE. Full register view, watch registers for changes, breakpoints, step instruction to instruction. Pipelining and optimisations can make the intrinsics a bit fucky though, have to make sure it’s -O0 and a proper debug compilation. I have line by line debugged raw assembly many times. It’s just a pain to initially set up. Honestly not very different from c/c++ debugging once running.
    - astrange 4y ago
      Sure, but gdb doesn't know what the function parameters are, or on some platforms where functions start and end, crashes don't have source lines, and ASan doesn't work. (though of course valgrind does)
      - variadix 4y ago
        I don’t know if this is frowned upon or not among assembly programmers, but I often just use naked functions in C with asm bodies, which gdb will provide the args for, rather than linking against a separate assembly file.

jeffreyrogers 4y ago

That's basically the problem the article describes although he's using vector intrinsics too and it still reloads and broadcasts the constant before each loop.

pclmulqdq 4y ago
When I have used intrinsics, the compiler at least has a hope of getting this right, particularly when you use patterns like: __m256i mask = _mm256_set1_epi8(0x0f) If you just used the intrinsic that sets the register to a constant over and over, it often repeats the instruction. The compilers just aren't that smart about SIMD yet.
- jeffreyrogers 4y ago
  He sets it once like this before the loops. __m256i c = _mm256_set1_epi32(10001); And then the disassembly has mov eax, 10001 vpbroadcastd ymm1, eax before each loop.
  - pclmulqdq 4y ago
    Yeah, if the compiler runs out of registers it will do this - it's better than spilling the constant to memory. Register allocation is one thing that compilers are still much worse at than humans, and you see it in SIMD code a lot.
    - DannyBee 4y ago
      Eh. Compilers are only worse because we don't care. Optimal register allocation + spilling is easily doable now on today's machines/algorithms. We just don't bother because it's not truly worth it in most cases (IE we get most of the performance for a very low cost)
DannyBee 4y ago
There are three reasons it reloads constants: 1. It thinks it is cheaper than keeping them in a register ( this is known as rematerialization). It will reload constants that it lets it keep something else in a register, and it's cheaper to do this. 2. It thinks something could affect the constant. 3. It thinks it must move it through memory to use it, and then it thinks the memory was clobbered. In this case, it definitely knows it is a constant, and it can't prove that both loops always execute, so it places it in the path where it is only executed once per loop, because it believes it will be cheaper. I can still make at least gcc do weird things if i prove to it the loop executes once. In that case, what is happening in gcc is that constant propagation is propagating the vector constant forward into both loops. Something later (that has a machine cost model) is expected to commonize it if it is cheaper, but never does.
- DannyBee 4y ago
  You can see it get propagated through as a constant at the high level here: https://godbolt.org/z/jxWKcnTT1 https://godbolt.org/z/jxWKcnTT1 That is normal and what i would expect to happen. You can see in lower level RTL dumps, nothing chooses to commonize it. That seems a bit weird, since it should have a cost model that says this isn't free.
  - caf 4y ago
    I believe it's possible to report this as a "missed optimisation" bug.
    - DannyBee 4y ago
      Yes. A lot of the intrinsics also look like (at least in gcc), they are marked always inline but not pure/const. it's probably worthwhile marking those that take memory as pure/const. That way, it's obvious the value is readonly even when it's inlined. (otherwise, the compiler will have to prove it in the inlined code, which is not always possible)

deleted 4y ago

[deleted]

phkahler 4y ago

>> This was with both `-O2` and `-O3`, and also with `-march=native` Until very recently GCC didn't do vectorization at -O2 usless you told it to.

inetknght 4y ago
That's true. I definitely omitted a bunch of other flags that were added including the flags to turn on vectorizations

an1sotropy 4y ago

Can you recommend any favorite resources for learning how to use SIMD intrinsics?

teux 4y ago
Not OP but also work with this. There’s some tutorials but honestly the best thing is to just use them. Write an image processing routine that does something like apply a gaussian blur to a black and white image. The c++ code for this is everywhere. You have a fixed kernel (2d matrix) and you have to do repeat multiplication and addition to each pixel for each element in the kernel. Write it in C++ or Rust. Then read the Arm SIMD manual, find the instructions that do the math you want, and switch it over to intrinsics. You are doing the same exact operations with the intrinsics as the raw c++. Just 8 or 16 of them at a single time. Run them side by side for parity and to check speed, tweak the simd, etc. Arm has good (well ,okay) documentation https://developer.arm.com/documentation/den0018/a/?lang=en https://developer.arm.com/documentation/den0018/a/?lang=en https://arm-software.github.io/acle/neon_intrinsics/advsimd.html https://arm-software.github.io/acle/neon_intrinsics/advsimd.... * Edit: you also have to do this on a supported architecture. Raspberry pi’s have a neon core at least in the 3’s. Not sure about the 4’s but I believe so too!
- corysama 4y ago
  Adding on: Go to https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html# https://www.intel.com/content/www/us/en/docs/intrinsics-guid... Start with SSE, SSE2, SSE3 Write small functions in https://godbolt.org/ https://godbolt.org/ . Watch the assembly and the program output.
  - inetknght 4y ago
    > https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html# https://www.intel.com/content/www/us/en/docs/intrinsics-guid... Intel's Intrinsics Guide is exactly what I used and it was before I learned about Compiler Explorer. I already had a large and thorough suite of unit tests for inputs and expected outputs, including happy and sad paths. So it was pretty easy to poke around and learn what works, what doesn't. It was definitely time intensive (took about three months for about 50 lines of code) but it also saved the company a few million dollars in hardware (DNA analysis software to compare a couple TiB of data requires a _lot_ of performance). I have since moved to a different company, partly because I never saw a bonus for saving all that money. The intrinsics guide does good to show what's available but it does not do a good job of documenting how each instruction actually works... many intrinsics are missing pseudocode and some pseudocode can have ambiguous cases. I used GDB in assembly mode to compare that table against the register content instruction-by-instruction to figure out where I misunderstood something if something went awry. Frustratingly, some operations are available in 64-bits but not bigger, some in 128-bits but not bigger, etc. So I wrote up a rough draft in LibreOffice Calc with 64, 128, and 256 columns to follow the bits around every intended operation. I then correlated against the intrinsics guide to determine what instructions are available to me in what bit sizes. For a given test run, each row in the spreadsheet was colored by what the original data contained, another row for what I needed the answer to be for that test case, then auto-color another row's cell green or red if the register after a candidate set of instructions did or didn't match the desired output. Any time I had to move columns around (the data was 4-bits wide), I'd color a set of 4 columns to follow where they go during swizzling.

teux 4y ago

I often hand write neon (and other vectorised architecture) intrinsics/assembly for my job, optimising image and signal processing routines. We have seen many many 3 digit percentage speedups from bare c/c++ code. I got into the nastiest discussion on reddit where people were swearing up and down it was impossible to beat the compiler, and handwritten assembly was useless/pretentious/dangerous. I was downvoted massively. Sigh. Anyways, that was a year ago. Thanks for another point of validation for that. It clearly didn’t hurt my feelings. :) I never come across people in the wild that actually do this also, it’s such a niche area of expertise.

astrange 4y ago
Tell them to read the ffmpeg code. All the platform-specific/SIMD stuff is done in asm. This isn't only because it's faster, it's honestly easier to read than intrinsics anyway. What it does lack is debugability.
- teux 4y ago
  For debugging you can actually use gdb in assembly tui mode and step through the instructions! You can even get it hooked up in vs code and remote debug an embedded target using the full IDE. Full register view, watch registers for changes, breakpoints, step instruction to instruction. Pipelining and optimisations can make the intrinsics a bit fucky though, have to make sure it’s -O0 and a proper debug compilation. I have line by line debugged raw assembly many times. It’s just a pain to initially set up. Honestly not very different from c/c++ debugging once running.
  - astrange 4y ago
    Sure, but gdb doesn't know what the function parameters are, or on some platforms where functions start and end, crashes don't have source lines, and ASan doesn't work. (though of course valgrind does)
    - variadix 4y ago
      I don’t know if this is frowned upon or not among assembly programmers, but I often just use naked functions in C with asm bodies, which gdb will provide the args for, rather than linking against a separate assembly file.