4 ms·

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 th

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
    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;
    - abainbridge 8y ago
      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 https://godbolt.org/z/sEvz2w
jcranmer 8y ago
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.
- abainbridge 8y ago
  > 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.
gnufx 8y ago
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.
- abainbridge 8y ago
  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.
  - gnufx 8y ago
    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.
deleted 8y ago
[deleted]
gameswithgo 8y ago
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

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
  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;
  - abainbridge 8y ago
    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 https://godbolt.org/z/sEvz2w

jcranmer 8y ago

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.

abainbridge 8y ago
> 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.

gnufx 8y ago

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.

abainbridge 8y ago
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.
- gnufx 8y ago
  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.

deleted 8y ago

[deleted]

gameswithgo 8y ago

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