Hacker News Reader

Comment by svantana | Hacker News Reader

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.

View on HN

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

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.

Side note: GCC supports feature based dispatch too[0]

[0]: https://lwn.net/Articles/691932/

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.

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.

I have a similar project in C++ supporting SSE2,AVX2, and AVX512 here: https://github.com/dnbaker/vec.

I've used it for numerical code and sketch data structures, for example. (See https://github.com/dnbaker/frp or 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.

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-assist...

[2] https://github.com/androm3da/optviewer-demo

Useful, thanks! God knows why they chose YAML though...

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

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?

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?

> 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

No idea what it all means. It'll be interesting to benchmark.

The code is not optimal, because there are implicit conversions to int (32-bit values) which are quite expansive. There should be explicit casts to uint16_t, like this: dest.r = uint16_t(uint16_t(dest.r * invAlpha) + uint16_t(c.r * c.a)) >> 8;

Adding a single uint16_t cast like this:

  dest.r = uint16_t(dest.r * invAlpha + c.r * c.a) >> 8;

Seems to get all of the benefit. The result is 34 instructions in the loop. (Was 38).

Amazingly, switching from gcc 8.2 to gcc trunk, reduces the instructions in the loop to 18. See https://godbolt.org/z/sEvz2w

There are a few issues impeding vectorization that I see:

1. The memory loads are not stride 1. They're stride 12, effectively.

2. You have i8 -> i32 -> i8 operations going on. Mixed size conversion is generally problematic for vectorization.

3. You're storing 3 bytes of every 12 bytes. The compiler cannot generate extra stores, so it has to introduce masked stores. That's expensive.

The optimal vectorized code for this sort of algorithm is probably an unroll-and-jam: load 4 pixels, shuffle the vectors into r/g/b/a vectors for computation, do the computation, and then shuffle them back into r/g/b/a vectors for storage. This requires some code rewriting--inserting a dummy dest.a = dest.a * 1.0; might convince the compiler to store, although it could well eliminate the store before vectorization.

This sort of thing is why you end up needing a more specialized language for vector codes, such as ISPC.

> The memory loads are not stride 1. They're stride 12, effectively.

Stride 16, no? Anyhow, that's a bug. I shouldn't have put the +=4 in the loop iteration increment. Once I fixed that and added a dummy set of dest.a, then I get auto-vectorization. Woo-hoo. See the link I posted in my reply to tomsmeding.

Here's GCC 8 providing diagnostics (see also -vec-all)

    $ g++ -march=haswell -Ofast -fopt-info-vec-missed x.C -c
    x.C:8:23: note: interleaved store with gaps
    x.C:8:23: note: not vectorized: complicated access pattern.
    x.C:8:23: note: bad data access.
    x.C:8:23: note: not vectorized: not enough data-refs in basic block.
    x.C:12:41: note: not vectorized: no grouped stores in basic block.
    x.C:8:23: note: Build SLP failed: unrolling required in basic block SLP
    x.C:8:23: note: Build SLP failed: unrolling required in basic block SLP
    x.C:14:3: note: not vectorized: not enough data-refs in basic block.

and here's GCC nearly-9:

    $ g++ -march=haswell -fopt-info-vec-all -Ofast x.C -c
    x.C:8:23: optimized: loop vectorized using 32 byte vectors
    x.C:5:8: note: vectorized 1 loops in function.
    x.C:12:14: note: ***** Re-trying analysis with vector size 16
    x.C:8:23: note: ***** Re-trying analysis with vector size 16

In addition to what others have said, you typically need "restrict" on array args, and -ffast-math, or at least -funsafe-math-optimizations (in -Ofast), for things like reductions. (You need -funsafe-math-optimizations for NEON generally, per GCC docs.) A BLAS-like library still passes its tests with -ffast-math.

I've recently had GCC 8 get about 2/3 the performance on haswell for a generic C optimized DGEMM micro-kernel as the hand-optimized one of similar structure which uses intrinsics/assembler. Without checking, the expert expects the performance difference to be due to prefetch and unrolling, which the generic kernel doesn't leave to the compiler.

Wow, magic flags I've never seen before - look useful.

As I understand it, -ffast-math is NOT useful here. That only effects floats and doubles.

Yes, that was meant to be a general remar. This probably most often comes up for floating point, at least in my circles, and the similar option to fast-math that the Intel compiler defaults to contributes somewhat to the myth of its greatly superior code. Likewise restrict isn't relevant here -- you'd see notes about aliasing from opt-info otherwise.

there is no floating point here so you don't need ffast-math, the problem might be that you need to have r/g/b each in their own array, rather than an array of r.g.b structs

> 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.

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.

> 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.

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.

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.

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/asplo...)

Unfortunately, no one is actually paying attention to all this research being done in ivory tower academics. Sad!

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.

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

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).

Don't be ridiculous, dude. No compiler is actually compiling to PCMPISTRI. It's meant to be used directly as assembly.

Of course I could be wrong. If you do know of any open-source compiler which compiles code to PCMPISTRI, let me know.

Superoptimization is not exactly exponential, it is NP-hard.

Of course, in the paranoid conspiracy I was referring to in my previous comment I predict the NSA/GCHQ is also using this directly via assembly. xD

Recently I checked how different compilers vectorize various C++ standard algorithms: 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.

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.

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.

Reply on news.ycombinator.com