'goading' - platform-agnostic SIMD relying on autovectorization of small loops

[kfjahnke]

As a follow-up to personal communication with @jan-wassenberg, I'd like to propose a technique here which I implemented as an intermediate layer between code intending to 'behave' in a SIMD fashion and the layer which implements the actual SIMD code. The reasoning goes like this:

• to implement a SIMD algorithm efficiently, the program has to provide a SIMD-friendly structure
• this structure is best expressed by using appropriate data types
• generation of the actual SIMD code should remain an implementation detail, and allow for varying 'engines'
• a system of generic types can be used to express the first point in a platform-agnostic way
• and to speed things up, it can be specialized to use a more efficient engine where possible or necessary

In my b-spline library I use this approach to good effect: I define a type vspline::simd_type which acts as a catch-all implementation of a class template structuring intended SIMD programming. This template 'behaves' like a 'proper' SIMD type, but internally, it simply has small fixed-size std::array-like containers and the 'SIMD' operations are implemented as small loops. The template mimicks Vc's SimdArray, and one layer 'above' the 'simdized' type used by vspline for a given elementary type is inherited from Vc::SimdArray if possible, and from vspline::simd_type otherwise. The resulting type is meant to behave in the same way, no matter what it's 'progeny' is. This construction has several nice effects:

• the code can be run without a SIMD library by relying entirely on vspline::simd_type
• when using a SIMD library, one can fine-tune the specialization
• scalar code can be enforced at the intermediate layer by specifying a vector size of one
• platforms not covered by a given SIMD library can still be addressed

The first point is especially important. It allows to run the SIMD-structured code on any machine. At first sight this looks like a good option for testing, but deeper inspection reveals that by communicating the SIMD intent clearly through the code's structure, it can also be 'picked up' by the compiler's optimizer, and, if 'goading' the compiler works as intended, the resulting code may perform a bona fide SIMD operation without the need to actually tell the compiler how to arrive at this solution (like, with intrinsics). It turns out that for a fair amount of code the compiler can provide near-optimal solutions, which it might not have found had the code merely stated it's intent in a scalar form. There is even a chance to get better machine code: If a SIMD library is used to explicitly code SIMD instructions, this process may be opaque to the optimizer. The 'goading' approach is entirely transparent, there are no hard-to-penetrate intrinsics, and optimization can possibly restructure the machine code in a way a human programmer might find hard to fathom and write explicitly.

In my experience, clang++ is especially good at 'picking up' the SIMD intent in goading code, but this is a moving target, compilers evolve quickly, and my experience is limited.

SIMD libraries tend to offer a fallback to scalar code where 'hardware' SIMD can't be had, but this still requires the entire library to be present. Using a small header like vspline::simd_type.h, which has no dependencies, removes the dependency from a given library and makes SIMD usable even on exotic platforms. On the compiler side, it's helpful if the compiler writers specify which small-loop constructs they will likely vectorize, and clang++ offers such documentation.

There is yet another aspect here: 'goading' expresses a SIMD intent, but the compiler, seeing the 'big picture', may decide that SIMD is inappropriate for a given construct, due to a cost model which may turn out that the code is better run without using SIMD instructions. This option may be blocked by explicit SIMD instruction use - a case of overly zealous early specialization.

I hope that this little write-up can add to the effort to make use of SIMD programming more widespread, which I think is critical, especially for number-crunching applications. vspline::simd_type is FOSS, licensed under the expat library. I'd like to see an echo to this post; @jan-wassenberg proposed to start discussing SIMD-related topics on highway's issue tracker, so here we go.

[veluca93]

I like this idea - in particular, I think it might be a good idea to replace HWY_SCALAR with something based on an equivalent of vspline::simd_type. In my experience, SCALAR is the target that requires the highest amount of special-casing, and this would significantly simplify implementations.

It also offers limited support for platforms where HWY doesn't have intrinsics yet.

[kfjahnke]

Precisely. It's good for prototyping, and the 'prototype' may already be sufficiently performant. If a 'real' SIMD implementation arrives later on, it's easy to specialize to it, and then to test if this actually produces any benefit which outweighs the extra dependency and usage overhead. It can also go the other way: compilers get smarter all the time, and one may discover that a new compiler version suddenly produces better code with goading than one's explicit-SIMD efforts.

'collapsing' the type to a vector size of one is optimized away (ideally...), resulting in code which is effectively scalar. For code which is 'forced to scalar' that way, there are some performance issues, though: in SIMD code you often have to execute both branches of a conditional and use masking to distribute the results to some pattern of the vector. 'True' scalar code simply uses if/else and can avoid executing the 'other' branch. This problem with SIMD code may be mitigated by branch prediction, but you can't rely on that.

In my code, I try to capture both the scalar and SIMD form in a single template, which works often enough - as long as the semantics of the operation are the same in scalar and SIMD - hence the use of an arithmetic SIMD type which exhibits the same semantics as a scalar wherever possible. If this is impossible, e.g. when I have conditionals vs. masking, I need to write two forms. In both cases, I use a common functor, and the functor composition code picks the right variant.

[jan-wassenberg]

@kfjahnke
Nice, I agree this will be a helpful option or alternative for passing the intent to compilers, thanks for bringing it up.

It seems useful to make this available to Highway users without requiring them to add/use another wrapper, so we can implement inside Highway as an alternative to the functions implemented using intrinsics.

one may discover that a new compiler version suddenly produces better code with goading than one's explicit-SIMD efforts.

Possibly :) It will be interesting to see how it compares in JPEG XL.

@veluca93

SCALAR is the target that requires the highest amount of special-casing

Right, especially TableLookupBytes (PSHUFB) requires 16 bytes of data. Before we actually remove HWY_SCALAR, we should make sure no one is depending on it, but I also like the idea of eventually removing it.

For the implementation, it seems like std::array could be the minimum viable wrapper? Any concerns about using range for loops?
Finally, I was thinking to default to 16 bytes unless overridden by a HWY_AUTOVEC_BITS option?

[Bulat-Ziganshin]

One more idea: we can add pragmas to loops asking compiler to vectorize them. OpenMP pragmas in particular. Compilers lose opportunities to vectorize code mainly because 1) computation is too complex so they can't find how to express it with SIMD, 2) they see potential dependencies between loop iterations

In the second case, OpenMP SIMD pragma essentially tells the compiler that potential dependency between loop iterations is no actually present, so vectorizing code is fine.

Overall, when writing SIMD code, we usually have to choose between simple code, and rely on compiler's ability to vectorize it (and optionally add vectorize pragmas to each loop), and using intrinsic or libraries like Highway to explicitly write SIMD code - but compatible only with specific platforms. This new approach should allow to write code immediately compatible with any vectorizing compiler, while providing extra optimization on directly supported platforms.

[jan-wassenberg]

Thanks Bulat, good point about the pragma. Looks the the following ones can be useful:

omp simd aligned(ptr, bytes)
clang loop vectorize(enable) (in case of -Os)
#pragma clang fp contract(on) (for fma, not needed if -ffp-contract=fast)

Here's a first attempt : https://gcc.godbolt.org/z/fx5r85cYj

Unfortunately I haven't been able to get clang to load 4 floats from aligned memory, it only wants to load 2.

[kfjahnke]

std::array is a good candidate, but using a dedicated type like vspline::simd_type (which simply contains a 1D C-style array) is probably cleaner, removing a big fat type which may be defined in all kinds of ways in different environments, and makes the result harder to compare between platforms. You don't lose anything by defining your own tailor-made container type, and having e.g. the operator functions built into the type doesn't stop you from also providing the SIMD functionality as functions - one can be expressed in terms of the other, and users can pick what best suits their needs and style. Simply producing std::array as the result of the functions also misses out on fitting the type with additional capabilities (like diagnostics, introspection, echoing to the console etc.) which are nice to have during development.

#include <cstddef>

template < typename T , std::size_t N>
class Simd {
  T _data[N] ;
  // Load member
   void Load(const T* p) {
      for (size_t i = 0; i < N; ++i) {
          _data[i] = p[i]; 
      }
}
} ;
// Load free function template delegating to member function
template < typename T , std::size_t N = 16 >
Simd<T,N> Load (const T* p) {
   Simd < T , N > x ;
   x.Load ( p ) ;
   return x ;
}

In my experience, 16 bytes is a bit short. This may seem strange, it looks as if the 'sweet spot' would be to hit the likely hardware vector size, but I even found that twice that size is a better value for my code. The advantage of coding vector-size-agnostic is that one can easily produce versions with different vector sizes and see how they perform. I think it's best to leave it to the user how many elements they choose, there may be no one right answer, and different parts of the code may perform best with different vector sizes, so the value should not be TU-wide - and not in bits, because often you need vectors with a given number of elements throughout a pipeline, some of which may contain float, others double...

Often the effects only show with real-world code and not in small synthetic benchmarks. Your approach of suggesting to the compiler with a pragma that it should autovectorize is, I think, merley interpreted as a suggestion, and dropping it makes for less clutter. I use -Ofast and, to autovectorize std functions well, also -fno-math-errno.

[jan-wassenberg]

Good point about std::array possibly differing across platforms, I can see the utility of such a tiny wrapper struct; added.

Also agree that the size should be configurable, 16 is just for initial experiments.

I've removed most pragmas and the openmp flag, and switched to -Ofast; unfortunately we still have really poor codegen, even with just adding [u]int16_t: https://gcc.godbolt.org/z/dn64hPv6s

This is disappointing because the HWY_SCALAR version actually autovectorizes well. Would be nice to understand what's going on here.

often you need vectors with a given number of elements throughout a pipeline, some of which may contain float, others double...

Interesting, autovec would have additional freedom here, but Highway type promotion is defined to only look at the lower half of the input, so we get a full-width output and I guess a fixed size in bits would still be ok?

[jan-wassenberg]

A teammate suggested using the special built-in vector types instead of a struct/array: using V = T __attribute__((__vector_size__(16), __aligned__(16)));

And this indeed generates the expected code (after pragma for FMA and builtin_assume_aligned): https://gcc.godbolt.org/z/EMx99n9EY

I was hoping to avoid the special vector types because they are not portable and don't work in MSVC, but that compiler anyway isn't known for autovectorization.

Any thoughts on whether we should use these types, or if there's a way to make this work without them?

[kfjahnke]

I was hoping to avoid the special vector types because they are not portable and don't work in MSVC, but that compiler anyway isn't known for autovectorization.

Any thoughts on whether we should use these types, or if there's a way to make this work without them?

I suggest you take a step back and look at the bigger picture. The assembler results you see may not be what you expect, but they may nevertheless be valid, and they may even be optimal for the amount of information the compiler has about the problem at hand. The main issue is how fast the resulting (real-world) code is, and you only find out about that when you (micro)benchmark your final application. That the hardware vector units are employed does not necessarily make for a faster program. Look at hardware vectorization as one tool among many - the CPU's 'normal' processing has very clever mechanisms (like pipelining, speculative branch execution, branch prediction, high clock rates etc) to make single-lane code execute very fast, and if the compiler decides not to emit vector code, this may be wise, and not considered a failure. Typically, the compiler guys know their business extremely well, and us 'lesser' folks coming along with notions about 'what should come out' may just not be right. Also keep in mind that there is a penalty for switching to use of, say, AVX2, and the relatively small loops you use as test cases may not outweigh this penalty. It's also quite hard (especially when using -Ofast) to stop the compiler from seeing that there is logic in your problem which can lead to shortcuts you did not intend.

What we're discussing here is 'goading'. The important point is that we write code which is intrinsically vector-friendly and which is meant to exploit vector units if that makes sense. In particular, we want to be able to switch from a prototype to a platform-specific, highly optimized version without having to recode anything: the vectorization should be intrinsic to the source code we write, whereas the target should be arbitrary. If the compiler chooses to not vectorize the 'goading' code, that makes it no less valid: the main thing is that it works as expected, and that it can be switched to use 'proper' hardware vector code APIs without changes to the source code. The first point ensures us that our 'vector logic' is correct - which can be quite different from the logic used for scalar code, especially when it comes to conditionals. The second point allows us to figure out whether the API used for specific hardware actually performs any better than other solutions - goading among them as an additional way to run the vectorized source code.

With these considerations, my advice is to keep the code - and especially the goading code - free from any specifics like the attributes you colleague suggests. These specifications may make the compiler produce the assembler code you expect, but I think it should be clear that - especially for the goading code - this is not the main concern. For the goading code, the idea is to keep it simple and stupid, with the most blatantly obvious and trivial inplementation we can think of, so that everybody with a smattering of C++ can instantly grasp what is going on. If the compiler grasps it as well, we may get hardware vector code as an added benefit. By presenting the 'goading' code with a vectorized source code structure, the chances to get such effects may increase, but it's not something we should aim for so hard as to 'force' the compiler to do what we think is right.

I think SIMD-affine people tend to make a mistake: they want to harness the SIMD capabilities of a given hardware. Then they look for a way to code so that these features they want harnessed are actually used. It's a bit of a bottom-up approach, and we have such code already: the intrinsics, awkward as they may be. But the real problem is how to efficiently solve problems, and that's more of a top-down thing: noone can assure you that a given problem will benefit from vectorization on a given platform with a given compiler. You can give it a shot, you can 'suggest' it to the compiler, but in the end, if it turns out that the vector path performs worse, it serves the problem better to avoid it. 'goading' is kind of a middle way: you express the vectorization in your source code's structure without forcing the compiler to actually use hardware vector code. By coding the logic like that, you expose opportunities for vectorization. What concrete machine code arises from that is a different matter. My experience is that the SIMD-friendly code structure helps especially with complex code and long pipelines, and then, sometimes, goading and a specific SIMD API come out nearly equal. And if you want to try next how your code performs with explicit hardware vectorization (like, via intrinsics) you just throw a switch if you have such an API handy.

[jan-wassenberg]

Two engineers with much more in-depth knowledge of compiler internals have had a look.
The problem seems to be that SROA loads are only merged up to 64-bit. I'm told this is
not going to be a quick fix.

The main issue is how fast the resulting (real-world) code is, and you only find out about that when you (micro)benchmark your final application.

Fair point, that's always true. However, we are somewhat sensitive to this because something similar to this 12x slowdown
has led to outages, and users may be tempted to replace the code that caused it with scalar, non-SIMD code (justifiably so, that may actually be faster than SIMD with a 12x handbrake).

we want to be able to switch from a prototype to a platform-specific, highly optimized version without having to recode anything

Agreed. Any user code written to the Highway API is able, and should be able to, switch the codegen (without changing user code) between intrinsics, whatever we end up with here in terms of compiler-friendly loops, and possibly still the scalar target which boils down to single-lane normal C++ which the compiler may or may not vectorize.

For the goading code, the idea is to keep it simple and stupid, with the most blatantly obvious and trivial inplementation we can think of

There appears to be a difference in goals here. We cannot have anything that risks a large speed reduction unless perhaps
users opt-in to a slow mode, but there is already a "simple" mode in the form of HWY_SCALAR.
Given that a current compiler unfortunately still fails at autovectorizing a trivial "sum of int16_t array" example using native code,
I think we will need to use the vector attribute here, though perhaps we can also have an opt-in mode to use an std::array like type for experimentation.

[kfjahnke]

There appears to be a difference in goals here. We cannot have anything that risks a large speed reduction unless perhaps
users opt-in to a slow mode, but there is already a "simple" mode in the form of HWY_SCALAR.
Given that a current compiler unfortunately still fails at autovectorizing a trivial "sum of int16_t array" example using native code,
I think we will need to use the vector attribute here, though perhaps we can also have an opt-in mode to use an std::array like type for experimentation.

I use the 'goading' code as a fallback option. To do so, I can use my simd_type as a base class and derive SIMD types I use in concrete code from this class. Another alternative is to go via a traits class and use that to define which concrete SIMD type should be used for a given set of template arguments - I use the latter method in vspline to route the code to use Vc::SimdArray for the elementary types it can handle and my simd_type for others (like long double). If you're interested, the code is here

The result is that with a given combination of elementary type T and desired lane count N, you get a concrete type which can

• simply be simd_type itself with the small-loop code
• be a class inheriting from simd_type with some methods overwritten
• be a different type altogether like Vc::SimdArray, as long as it has the same interface

This way, one can have a variety of routes to deal with various SIMD libraries, compilers and hardware. With the situation you describe, I'd create a specialization for the given compiler/platform and insert the vector attribute just there, keeping the base class 'clean'. The generic base type allows you to write generic SIMD code, the specializations or routings via traits can produce performance gains by, e.g, using explicit SIMD commands with intrinsics, and that is where your library comes in with it's specific implementation of explicit SIMD code. The 'generic' SIMD type acts like a safety net, as a starting point when tackling new environments, or, with a bit of luck, as a viable alternative if the compiler 'gets it'.

[jan-wassenberg]

To do so, I can use my simd_type as a base class and derive SIMD types I use in concrete code from this class. Another alternative is to go via a traits class and use that to define which concrete SIMD type should be used for a given set of template arguments - I use the latter method in vspline

The traits sound like a good idea because SVE and Risc-V V can't use inheritance, or rather: their "sizeless" vectors cannot be wrapped in a class. That is why Highway relies on non-member functions.

I agree that the concept of a 'starting point' is useful, also to measure the benefit of a specific implementation.
Instead of traits, Highway uses #if HWY_TARGET == HWY_SCALAR to completely replace algorithms for the generic or any other case.

It's still disappointing that builtin vector types seem necessary to get good codegen, that erodes some of the benefits of a fallback (beyond the HWY_SCALAR we already have). I still plan to do this, but on a longer time schedule.

[Artoria2e5]

WRT writing things that compilers (usually) autovectorize, the simd-everywhere/simde project might be interesting to look at. Well, mainly how it annotates the loops and uses builtins.

[kfjahnke]

Am 23.08.21 um 14:02 schrieb Mingye Wang:

WRT writing things that compilers (usually) autovectorize, the simd-everywhere/simde <https://github.com/simd-everywhere/simde> project might be interesting to look at.

Thanks for the hint! It's a different approach to get the same SIMD code to run on different platforms, and one I wasn't aware of previously. Kay

[jan-wassenberg]

@Artoria2e5 yes, thanks, I've occasionally spoken to the author. It is a very impressive effort with N(=number of targets)^2 functions to implement :)

@kfjahnke just a quick heads-up that we're postponing this until there's some progress on autovectorization without needing builtin vector types.