6 ms·

I find that modern c++ compilers can do a pretty good job of auto-vectorization, given that the code is "vector-friendly" to begin with. But writing code in tha

I find that modern c++ compilers can do a pretty good job of auto-vectorization, given that the code is "vector-friendly" to begin with. But writing code in that style is a bit of black magic with lots of trial and error. I wish compiler vendors would publish "style guides" for this purpose, or at least a collection of best practices.

gameswithgo 8y ago
Leveraging auto vectorization can be nice, as you can compile for different targets with one set of code, and not have to write out intrinsics for SSE2, AVX2, AVX512 etc. But yeah it is tricky, you might get it all sorted and a compiler upgrade ruins it, or it won't work on another compiler, or someone updates your function later not realizing you carefully tuned it to get vectorized and it ruins it. Also there are some clever hacks you can do with intrinsics that compilers won't figure out sometimes. I made a library in Rust that will let you write a single function using abstracted intrinsics, that can produce SSE2/SSE41/AVX2 versions at compile time: https://github.com/jackmott/simdeez https://github.com/jackmott/simdeez
- Asooka 8y ago
  Seems to me like it would be a good idea to have a tool (superoptimiser?) that can take your simple code and rewrite it with intrinsics, which you then check into source control. So you have a doFooGeneric and have the tool generate doFooSSE, doFooSSE4, doFooAVX2, doFooNEON and select one at runtime (like Intel's compiler does) or at compile time. Since you'll only run the tool infrequently, it can spend a lot of time trying to find the best vectorisation.
  - colejohnson66 8y ago
    Side note: GCC supports feature based dispatch too[0] [0]: https://lwn.net/Articles/691932/ https://lwn.net/Articles/691932/
    - gnufx 8y ago
      Yes, but target_clones, at least, isn't a panacea. If you know how to make it work in a shared library, I'm rather interested.
  - gameswithgo 8y ago
    another Rust library "Faster" attempts to do that. Its cool, but the downside is simple code can't always translate optimally to intrinsics. Like if you ask for a "floor" operation for instance. With SSE2 you have no floor operation. So you either can do a floor one at a time, or use some clever combinations of other SSE2 intrinsics to do a floor, or, if you can accept certain constraints, you can use a faster option using less intrinsics. So your simple code needs to specify which you want, which ends up being kind of like intrinsics. Also your simple code has to line everything up in arrays anyway so intrinsics don't add that much complexity. I do overload operators in SIMDeez so some of the time your code can look pretty simple.
- stochastic_monk 8y ago
  I have a similar project in C++ supporting SSE2,AVX2, and AVX512 here: https://github.com/dnbaker/vec https://github.com/dnbaker/vec. I've used it for numerical code and sketch data structures, for example. (See https://github.com/dnbaker/frp https://github.com/dnbaker/frp or https://github.com/dnbaker/sketch https://github.com/dnbaker/sketch, respectively). Most of the work I do, the compiler just isn't able to vectorize, so I just write intrinsics. I similarly wrapped FFTW and the Sleef trigonometric function library so that I can generate optimal code for a variety of types and architectures.
microcolonel 8y ago
> But writing code in that style is a bit of black magic with lots of trial and error. I wish compiler vendors would publish "style guides" for this purpose, or at least a collection of best practices. I think that would be more difficult than teaching developers to look at the generated code sometimes. At least some JavaScript developers do this, so I don't see why C++ developers can't.
- planteen 8y ago
  I think C++ developers do this a lot. I often see links to godbolt.org on Stack Overflow and Bjarne himself on YouTube videos. The tricky part is the are a number of different valid march flags for x86 and ARM that support SIMD.
  - microcolonel 8y ago
    > The tricky part is the are a number of different valid march flags for x86 and ARM that support SIMD. Sure, but if you're writing software which works on AMD64, you can see prettymuch every autovectorization opportunity that exists on other platforms. Most of the autovectorizer functionality in gcc and clang is platform-agnostic, AFAIK.
    - planteen 8y ago
      Yes you can see the broad opportunity but various things can easily break vectorization between extensions of x86 and ARM. The first that comes to mind is use of doubles instead of floats. Another is too wide of an inner loop, especially on algorithms that must be tuned for cache line sizes. You can also run into accuracy & stability issues between different x86 instruction extensions - it's really a nightmare to debug those.
    - Something1234 8y ago
      Isn't the best flag `-march=native`? It gives you all the vectorization that your processor supports, or at least I think that's the case? At least if you don't have to provide builds for other people's machines.
wyldfire 8y ago
FWIW clang has a feature called opt-viewer [1] [2] that isn't quite a style guide but instead gives explicit indication when and why it couldn't optimize particular code. [1] https://llvm.org/devmtg/2016-11/Slides/Nemet-Compiler-assistedPerformanceAnalysis.pdf https://llvm.org/devmtg/2016-11/Slides/Nemet-Compiler-assist... [2] https://github.com/androm3da/optviewer-demo https://github.com/androm3da/optviewer-demo
- IshKebab 8y ago
  Useful, thanks! God knows why they chose YAML though...
jancsika 8y ago
If a failure of auto-vectorization in a hot code path decreases performance enough for the user to perceive it as a bug, then it seems like explicitly maintaining SIMD/NEON code-paths would be preferable to dealing with auto-vectorization black magic. But I've never done either.
- gnufx 8y ago
  Vectorization failures (where vectorization would be correct) should be reported as a bug. Note that GCC has some parameters to tune vectorization about from forcing it with pragmas.
slack3r 8y ago
It may be black magic now, but people are working on making the black magic something lesser mortals don't have to worry about (eg: https://theory.stanford.edu/~aiken/publications/papers/asplos06.pdf https://theory.stanford.edu/~aiken/publications/papers/asplo...) Unfortunately, no one is actually paying attention to all this research being done in ivory tower academics. Sad!
- jcranmer 8y ago
  Superoptimization is slow, and it's generally considered feasible only for shortish bits of code. A block of about 30 instructions takes around 10 minutes to superoptimize even on state-of-the-art stochastic superoptimizers. You also need correct semantics for instructions. Go read the PCMPISTRI instruction and try to write out the SMT formulas for it so you can prove equivalence. Floating point is in an even worse state, since most interesting floating point transformations are only legal if you're willing to slacken requirements for bit-equivalence. Superoptimization is not mature enough to become part of the regular compiler flow. What is happening is you're seeing people couple superoptimizers to find missing optimizations in the compiler--John Regehr is basically doing this for LLVM's InstCombine pass with Souper.
  - slack3r 8y ago
    Lol, my comment was restricted to SIMD, which definitely does not take 10 minutes. Secondly, no mainstream compiler actually compiles code to the PCMPISTRI instruction. Presumably it was meant to be used directly as assembly. I'm not sure why you are bringing in this obscure instruction into the discussion of superoptimizers. I personally have a paranoid fantasy where NSA/GCHQ introduced this instruction to speed up password cracking. :D
    - jcranmer 8y ago
      You're citing the classic superoptimization paper, although it's actually quite old at this point. The goal of superoptimization has always been to try to compile to the no-real-C-equivalent instructions in an ISA, which includes the weird vector instructions such as PCMPISTRI. (I believe Strata attempted to match some of these instructions, and I think they managed to get formulas for about half of the weird immediate forms--these are the instructions that caused them to match "half" an instruction). In any practical vectorized tight inner-loop, the block you're trying to optimize is inherently going to be large. Superoptimization is exponential in the size of the block being optimized, which limits its utility. That was my entire point: it becomes unacceptably expensive way too quickly to get used in compilers. (Some of the code I'm looking at right now has 100s of instructions in a single basic block, definitely not atypical for a compiler).
abainbridge 8y ago
Hmmm, I feel like I've been waiting for a compiler to get clever enough to auto-vectorize my code since MMX was new. It never seems to happen. I guess I need that style guide. For example, here's a hello-world type SIMD problem: auto-vectorize a simple alpha blending pixel painting routine. struct Pixel { unsigned char r, g, b, a; }; // Draw a horizontal row of alpha blended pixels into a scan line. // Assume clipping is already done. void hline(Pixel *scanline, int startIdx, int len, Pixel c) { len &= 0xfff0; // Let the compiler assume that the length is always a multiple of 4. int invAlpha = 255 - c.a; for (int i = 0; i < len; i+=4) { Pixel &dest = scanline[startIdx + i]; dest.r = (dest.r * invAlpha + c.r * c.a) >> 8; dest.g = (dest.g * invAlpha + c.g * c.a) >> 8; dest.b = (dest.b * invAlpha + c.b * c.a) >> 8; } } And here is GCC 8 _not_ auto-vectorizing it: https://godbolt.org/z/zPZL-J https://godbolt.org/z/zPZL-J Is this the kind of thing you think should be auto-vectorizable by the compiler? If so, any idea how to persuade the compiler to do it?
- tomsmeding 8y ago
  To properly auto-vectorise this, you need to transform your ArrayOfStructures (AoS) representation to a StructureOfArrays (SoA) form, i.e. put all the r's next to each other, all the g's, etc. Then your operations are nicely in groups of four adjacent elements and the compiler will almost surely vectorise it. I'm no black magician, but I think the fact that the operations you want to do in parallel (the r's of four adjacent pixels) do not access adjacent memory cells, requiring a gather instruction or somesuch, which I hear is either slow or unsupported. Alternatively, it could vectorise the pixels themselves, but that's three elements, not four. Does it auto-vectorise it if you also do the operation on the a's?
  - abainbridge 8y ago
    > Does it auto-vectorise it if you also do the operation on the a's? Good point. Combined with fixing my loop increment (that jcranmer made me realize was wrong), I now get some vectory goodness: https://godbolt.org/z/yTJzKH https://godbolt.org/z/yTJzKH No idea what it all means. It'll be interesting to benchmark.
wmu 8y ago
Recently I checked how different compilers vectorize various C++ standard algorithms: http://0x80.pl/notesen/2019-02-02-autovectorization-gcc-clang.html http://0x80.pl/notesen/2019-02-02-autovectorization-gcc-clan... You'll also find there a hint how to rewrite std::replace algorithm to make it vectorizable.

gameswithgo 8y ago

Leveraging auto vectorization can be nice, as you can compile for different targets with one set of code, and not have to write out intrinsics for SSE2, AVX2, AVX512 etc. But yeah it is tricky, you might get it all sorted and a compiler upgrade ruins it, or it won't work on another compiler, or someone updates your function later not realizing you carefully tuned it to get vectorized and it ruins it. Also there are some clever hacks you can do with intrinsics that compilers won't figure out sometimes. I made a library in Rust that will let you write a single function using abstracted intrinsics, that can produce SSE2/SSE41/AVX2 versions at compile time: https://github.com/jackmott/simdeez https://github.com/jackmott/simdeez

Asooka 8y ago
Seems to me like it would be a good idea to have a tool (superoptimiser?) that can take your simple code and rewrite it with intrinsics, which you then check into source control. So you have a doFooGeneric and have the tool generate doFooSSE, doFooSSE4, doFooAVX2, doFooNEON and select one at runtime (like Intel's compiler does) or at compile time. Since you'll only run the tool infrequently, it can spend a lot of time trying to find the best vectorisation.
- colejohnson66 8y ago
  Side note: GCC supports feature based dispatch too[0] [0]: https://lwn.net/Articles/691932/ https://lwn.net/Articles/691932/
  - gnufx 8y ago
    Yes, but target_clones, at least, isn't a panacea. If you know how to make it work in a shared library, I'm rather interested.
- gameswithgo 8y ago
  another Rust library "Faster" attempts to do that. Its cool, but the downside is simple code can't always translate optimally to intrinsics. Like if you ask for a "floor" operation for instance. With SSE2 you have no floor operation. So you either can do a floor one at a time, or use some clever combinations of other SSE2 intrinsics to do a floor, or, if you can accept certain constraints, you can use a faster option using less intrinsics. So your simple code needs to specify which you want, which ends up being kind of like intrinsics. Also your simple code has to line everything up in arrays anyway so intrinsics don't add that much complexity. I do overload operators in SIMDeez so some of the time your code can look pretty simple.
stochastic_monk 8y ago
I have a similar project in C++ supporting SSE2,AVX2, and AVX512 here: https://github.com/dnbaker/vec https://github.com/dnbaker/vec. I've used it for numerical code and sketch data structures, for example. (See https://github.com/dnbaker/frp https://github.com/dnbaker/frp or https://github.com/dnbaker/sketch https://github.com/dnbaker/sketch, respectively). Most of the work I do, the compiler just isn't able to vectorize, so I just write intrinsics. I similarly wrapped FFTW and the Sleef trigonometric function library so that I can generate optimal code for a variety of types and architectures.

microcolonel 8y ago

> But writing code in that style is a bit of black magic with lots of trial and error. I wish compiler vendors would publish "style guides" for this purpose, or at least a collection of best practices. I think that would be more difficult than teaching developers to look at the generated code sometimes. At least some JavaScript developers do this, so I don't see why C++ developers can't.

planteen 8y ago
I think C++ developers do this a lot. I often see links to godbolt.org on Stack Overflow and Bjarne himself on YouTube videos. The tricky part is the are a number of different valid march flags for x86 and ARM that support SIMD.
- microcolonel 8y ago
  > The tricky part is the are a number of different valid march flags for x86 and ARM that support SIMD. Sure, but if you're writing software which works on AMD64, you can see prettymuch every autovectorization opportunity that exists on other platforms. Most of the autovectorizer functionality in gcc and clang is platform-agnostic, AFAIK.
  - planteen 8y ago
    Yes you can see the broad opportunity but various things can easily break vectorization between extensions of x86 and ARM. The first that comes to mind is use of doubles instead of floats. Another is too wide of an inner loop, especially on algorithms that must be tuned for cache line sizes. You can also run into accuracy & stability issues between different x86 instruction extensions - it's really a nightmare to debug those.
  - Something1234 8y ago
    Isn't the best flag `-march=native`? It gives you all the vectorization that your processor supports, or at least I think that's the case? At least if you don't have to provide builds for other people's machines.

wyldfire 8y ago

FWIW clang has a feature called opt-viewer [1] [2] that isn't quite a style guide but instead gives explicit indication when and why it couldn't optimize particular code. [1] https://llvm.org/devmtg/2016-11/Slides/Nemet-Compiler-assistedPerformanceAnalysis.pdf https://llvm.org/devmtg/2016-11/Slides/Nemet-Compiler-assist... [2] https://github.com/androm3da/optviewer-demo https://github.com/androm3da/optviewer-demo

IshKebab 8y ago
Useful, thanks! God knows why they chose YAML though...

jancsika 8y ago

If a failure of auto-vectorization in a hot code path decreases performance enough for the user to perceive it as a bug, then it seems like explicitly maintaining SIMD/NEON code-paths would be preferable to dealing with auto-vectorization black magic. But I've never done either.

gnufx 8y ago
Vectorization failures (where vectorization would be correct) should be reported as a bug. Note that GCC has some parameters to tune vectorization about from forcing it with pragmas.

slack3r 8y ago

It may be black magic now, but people are working on making the black magic something lesser mortals don't have to worry about (eg: https://theory.stanford.edu/~aiken/publications/papers/asplos06.pdf https://theory.stanford.edu/~aiken/publications/papers/asplo...) Unfortunately, no one is actually paying attention to all this research being done in ivory tower academics. Sad!

jcranmer 8y ago
Superoptimization is slow, and it's generally considered feasible only for shortish bits of code. A block of about 30 instructions takes around 10 minutes to superoptimize even on state-of-the-art stochastic superoptimizers. You also need correct semantics for instructions. Go read the PCMPISTRI instruction and try to write out the SMT formulas for it so you can prove equivalence. Floating point is in an even worse state, since most interesting floating point transformations are only legal if you're willing to slacken requirements for bit-equivalence. Superoptimization is not mature enough to become part of the regular compiler flow. What is happening is you're seeing people couple superoptimizers to find missing optimizations in the compiler--John Regehr is basically doing this for LLVM's InstCombine pass with Souper.
- slack3r 8y ago
  Lol, my comment was restricted to SIMD, which definitely does not take 10 minutes. Secondly, no mainstream compiler actually compiles code to the PCMPISTRI instruction. Presumably it was meant to be used directly as assembly. I'm not sure why you are bringing in this obscure instruction into the discussion of superoptimizers. I personally have a paranoid fantasy where NSA/GCHQ introduced this instruction to speed up password cracking. :D
  - jcranmer 8y ago
    You're citing the classic superoptimization paper, although it's actually quite old at this point. The goal of superoptimization has always been to try to compile to the no-real-C-equivalent instructions in an ISA, which includes the weird vector instructions such as PCMPISTRI. (I believe Strata attempted to match some of these instructions, and I think they managed to get formulas for about half of the weird immediate forms--these are the instructions that caused them to match "half" an instruction). In any practical vectorized tight inner-loop, the block you're trying to optimize is inherently going to be large. Superoptimization is exponential in the size of the block being optimized, which limits its utility. That was my entire point: it becomes unacceptably expensive way too quickly to get used in compilers. (Some of the code I'm looking at right now has 100s of instructions in a single basic block, definitely not atypical for a compiler).

abainbridge 8y ago

Hmmm, I feel like I've been waiting for a compiler to get clever enough to auto-vectorize my code since MMX was new. It never seems to happen. I guess I need that style guide. For example, here's a hello-world type SIMD problem: auto-vectorize a simple alpha blending pixel painting routine. struct Pixel { unsigned char r, g, b, a; }; // Draw a horizontal row of alpha blended pixels into a scan line. // Assume clipping is already done. void hline(Pixel *scanline, int startIdx, int len, Pixel c) { len &= 0xfff0; // Let the compiler assume that the length is always a multiple of 4. int invAlpha = 255 - c.a; for (int i = 0; i < len; i+=4) { Pixel &dest = scanline[startIdx + i]; dest.r = (dest.r * invAlpha + c.r * c.a) >> 8; dest.g = (dest.g * invAlpha + c.g * c.a) >> 8; dest.b = (dest.b * invAlpha + c.b * c.a) >> 8; } } And here is GCC 8 _not_ auto-vectorizing it: https://godbolt.org/z/zPZL-J https://godbolt.org/z/zPZL-J Is this the kind of thing you think should be auto-vectorizable by the compiler? If so, any idea how to persuade the compiler to do it?

tomsmeding 8y ago
To properly auto-vectorise this, you need to transform your ArrayOfStructures (AoS) representation to a StructureOfArrays (SoA) form, i.e. put all the r's next to each other, all the g's, etc. Then your operations are nicely in groups of four adjacent elements and the compiler will almost surely vectorise it. I'm no black magician, but I think the fact that the operations you want to do in parallel (the r's of four adjacent pixels) do not access adjacent memory cells, requiring a gather instruction or somesuch, which I hear is either slow or unsupported. Alternatively, it could vectorise the pixels themselves, but that's three elements, not four. Does it auto-vectorise it if you also do the operation on the a's?
- abainbridge 8y ago
  > Does it auto-vectorise it if you also do the operation on the a's? Good point. Combined with fixing my loop increment (that jcranmer made me realize was wrong), I now get some vectory goodness: https://godbolt.org/z/yTJzKH https://godbolt.org/z/yTJzKH No idea what it all means. It'll be interesting to benchmark.

wmu 8y ago

Recently I checked how different compilers vectorize various C++ standard algorithms: http://0x80.pl/notesen/2019-02-02-autovectorization-gcc-clang.html http://0x80.pl/notesen/2019-02-02-autovectorization-gcc-clan... You'll also find there a hint how to rewrite std::replace algorithm to make it vectorizable.