Towards fearless SIMD

Half the point of using SIMD intrinsics rather than embedding assembly is that register allocation and instruction scheduling are performed by the compiler. Using intrinsics certainly does not guarantee that exactly the corresponding instructions will be emitted in exactly the given order.

Right, I've run into this a number of times, especially when porting code originally written for 32 bit to 64 bit. Besides compilers getting better, I think there's another factor - it used to be that a compelling reason to write asm is to get good utilization of a limited number of registers. But especially on aarch64 (and, in the not too distant future, AVX-512), there are a lot more.

Higher level abstractions are a good idea, but the problem is, are you able to exploit the capabilities that the chip exposes? For simple things like computing a scalar function elementwise over a vector, no problem, but a lot of the more interesting problems don't fit such simple templates.

As someone coming from CUDA I think you‘re on the right path. CUDA unifies multicore and vectorization parallelims. Crucial here is hardware support for branching (including early returns) even if it degrades performance. This allows a CUDA kernel being programmed in a programmer friendly way that is often already fairly performant, and the actual mapping to hardware is deferred to kernel invocation where it‘s straightforward to specialize. I think this concept is something that CPU (programming) could learn from GPU. Why not adopt the concept of kernels?

I think so too, that SIMD is too low-level to be utilized effectively. Luckily joe_the_user enlightened me with this little gem on a previous post: https://news.ycombinator.com/item?id=17419917

Or for the lazy:

I don't know about tensor flow in particular but are little-known methods of running "general purpose" parallel programs on GPUs. Specifically, H. Dietz' MOG, "Mimd on GPU". It's a shame the project hasn't gotten more attention imo.

http://aggregate.org/MOG/

See: https://en.wikipedia.org/wiki/Flynn%27s_taxonomy for explanations of terms.

The compiler can optimize intrinsics, though. Why shouldn't it be able to?

I agree that somewhat with AVX2 and especially with AVX-512 there's probably less reason to write intrinsics if you have a vector language. But for now SSE2, SSSE3, and SSE4 are still the bread and butter for SIMD on x86, and there are some important instructions (Fabien Giesen goes into detail at [1]) that you really have to think about how to use effectively. For example (this is mentioned at the end), all horizontal adds on x86 are awful except for PSADBW, which is really limited, as Intel designed it in a fit of myopia to target only motion estimation in contemporary codecs, and it requires you to basically design your whole algorithm around it.

[1]: https://fgiesen.wordpress.com/2016/04/03/sse-mind-the-gap/

For the simple SIMD cases where the computation doesn't have any horizontal dependencies (except for a total reduction step), there's little need for any sort of intrinsic usage. (Although you may need some compiler hints to push it to autovectorize).

The real problem is that SIMD hardware sets tends to have lots of instructions that have mixing of horizontal lanes. The scope and performance of these mixing instructions varies greatly from implementation to implementation, and these kinds of instructions are hard for compilers to automatically pick up. It's the latter case that means you need the SIMD intrinsics to be exposed to use the hardware effectively.

Clang supports vector types for C and they're still nowhere near as fast as using intrinsics. For whatever various reasons, compilers tend to do pretty poorly at producing properly vectorized code. I think part of this is that it's hard to encode all the information you need to vectorize properly (this loop will run some power of 2 number of times, these pointers won't alias, etc)

Even using intrinsics is dicey sometimes - compilers spill registers more often than can make sense. I think the ideal situation would be if you could somehow hint at register scheduling without writing asm yourself, but compiler are still a long ways from that.

I find intrinsics to be a useful level of abstraction because it allows me to control and automate the code generation in C++ without having to know the details of register scheduling, etc. It also means I don't have to hand write intrinsic algorithms for every architecture -- I have template libraries that can take a rough specification of the architecture characteristics and generate approximately appropriate intrinsic code. It is neither hand writing all the architecture-specific intrinsic code nor trusting the compiler to do a good job. I started working this way when I used to target code at a really weird mix of exotic vector/parallel computing hardware, and it worked nicely.

The real problem is that, in my experience, compilers universally do a poor job of auto-vectorization/parallelization unless the code pattern is blindingly obvious. All of the "higher level abstractions" I've seen are no better at finding vectorizable patterns than the compiler does -- which makes sense since they are both just software. It ends up being syntactic sugar. The amount of effort required to trick compilers into doing the right thing, plus the things they won't do at all, is such that the complexity is worse than just writing the intrinsic code directly. Writing a lot of intrinsic code directly far from optimal but fortunately those intrinsics are available in languages like C++ that can abstract much of that.

Compilers will not consistently generate competent auto-vectorized for the foreseeable future. I've seen very little forward progress in the decade I've been exposed to it. There are still some relatively simple non-vectorized code patterns that compilers currently have a difficult time detecting and doing optimized code generation for.

Yes, SIMD intrinsic programming is often worthless unless implemented for every target architecture. Let me give you an example case; my target production architecture rarely changes, but I want my program to run on every developer computer where CPUs are heterogeneous.

Now, I think the problem is that it is tying optimizations to instructions rather than CPU architectures. When I ported code from an I7 to an I9 it seemed that instruction latency changed. Still, if you are only supporting limited computational targets any hooks at all help.

But why intrinsic rather than assembly? Because usually vector extensions in GCC work well enough, and when they don't intrinsics are easier for me (a man who rarely needs to write assembly and doesn't have the time to beat the compiler in 99.99% of cases).

And a minor point... I really wish GCC had a pragma which allowed me to specify a function should be optimized to multiple targets and then install the thunks automatically.

I think what you're looking for is ISPC.[0][1] It distinguishes between 'uniform' (scalar) vs 'varying' (vector) variables[2] and applies SIMD instructions pretty much transparently. It defaults to varying, whereas I think for a general-purpose C-like compiler you'd want scalar by default and explicitly declare eg:

  vector float add2(float base,vector float offs)
    {
    return base + 2*offs;
    }
  double sum(double* ar,size_t ln)
    {
    vector double x = (vector)0.0;
    while(ln >= sizeof vector) /* == # of simd lanes */
      {
      x += *ar; /* maybe this needs some kind of cast? */
      ln -= sizeof vector; /* == 1 on arches with no simd support */
      }
    /* this part's definitely not done properly */
    double buf[sizeof vector]; *buf = x;
    double ret = 0.0; /* slurp up the last few */
    for(size_t i=0; i<ln ;i++) ret += buf[i] + ar[i];
    return ret;
    }

0: https://pharr.org/matt/blog/2018/04/18/ispc-origins.html

1: https://ispc.github.io/

2: https://pharr.org/matt/blog/2018/04/26/ispc-volta-more-on-pe...

Nice! This is much simpler than faster. Thanks for dropping the link here.

I really need to revive my multithreaded, SIMD-ified Rust PNG decoder someday with something like this…

Your library is actually mentioned in the linked article

> Another crate, with considerable overlap in goals, is simdeez. This crate is designed to facilitate runtime detection, and writing the actual logic without duplication, but leaves the actual writing of architecture specific shims to the user, and still requires nontrivial unsafe code.

I don't know if you've ever seen Kokkos[1], but that's one of the big C++ frameworks for taking parallel loops and using templates to generate code for SIMD and multiple cores. They also support GPU code generation to some degree. The main issue is compile time, which gets pretty bad when you start using it in non-toy applications.

I can't find the reference right now, but there have been some attempts to augment C++ compilers to understand the semantics of the library directly, basically treating the template metaprogramming as a DSL instead of general-purpose. This can be speed up the compile times dramatically, but of course you lose generality and the compiler has to be customized to understand every library it wants to optimize. Overall it seems like there is more research to be done on doing this in a safe way without paying through the nose with compile time.

[1]: https://github.com/kokkos/kokkos

That doesn't give you run-time dispatch based on available hardware capabilities. So you either need virtual functions (and take the associated perf hit), or some other solution like the linker tricks mentions, or cached JIT, or....

In an LLVM context it also means you don't get runtime feature detection. You would need to build N dlls and then write code to load the proper one at runtime based on feature detection.

JITs could solve that problem, but few JITs currently do very much auto vectorization, because they don't have time.

I think autovectorization is differently-fearful rather than fearless; you live in perpetual dread of the wind changing and suddenly your code doesn't autovectorize any more.

I've spent quite a bit of time looking at autovectorization, but didn't write about it much here, as it's only good for a pretty small subset of problems. One subtle gotcha I ran into is that `round` doesn't autovectorize, but `float` does, even though today's chips have perfectly good vector round instructions. See rust issue #55107 for a deep dive into that problem.

Autovectorizing is quite a long way away from being as or more performant from using intrinsics or asm.

This makes sense when you think about it. The compiler would either need to be extremely capable of generalizing about some kinds of arithmetic, or it would need millions of special cases to recognize. By writing your own vectorization, you are basically covering your singular special case on your own.

Your formatting didn't work, but no, it doesn't "look painful."

What you wrote does not guarantee vectorization, it just relies on autovectorization.

Rust already does autovectorization magically behind the scenes thanks to LLVM (which Julia also uses), but explicit SIMD makes it a guarantee.

From the asm you posted I have no idea whether it's optimized or not; it looks like two virtual function calls (calll %eax). Also, while I'm sure Julia is nice, the GC makes me worry about whether it'll work well in real-time audio synthesis (my primary use case).

Your code only shows that

    gen_sinwave(113.0)

calls

    gen_sinwave(1113.0, 0.0, 0.1)

(which are the default arguments). It is usually better to use @code_llvm because the LLVM IR is typically easier to read.

    julia> @code_llvm gen_sinwave(1113.0);
    
    ; Function gen_sinwave
    ; Location: REPL[2]:2
    define nonnull %jl_value_t addrspace(10)* 
    @julia_gen_sinwave_345638059(double) {
    top:
      %1 = call nonnull %jl_value_t addrspace(10)* @julia_gen_sinwave_345638060(double %0, double 0.000000e+00, double 1.000000e-01)
      ret %jl_value_t addrspace(10)* %1
    }

However, defining

    function gen_sinwave(freq, init=0.0, step=0.1)
        data = collect(init:step:freq)
        fin9_shaper.(data)
    end

and looking at

    @code_llvm gen_sinwave(1113.0, 0.0, 1.0)

we can see that there is a lot of auto-vectorization going on

No, it's not about panicking. It's undefined behavior to run code compiled with CPU features that aren't supported by the current CPU. See: https://github.com/rust-lang/rfcs/blob/master/text/2045-targ...

There are some other ideas for making it easier to reason about safety at this level: https://github.com/rust-lang/rfcs/pull/2212

Can you point to where you heard about unsupported SIMD causing a panic? I'd like to fix that because it's really wrong!

Single Instruction Multiple Data

https://en.wikipedia.org/wiki/SIMD

ELI5: Your processor can process more data in parallel.

If you have for example loop that has something like this in the body:

a[i] + b[i] = c[i]

Using SIMD processor can make all this operations same time:

a[i] + b[i] = c[i]

a[i+1] + b[i+1] = c[i+1]

a[i+2] + b[i+2] = c[i+2]

a[i+3] + b[i+3] = c[i+3]

Normally in one iteration you would only get one of this addition done without SIMD, thanks to SIMD you can have multiple.

If you're shipping binaries, you don't know the exact architecture in advance (because there are many extensions to x86 and you don't know if the end user is running a new enough processor to use all of them). If you don't use them you are likely leaving performance on the table. So you want to select the fastest option supported by the processor you happen to be running on. You can do this with fairly minimal peformance impact by linking in different versions of the function at runtime, but this requires some support from your compiler and runtime environment.