This post assumes at least a vague level of familiarity with the concept of SIMD CPU instructions (x86 SSE/AVX and ARM Neon), where the CPU can perform a single operation on multiple scalar values simultaneously. There is a lot of x86 assembly here to demonstrate what’s happening but you don’t have to be able to read it.
This is not a super deep dive, just a writeup on something I found sort of interesting. All assembly was generated using Compiler Explorer with the Rust 1.98.0 stable compiler (because I wrote most of this before 1.98.1 was out, you should definitely be on that instead of 1.98.0 if you’re not already).
In the context of compilers, auto-vectorization is when the compiler uses vectorized SIMD CPU instructions to implement high-level code that only operates on scalar values, and in a way that provably behaves identically to a non-vectorized implementation. In many data processing contexts this can dramatically improve performance…when it happens.
I’ll note up front that if you want to be 100% sure that a piece of code is using vectorized CPU instructions, you can’t rely on auto-vectorization at all unless you’re willing to look at the compiled assembly every time the code changes. You need to use either compiler intrinsics or some library that wraps them with a higher-level interface (or raw assembly if you want to be really sure what the CPU is executing, as ffmpeg does). In many use cases this requires changing larger amounts of code to operate on vector values instead of scalar values. That is also an interesting topic! But not what this post is about.
With that out of the way…
Take this very simple Rust function that computes a sum of products over two float arrays:
|
|
(I made the size a constant so that the compiler will omit length and bounds checks, and I made it large so that the compiler won’t fully unroll the loop.)
This should be trivial for a compiler to auto-vectorize, but. Here’s that compiled with target-cpu=x86-64 and opt-level=3 (the default for --release builds):
|
|
It’s using SSE instructions and 128-bit vector registers (xmm0, xmm1, etc), but it’s only using 32-bit scalar arithmetic instructions (addss, mulss) and 32-bit scalar load instructions (movss). This isn’t vectorized at all! Those SSE scalar instructions take vector registers as operands, but they only operate on the lowest 32 bits.
The x86-64 target includes SSE and SSE2 as baseline features, so the compiler could use 128-bit / f32x4 vector instructions here, but it’s choosing not to. (x86-64 does not enable SSE3 or SSE4 by default because the earliest amd64/x86_64 CPUs don’t support them, but those aren’t needed to vectorize this.)
Does enabling AVX instructions make any difference?
|
|
(I’m enabling AVX2+FMA instead of AVX because those just add more instructions on top of AVX, and nowadays most CPUs that support AVX will also support AVX2+FMA. AVX2 isn’t useful in this example but FMA definitely is!)
Compiled:
|
|
…They’re the same picture code! It’s using AVX’s newer VEX instruction encoding instead of the legacy SSE encoding (hence why most of the instructions start with v and the add/mul instructions have 3 operands instead of 2), but functionally this is exactly the same code as before except it only uses 3 vector registers instead of 4.
Does rewriting the function to use a manual loop instead of iter::zip and fold look any better?
|
|
I’m not going to paste the assembly here because the answer is no, no it does not. This compiles to the exact same assembly as the first version.
The main problem here is that the compiler can’t safely reorder floating-point arithmetic operations because IEEE 754 floating-point arithmetic is not associative, i.e. (a + b) + c is not necessarily equal to a + (b + c). They’ll generally be equal within some margin of error, but due to floating-point rounding semantics they may not be exactly equal.
The natural way to 128-bit vectorize this function is to process the input arrays in chunks of 4 while accumulating into an f32x4 vector, then sum over the accumulator vector at the end. This is impossible to do without reordering addition operations, which the compiler will not do because it might change the final result for some inputs.
To prove that this is a float-specific issue, here’s an integer version of the same function (with SSE4 enabled because it makes the generated code shorter and simpler):
|
|
Compiled:
|
|
I’m not going to go into detail on what exactly this is doing, but it did auto-vectorize! paddd and pmulld are i32 vector arithmetic instructions, and movdqu is an i32 vector load instruction. It’s using xmm* registers so the vector size is 128-bit / i32x4.
Back to the float version, what if the function chunks manually, so that the compiler can theoretically use vector instructions without needing to reorder anything?
|
|
Compiled:
|
|
Oh hey, it auto-vectorized!
It’s using f32 vector arithmetic instructions (addps, mulps) instead of scalar (addss, mulss), and it’s also using f32 vector load instructions (movups). Everything after the jne is to reduce the final f32x4 accumulator to a single scalar f32, so scalar addss instructions are expected there. (Along with some fun instructions like shufps and unpckhpd)
This is better than needing to use x86_64 intrinsics, but it isn’t ideal. Manually iterating in chunks of 4 prevents the compiler from taking advantage of larger vector sizes if they’re available, such as AVX’s 256-bit vectors, which can hold and operate on f32x8 values. Here’s that same function compiled with AVX2+FMA enabled:
|
|
VEX encoding allows the compiler to do the same thing in fewer instructions (also SSE3’s movshdup), but it’s still using 128-bit vector registers (xmm*) even though 256-bit vectors are available. It’s also not using any 128-bit FMA instructions, I believe because FMA has slightly different rounding behavior than separate mul+add instructions, so using FMA instructions here might change the result.
Some compilers have flags to enable float optimizations that are not strictly safe, such as GCC’s -funsafe-math-optimizations, or the maybe better-known -ffast-math which is a superset. Among other things, this includes -fassociative-math which allows the compiler to assume that float arithmetic is associative so that it can reorder float arithmetic operations. This may change the result for some inputs (hence an “unsafe” optimization) but generally enables the compiler to generate more performant code.
Rust used to not have any reasonable way to do anything like this on stable (for my own definition of reasonable), but now it does! Rust 1.98 stabilized algebraic operators for floats. These allow you to declare per-operation that you’re okay with the compiler making optimizations that may change the result as long as the optimized code is algebraically equivalent to the original. Yes, this includes potentially reordering operations.
Let’s try this out:
|
|
The syntax is very Java-like, but if you were using these frequently then you could implement something like the standard library’s Wrapping<T> newtype, where you’d overload the arithmetic operators to delegate to the algebraic_* functions. (I’m slightly surprised this isn’t already in std, but I suppose it was easier to ship the core functionality by itself before shipping any conveniences on top of it.)
Compiled:
|
|
This is a lot more code than the manually chunked version, but it definitely auto-vectorized!
The manually chunked version did two f32x4 multiply+add operations per loop iteration. This one does four, and it’s also accumulating into two different f32x4 accumulators (xmm0 and xmm1) that it adds together right after the loop ends. From my not-super-scientific testing on a Zen 4 CPU, this is actually noticeably faster than the manually chunked version! Presumably using two accumulators is friendlier to the CPU’s out-of-order execution hardware. (You may have noticed that the auto-vectorized i32 version above also used two accumulators.)
Now with AVX2+FMA enabled:
|
|
It’s now using 256-bit / f32x8 vectors (ymm* registers) and fused multiply-add instructions (vfmadd*ps), with no code changes other than sticking #[target_feature(enable = "avx2,fma")] on top of the function!
Similar to the 128-bit SSE version, this one does four f32x8 FMA operations per loop iteration, but it accumulates each into a separate f32x8 accumulator rather than only using two accumulators. I’m not sure why, probably some heuristic on optimizing for AVX vs. SSE.
Just for fun, here’s a version that attempts to use x86_64 AVX intrinsics (yeah it’s ugly):
|
|
Compiled:
|
|
It’s similar to the auto-vectorized version, but each loop iteration does five f32x8 FMA operations into a single f32x8 accumulator. Pretty direct translation of the Rust code, only unrolling the loop a bit.
For me, this performs significantly worse than the auto-vectorized AVX version, actually even a little worse than the auto-vectorized 128-bit SSE version! This seems to be caused entirely by this version using only one accumulator (because that’s what the Rust code said to do) while the auto-vectorized versions use multiple accumulators. Yay out-of-order execution (I assume).
And…that’s all I’ve got here! I’m not entirely sure this was a useful excursion, but I found it interesting, particularly that auto-vectorization did much better than my naive intrinsics implementation (when the compiler is allowed to reorder additions).
Postscript: Aligned Loads
Whether you’re manually vectorizing or auto-vectorizing, you can get a noticeable performance boost by guaranteeing that vector loads/stores are always on a vector size boundary, if possible. The compiler will generally use aligned load instructions (vmovaps) instead of unaligned (vmovups) if it can guarantee the address is aligned, but on modern CPUs unaligned loads from aligned addresses perform just as well as aligned load instructions, so aligning the data improves performance regardless of whether the compiler emits aligned load instructions.
In Rust, you can accomplish this by making a newtype and sticking #[repr(align(N))] on top of it, where N is in bytes:
|
|
Then you could implement Deref so that you can pass an &AlignedF32Array<LEN> to any functions that expect a &[f32; LEN], or you could make functions take &AlignedF32Array<LEN> as a parameter if you want to guarantee at compile time that the data is aligned.
Postscript 2: AVX-512
I didn’t paste an auto-vectorized AVX-512 version because it looks almost exactly the same as the AVX2+FMA version, only using 512-bit / f32x16 vectors (zmm* registers) and with 2 extra instructions at the end to add the 256-bit halves together (vextractf64x4 followed by vaddps).
Using 512-bit vectors may not improve performance much if at all depending on the CPU, and on some CPUs it may even worsen performance. Intel Skylake-X seems to be particularly problematic given that the compiler will not use 512-bit vectors at all here when optimizing for target-cpu=x86-64-v4, which is roughly Skylake-X as a baseline.
On my AMD Zen 4 CPU, 512-bit vector performance is ~equal to 256-bit on the same total amount of data, which is unsurprising given that Zen 4 implements 512-bit vector operations by double pumping its 256-bit vector units. I’ve read that Zen 5 has a decently performant 512-bit vector implementation but I don’t have one to test on.
All that said, on CPUs that support it, AVX-512 (or “AVX10.1” as Intel is rebranding it) is still useful even if you never use 512-bit vectors. Some of the new instructions are really nice to have (e.g. masked loads/stores) and you get twice as many vector registers for all vector sizes, so AVX-512 can improve performance of 256-bit vector code that can take advantage of the new functionality (i.e. not this trivial example).