SIMD in Rust | Hacker News Reader

SIMD in Rust

huonw.github.io

198 pointsdbaupp32 comments

On the last paragraph, for runtime selection of SIMD implementations, would that use something like STT_GNU_IFUNC? Perhaps exactly that on Linux, since it's compiling to ELF, after all.

I would have liked to see benchmarks compared to non-simd rust too. Thankfully this is in the source code. Here's what I get from cargo bench, fwiw:

         Running target/release/mandelbrot-aefed80dbc3f2841

    running 2 tests
    test mandel_naive ... bench:     802,072 ns/iter (+/- 25,106)
    test mandel_simd4 ... bench:     235,853 ns/iter (+/- 6,374)

    test result: ok. 0 passed; 0 failed; 0 ignored; 2 measured

         Running target/release/matrix-58de8ccd4bd58dcd

    running 6 tests
    test inverse_naive   ... bench:       4,967 ns/iter (+/- 251)
    test inverse_simd4   ... bench:       1,984 ns/iter (+/- 94)
    test multiply_naive  ... bench:       2,226 ns/iter (+/- 26)
    test multiply_simd4  ... bench:         897 ns/iter (+/- 32)
    test transpose_naive ... bench:         627 ns/iter (+/- 16)
    test transpose_simd4 ... bench:         361 ns/iter (+/- 7)

    test result: ok. 0 passed; 0 failed; 0 ignored; 6 measured

Yeah, the runtime selection could indeed leverage ifunc when available (the actual dispatch isn't so interesting, since a simple branch on CPUID is perfectly workable in many cases: usually the dispatch is done when calling an expensive, long-running function, so a little bit of O(1) setup is in the noise). The really hard bit is getting dependencies compiled in multiple modes using different features, which will be especially important if/when Rust gets an ecosystem of libraries with SIMD utilities/functions. I hope we do get a wide variety of such things (rather than everyone just using the intrinsics directly, as in C/C++).

BTW, the benchmarks are comparing to non-SIMD rust: the graphs are of how many times faster the SIMD Rust code is than scalar Rust code (i.e. if they were plotted, the scalar bars would all be at 1.0).

Aha, the y-axis is "times faster than scalar", I totally missed that.

To anyone interested, we have a rust port of our general purpose CUDA and OpenCL library: https://github.com/arrayfire/arrayfire-rust

This is in extreme alpha stages and is written by people who are still coming to grips with rust. If anyone wants to chat about it or has some feedback, please drop by over here: https://gitter.im/arrayfire/arrayfire-rust

Nice! I dream of the days when Rust will be the best language for data parallelism, with an amazing ecosystem of libraries for threading, SIMD and GPU programming.

how much longer until I get to use it in something on my desktop that runs 3x faster?

Grab and build Servo? To quote https://lwn.net/Articles/647969/ :

But the results are already impressive; the team said that Servo provides a 2x speed increase when rendering the CNN homepage and a 3x speed-up on Reddit.

Does the library support complex numbers?

Yes! The C32 and C64 data types should give you complex support.

This is _not_ a post about auto-vectorization in Rust (which would have been a lot more interesting!). The provided Mandelbrot Set example is algorithmically similar to loop unrolling with a 4x unroll factor. The strategy works well in this case because neighboring locations in the Mandelbrot Set tend to require similar numbers of iterations to compute.

Ehh, auto-vectorization is a much less interesting problem than doing fun things manually.

Does Rust not already get LLVM's current auto-vectorization for free?

From the article:

  > Speaking of the optimiser, rustc uses LLVM, which is industrial
  > strength, and supports a lot of autovectorisation

I'm sorry you didn't find the blog post as interesting as you hoped. :) As others have pointed out, I talk a bit about how rustc gets autovectorisation by leaning on LLVM in the "Explicit SIMD in the Compiler" section.

In any case, I agree the Mandelbrot example isn't so interesting: I included it because it is relatively simple, well-known and gives a pretty picture (i.e. good for a blog post where a single example isn't mean to be the focus). In fact, manual unrolling catering to autovectorisation is how Rust is currently top of the mandelbrot benchmark game[1], and explains the equal performance of the explicit-SIMD and scalar versions of spectral-norm on AArch64 (although the fact they aren't equal on x86 hints at the lack of guarantees around autovectorisation).

I find the examples like matrix inversion, nbody and fannkuch-redux are more compelling because the vectorised version is far less similar to the scalar one ("strange" shuffles, approximation of floating point ops and dynamic byte shuffles with precomputed values, respectively).

[1]: http://benchmarksgame.alioth.debian.org/u64/performance.php?...

This article could use some disassembly (and LLVM IR) from compiled code to see what a piece of Rust SIMD code looks like when compiled for different architectures. No doubt you've done this when debugging, but it would also be useful for the rest of us.

How well does it work in general? When you write SIMD code, can the compiler keep the values in vector registers or is there spilling going on?

As you can see from the benchmarks, it works basically as well as industrial C/C++ compilers like Clang (if not slightly better) and GCC (although GCC's older and more optimised backend leaps ahead of the LLVM-based compilers in some cases).

I'm planning follow up posts which may involve more assembly/IR, but this is designed to be an introduction/high-level post, and the graphs are meant to serve as a summary/replacement for digging through reems of assembly.

This is cool! A lot of use of SIMD is working on a large array. How does the bounds checking not make this prohibitively expensive? Also, how are the alignment requirements managed?

There is the `load` method on SIMD types, e.g. [1]. This does an unaligned load from any place within an array, with bounds checks, i.e. the safest always-works method.

The bounds checking isn't that bad in and of itself, e.g. for f32x4 it is one bounds check for 4 elements and that bounds check is just a comparison and an extremely well-predicted branch. However, it definitely can be noticable and can inhibit other optimisations.

There's various routes this can be improved for sure, e.g.

- `unsafe` versions of the `load` that don't bounds-check and/or do aligned loads,

- functions that convert a `&[f32]` into a `&[f32x4]` (possibly with prefix and suffix &[f32]'s for unaligned left-overs),

- tweaking the set of optimisation passes the compiler runs to handle the patterns that occur in Rust better (I believe rustc just runs the default set of LLVM passes, which are likely more tuned to C/C++ than Rust, e.g. the IRCE pass[2] should help eliminate more bounds checks but isn't enabled by default because presumably C/C++ don't use bounds checks enough for it to be worth it)

- higher-level combinators/"algorithms" that avoid the need to do the loading/memory-management manually

[1]: http://huonw.github.io/simd/simd/struct.f32x4.html#method.lo...

[2]: https://github.com/rust-lang/rust/issues/22987

Are there any preliminary attempts to integrate this into Servo yet? I'm curious to know the results, if so.

I've done some experimental work, yes. However, I haven't found many places where it will obviously help a lot: it's very easy to use it for 3D transforms (which does a pile of 4D matrix ops, exactly what the matrix benchmarks in the post measure), but other things are less nice.

Weird question, where is the restrict keyword in Rust?

Rust doesn't need such a mechanism, because by default Rust already has an enormous wealth of bulletproof data regarding the aliasing that goes on in your program. Controlling aliasing is in some sense what Rust is all about! :)

If I understand the keyword correctly, it's not really needed in Rust. The Rust compiler keeps very close track of who has a reference (many immutable or one mutable) to a value. There isn't really "accidental" aliasing.

That's awesome. It feels like this alone could, at least theoretically, make rust faster than C on average. Most C programmers are not even aware that the restrict keyword exists and don't use it in places where they could greatly benefit from it.

&mut implies restrict.

My opinion, ensuring zero overhead and zero boilerplate code for calling external libraries will solve the SIMD problem. Anything worth vectorizing will be written in C/assembly.

Rust has inline assembly these days. Between that and approaches like this, I certainly hope using FFI for performance won't always be necessary.

I don't think inline assembly solves the problem. If I optimize any worthwhile problem, I would be smart to do it in a way that is accessible from every modern language.

Rust, being able to expose a C ABI and having roughly the same amount of runtime, is accessible from every modern language.

On the contrary, much of the motivation for this is writing stuff like image decoding libraries in Rust. People often decode untrusted images, so it makes sense to use a memory-safe language to isolate crashes and prevent RCE vulnerabilities without the overhead of spawning a process per image. But image decoding makes great use of SIMD, so not having SIMD in the implementation language will result in a performance regression over the state of the art.

Rust already guarantees zero overhead, and close to zero boilerplate, for FFI calls into C.

However, there's no fundamental reason Rust can't be a viable replacement language for C for these sort of things. As one example, I think it would be great to have Rust used more in the numeric/scientific computing space, where a lot of code is written by non-expert programmers (i.e. don't mix well with C/C++ to get reliable software), so having a compiler looking out is possibly nice.

Also, it should be possible to replace a C component with a Rust one in essentially a drop-in zero-overhead way since Rust can trivially expose a C-compatible interface.

> Anything worth vectorizing will be written in C/assembly.

This isn't the way to go. Once you have to call an external function, you lose all compiler optimizations that might take place. If you write low level "primitive" operations (e.g. matrix multiply and inverse), you will get worse performance by doing external function calls rather than having your code made visible to the compiler so that it can be inlined and optimized.

Additionally, you can't write assembler SIMD code that is portable from architecture to architecture. This can be done in C using extensions but not if you stick to the standard (and support MSVC). Quite a lot of SIMD code can be written portably without having to use architecture specific instructions.

It's definitely a good thing that languages like Rust have native SIMD.

Reply on news.ycombinator.com