Getting explicit SIMD on stable Rust

[jethrogb]

Your type is private, mine is public but can’t be named.

[burntsushi]

@stoklund I think we are pretty close to the same page modulo maybe some bikeshedding. I’m still skeptical of step 3. When you put it in context, it doesn’t seem like much. It is tempting.

I think my current plan is to keep chugging away at my implementation and write up a pre-RFC in a new thread. If we have broad consensus there, then I’ll mush on to a full RFC.

[stoklund]

Sounds great, thanks!

FWIW, I think that step 3 is realistically blocking stabilization of the current simd crate. It would be nuts to start implementing portable SIMD arithmetic in terms of vendor intrinsics when LLVM has already done all that hard work.

[burntsushi]

Understood. That’s a really important point I think. Would it be possible to unpack that a bit? Or point to something that expands a bit more on just how complex it is? Not that I don’t buy it—but if we’re going to sell a small cross platform API in std to folks, we’ll need a good motivation.

For what it’s worth, while the simd crate couldn’t be stabilized as-is, I feel like one could offer up nice APIs for specific platforms without too much trouble. (e.g., Just x86.) Is that accurate?

[krdln]

What all of this means is that we can punt on the Rusty API for now and move forward only with the vendor defined intrinsic interfaces. The Rust API can come later.

I’m afraid that stabilizing vendor intrinsics first, and a Rustic cross-platform API later may lead to lots of non-cross-platform SIMD code being produced in the period when the only stable way to use SIMD in Rust is via platform-specific intrinsics. To make it harder for people to fall into that pit of non-cross-platform code, I think that Rust has to have a cross-platform SIMD API (at least for simple things like add, mul, cmd and shuffle) ready at the very moment of stabilising platform intrinsics.

We are almost 2 years after Rust 1.0 without stable SIMD support precisely because nobody can agree on what that higher level API looks like in Rust. Actually, that’s probably not quite accurate. Possibly the issue is that Rust the language doesn’t quite have everything we need to make the “best” SIMD API.

The first Rust API doesn’t have to be perfect. It should just allow simple cross-platform SIMD to be possible. It could be just a bunch of opaque types like i32x4 with no public fields and all simd operations available through methods. It could be inside a std::simd::v1 module, which could be just deprecated if the better SIMD abstraction comes up (eg. maybe when the type system evolves to have type-level integers).

[stoklund]

There is a lot of details to work out. Suppose you’re writing impl Mul for i32x4. It would go something like this:

• If MIPS MSA is available, use __msa_mulv_w().
• If ARM NEON is available, use vmul_i32().
• If SSE 4.1 is available, use _mm_mullo_epi32().
• If SSE2 is available, try to cobble something together out of 16-bit multiplications using _mm_mulhi_epi16() and _mm_mullo_epi16(), or maybe _mm_mul_epu32() combined with some shuffling.
• Otherwise, expand into a lane-wise scalar multiplication.

In particular, trying to construct an i32x4 multiplication out of existing SSE2 intrinsics requires some work and knowledge. Work and knowledge that has already been put into LLVM.

This is just one operation for one type. There’s about 150 of those to go through. Then you would need to write individual unit tests for all of them since you’re guaranteed to have picked the wrong intrinsic by mistake at least once. Then find a MIPS machine to run your unit tests on. No, not that one. One with SIMD instructions available.

[burntsushi]

I’m afraid that stabilizing vendor intrinsics first, and a Rustic cross-platform API later may lead to lots of non-cross-platform SIMD code being produced in the period when the only stable way to use SIMD in Rust is via platform-specific intrinsics. To make it harder for people to fall into that pit of non-cross-platform code, I think that Rust has to have a cross-platform SIMD API (at least for simple things like add, mul, cmd and shuffle) ready at the very moment of stabilising platform intrinsics.

I just don’t think this is a good enough reason to delay stabilization. It’s a cost, yes, but it’s one I’d happily pay to get a low level form of SIMD out the door. Regardless of whether we have a Rustic API, we need the low level API on stable Rust.

Also, as has been repeated many many many times in this thread, the set of intrinsics that can be put behind a cross platform API is tiny. Overall, this is the beginning of a stabilization effort that will include thousands of intrinsics.

The first Rust API doesn’t have to be perfect. It should just allow simple cross-platform SIMD to be possible. It could be just a bunch of opaque types like i32x4 with no public fields and all simd operations available through methods. It could be inside a std::simd::v1 module, which could be just deprecated if the better SIMD abstraction comes up (eg. maybe when the type system evolves to have type-level integers).

We cannot keep rehashing this. Please see: Getting explicit SIMD on stable Rust

[burntsushi]

Thank you for spelling that out. Some variation of it will no doubt find its way into the RFC.

[comex]

But you forgot 512-bit (AVX-512 / __mm512i).

Also, you should specify how the per-type versions are distinguished. To avoid adding friction by changing names compared to the vendor standard, I suggest making the relevant functions generic, bounded on traits which would be implemented for suitable vector types. The traits wouldn’t have to be stabilized themselves.

Perhaps same approach could be used to let the many signedness-agnostic functions work on, e.g., both i32x4 and u32x4.

[burntsushi]

Also, you should specify how the per-type versions are distinguished. To avoid adding friction by changing names compared to the vendor standard, I suggest making the relevant functions generic, bounded on traits which would be implemented for suitable vector types. The traits wouldn’t have to be stabilized themselves.

The only way to get around not stabilizing the traits AFAIK is by adding them to the prelude. I doubt that’s going to fly.

Nevermind the fact that I definitely think adding generics to the vendor Intel functions is a bridge too far at this point. If we got there, I think I’d sooner go back to the __m128/__m128i/__m128d types.

[stoklund]

But you forgot 512-bit (AVX-512 / __mm512i).

Nope, I silently omitted it

I would prefer to skip AVX512 in the first round of stabilization. The mask registers are mapped to scalar integers in the C API, and I think we could do something better if we had boolean vectors.

Is there a real demand for AVX512 today? It is available in shipping hardware beyond Xeon PHI?

[comex]

Isn’t that only true for trait methods, as opposed to bounds on functions?

[burntsushi]

Hmm. Good point. My general dislike for adding generics at this point stands though.

[jethrogb]

Also, you should specify how the per-type versions are distinguished. To avoid adding friction by changing names compared to the vendor standard, I suggest making the relevant functions generic, bounded on traits which would be implemented for suitable vector types. The traits wouldn’t have to be stabilized themselves.

I don’t know about non-Intel architectures, but Intel intrinsics all have a different suffix based on the type you’re supposed to pass in.

+1 for punting on AVX-512. Although yesterday’s AWS announcement suggests it’s coming to regular processors sometime soon. OTOH I’ve heard Xeon E5/E7 v5 is still about a year out at this point.

[scottmcm]

Step 1: Common opaque SIMD types

Feels like a great sweet spot. Small enough set to be uncontroversial, just enough traits that it’s possible to use non-horribly.

And I’m pleased to see that, even if you ignore intrinsics, the simple cases can be coded reasonably—no unsafe and fairly ergonomically—in such a way that they even produce LLVM vector intrinsics. For example, this gives %2 = fmul <4 x float> %0, %1 and then mulps %xmm1, %xmm0:

pub fn my_mul(a: i32x4, b: i32x4) -> i32x4 {
    let a: [i32;4] = a.into();
    let b: [i32;4] = b.into();
    [
        a[0] * b[0],
        a[1] * b[1],
        a[2] * b[2],
        a[3] * b[3],
    ].into()
}

__m128i becomes i64x2, i32x4, i16x8, or i8x16.

I think it might need to be more nuanced than that. Something like __m128i _mm_adds_epu8(__m128i a, __m128i b) that “Adds the 16 unsigned 8-bit integers in a to the 16 unsigned 8-bit integers in b using saturating arithmetic” should probably take u8x16s, not i8x16s.

Maybe it’s sufficient to say “a function takes a type implied by the suffix of its name”? That’d justify only providing the signed versions of the ones that don’t care initially, though I bet we’ll want to offer _mm_add_epu32 at some point, despite only _mm_add_epi32 existing officially.

Will adding literally thousands more functions to std impact non-simd-using consumers at all? I take it they can’t go in an intel_intrinsics crate because of needing nightly for something?

Step 3: Portable SIMD operations

Yay!

Given all the llvm intrinsics that take vectors, I suspect there’s a few more. The only one I’ll recommend for the RFC, though is mul_add on floating-point vectors. (Oh, and since we have i32::saturating_add in stable, i32x4::saturating_add would be nice, and there’s an MMX instruction for it.)

And I assume “step 3” isn’t gated on completion of “step 2”, despite the numbering?

[stoklund]

And I’m pleased to see that, even if you ignore intrinsics, the simple cases can be coded reasonably—no unsafe and fairly ergonomically—in such a way that they even produce LLVM vector intrinsics. For example, this gives %2 = fmul <4 x float> %0, %1 and then mulps %xmm1, %xmm0:

Just a word of warning here: It’s easy enough to tickle LLVM’s SLP vectorizer into producing one or two SIMD instructions with tiny toy examples, but this is not a robust alternative to hooking up the real portable SIMD operations (my step 3). LLVM has a number of optimizations that run before the SLP vectorizer gets to see the code, and they can easily obfuscate things by optimizing the separate lane expressions in different ways.

Try creating a larger example, and make sure that there are constant folding opportunities in some lanes, but not in others. That should trip up the SLP vectorizer enough to just give you scalar code. When we have to defend this proposal in RFC form, it would actually be good to have real counterexamples at hand to show that this is not a viable alternative to step 3.

Given all the llvm intrinsics that take vectors, I suspect there’s a few more. The only one I’ll recommend for the RFC, though is mul_add on floating-point vectors. (Oh, and since we have i32::saturating_add in stable, i32x4::saturating_add would be nice, and there’s an MMX instruction for it.)

I was going for conservatism rather than completeness, so I left out many things.

• Fused multiply-add (mul_add) is available on many platforms, but not universally, and it is a very expensive operation to emulate. f64x2::mul_add() requires a 104-bit wide multiplication which you really, really want implemented in hardware.
• Saturating arithmetic is universally available for 8-bit and 16-bit lanes, but not for i32x4. It turns out that nobody actually needs saturating arithmetic larger than 16 bits. I left it out to avoid the asymmetry.
• Comparisons and selects are universally available, but with subtle variations across platforms that we don’t need to resolve now. Compare the semantics of Intel’s blendvps instruction with NEON’s vbsl. The difference is just big enough to get in the way.

Most of these things should be fairly straightforward to implement in terms of vendor intrinsics, which I’m sure the simd crate will do.

I would like to see a second round of stabilization that brings the portable operations up to par with SIMD.js at least, but there are a number of issues to work out first.

And I assume “step 3” isn’t gated on completion of “step 2”, despite the numbering?

Right. The steps represent my priority, not a dependency.

[scottmcm]

(Oops, it looks like I pasted in the wrong code in my previous post. That rust code should have been f32s, not i32s. I won’t edit it since that seems to do weird things to timestamps here?)

Just a word of warning here: It’s easy enough to tickle LLVM’s SLP vectorizer into producing one or two SIMD instructions with tiny toy examples, but this is not a robust alternative to hooking up the real portable SIMD operations (my step 3).

Absolutely.

it would actually be good to have real counterexamples at hand

As you suggested, man was one easy to produce This one, which I’m not surprised didn’t work, does generate vector instructions, but it’s four mulsss, not a mulps

pub fn my_dot_direct(a: f32x4, b: f32x4) -> f32 {
    let a: [f32;4] = a.into();
    let b: [f32;4] = b.into();
    a[0] * b[0] +
    a[1] * b[1] +
    a[2] * b[2] +
    a[3] * b[3]
}

And I guess the inliner is one of the passes that runs before the SLP vectorizer. I was hoping this would inline the vector fmul from my_mul, but nope. No fmul <4 x float> in the LLVM, no mulps in the assembly.

pub fn my_dot_usingmul(a: f32x4, b: f32x4) -> f32 {
    let c: [f32;4] = my_mul(a, b).into();
    c[0] + c[1] + c[2] + c[3]
}

But then a tiny change makes it happy again. This one actually generates rather nice-looking vector operations even for the additions:

pub fn my_dot_usingmul_balanced(a: f32x4, b: f32x4) -> f32 {
    let c: [f32;4] = my_mul(a, b).into();
    (c[0] + c[1]) + (c[2] + c[3])
}

(Well, except for the fact that apparently it didn’t notice that %2 and %4 are exactly the same thing, which I thought SSA was really good at.)

  %2 = fmul <4 x float> %0, %1
  %3 = shufflevector <4 x float> %2, <4 x float> undef, <2 x i32> <i32 0, i32 2>
  %4 = fmul <4 x float> %0, %1
  %5 = shufflevector <4 x float> %4, <4 x float> undef, <2 x i32> <i32 1, i32 3>
  %6 = fadd <2 x float> %3, %5
  %7 = extractelement <2 x float> %6, i32 0
  %8 = extractelement <2 x float> %6, i32 1
  %9 = fadd float %7, %8
  ret float %9

Yay, non-associative floating point math! Makes me want a bunch of sum_unspecified_order() methods (on simd, slices, …), but that’s definitely a post-step-4 bikeshed.

(Hmm, looking at llvm’s fastmath flags makes we want to go make an nnan_f32 type that lowers like that all the way to llvm, and would actually be Ord & Eq. But that’s a distraction for the future…)

[eternaleye]

One thing I think is important to bring up: Both ARM SVE and the RISC-V V[ector] extension (old slides, old video, related work, new presentation a couple days ago with media not up yet) are on the very immediate horizon.

The key distinguishing factor is that they do not have fixed vector lengths.

In addition, there are three main categories of instructions that use SIMD registers:

1. Iterated instructions
   • Parallel add/sub/and/or/xor/etc
   • These are actually quite poorly served by SIMD (see RISC-V slides for summary, or “related work” for detail). Reasons:
     • Needing to handle the boundary cases
     • Code bloat for handling the different register widths of every generation
     • Requires source changes to handle new generations
     • Code written for new generations not backwards compatible
     • Strip-mining loop is boilerplate, ripe for zero-overhead abstraction
   • For these instructions, we might be far better served by intrinsic (or library) functions that take slices of primitive types, and handle the strip-mining for the programmer.
     • These, then, would also work for ARM SVE or RISC-V+V.
2. Permutative/combinatorial instructions
   • PSHUFB and friends; reductions
   • This is a category that is very SIMD-friendly, and does not generalize well to arbitrary width.
   • However, such instructions may see less use than “iterated instructions” outside of crypto/compression.
   • Survey?
   • EDIT: According to someone who was present and watched the new RISC-V talk:
     • I asked krste whether permute-heavy code like crypto and codecs fits into the model at all, he said that they had permutes but there wasn’t time to discuss
     • I also asked about reductions, response was “recursive halving or something”
       • Editor’s note: If you have permutes, then I think they can be used to recover any reduction order under recursive halving.
3. Scalar instructions with large bit-width
   • This covers cases like the AES or SHA acceleration instructions on x86.
   • Heavily architecture specific, heavily purpose-specific.
   • Likely quite worth waiting a while to stabilize.

I think talking about “SIMD intrinsics” as a single unitary thing is a huge mistake: these categories may very well merit being handled differently.

[jFransham]

If I can take a different course on this, maybe there could be a level of stabilisation between “unstable” and “stable”, so that #[feature(...)] can be used on stable but the feature in question is not necessarily included in Rust’s stability story. This would be a more general solution than a special-case libstd-llvm that is only for this one case. It could be that only the small number of features strictly needed for this could be included to start with, but it might also allow us to get things like Macros 1.1 into the bloodstream as soon as possible while keeping the unstable parts explicit in the code.

I haven’t read this whole thread, sorry if something similar or strictly better has been suggested.

[ruudva]

I came here via the Reddit thread. I read the topic two weeks ago but it was already long back then, so I only skimmed through what happened since. I’m sorry for going a bit off topic, but this seems like the best way to share my opinion.

Almost a year ago I wrote Convector, a project in Rust that heavily exercises AVX. This is my experience/wishlist:

• The tooling around target features could indeed be better. I proposed a way to deal with this in Cargo, but we could not reach consensus in the topic. Then we got support for RUSTFLAGS in .cargo/config, so I just put that under source control. It is an ugly hack, but it actually works fine.
• I want access to the raw platform intrinsics with the same names as in the Intel Intrinsics Guide. I’m glad this topic is going in that direction. They are weird and ugly, but at least they are documented and searchable, and they would be consistent with C/C++. One of the things that surprised me about the current intrinsics, is that e.g. _mm256_add_ps is called simd_add instead. The latter looks friendlier, but it is undiscoverable (also because it is not documented, I suppose), but the main issue is, if you go this way you have to draw the line somewhere about what to rename. I propose to not rename anything, especially since the consensus seems to be to not focus on portable SIMD at the moment.
• The types of these intrinsics are sometimes weird (e.g. _mm256_and_ps operates on floats?), but at this level types have little meaning anyway. To some operations, the operands are just “a sequence of bits”, and they might later be interpreted as floats or integers or bitmasks or whatever. Code full of these intrinsics is hard enough to read without all the transmutes. I’m not sure what the best way to go about this is. Maybe an opaque 128/256/512 bit type with methods to cast from and to tuples of float and integer types?