[−][src]Crate slipstream
This library helps writing code in a way that incentives the compiler to optimize the results better (without really doing anything itself).
Modern compilers, including rustc
, are able to come up with impressive ways to
speed up the resulting code, using techniques like loop unrolling and
autovectorization, routinely outperforming what one would hand-craft.
Nevertheless, each optimisation has some assumptions that must be proven to hold
before it can be applied.
This library offers „vector“ types, like u16x8
, which act in a very similar
way as little fixed-sized arrays (in this case it would be [u16; 8]
), but with
arithmetics defined for them. They also enforce alignment of the whole vectors.
Therefore, one can write the algorithm in a way that works on these groups of
data and make it easier for the compiler to prove the assumptions. This can
result in multiple factor speed ups by giving the compiler these proofs „for
free“ and allowing it to apply aggressive optimizations.
Unlike several other SIMD libraries, this one doesn't do any actual explicit SIMD. That results in relatively simpler interface while still working on stable compiler. It also works in no-std environment.
Anatomy of the crate
Vector types
On the surface, there are types like u16x8
, which is just an wrapper around [u16; 8]
.
These wrappers act a bit like arrays (they can be dereferenced to a slice, they can be indexed)
and have common arithmetic traits implemented. The arithmetic is applied to each index
separately, eg:
let a = u8x2::new([1, 2]); let b = u8x2::new([3, 4]); assert_eq!(a + b, u8x2::new([4, 6]));
Most of their methods are provided by traits, especially the Vector
trait. See the
methods there to see how they can be created and how they interact.
All these can be imported by importing prelude:
use slipstream::prelude::*;
The names are based on primitive types, therefore there are types like u8x2
, i8x2
,
f32x4
, f64x2
.
There are some more types:
wu8x2
is based onWrapping<u8>
,wi8x2
is based onWrapping<i8>
.bx2
are vectors ofbool
s.m8x2
are mask vectors. They act a bit like booleans, but they have width and use all bits set to1
fortrue
. These can be used toblend
vectors together, mask loads and stores and are results of comparisons. The representation is inspired by what the vector instructions actually use, so they should be possible for the compiler to autovectorize. The widths match the types they work with ‒ comparing twou32x2
s will result inm32x2
. The lanes can be converted to/frombool
with methods on theMask
trait, but usually these are just fed back to some other vector operations.
Under the hood
The above types are only type aliases. Under the hood, these are implemented in generic way by
types like Packed4
. These can be parametrized by a type and a
length. While the crate disallows carrying different base types (for safety reasons; the crate
makes certain assumptions about the base type), different array lengths are possible ‒ though
for the compiler to make any sense of them, likely only power of two lengths make any sense.
The lengths are specified using the type level numbers from the typenum
crate, eg.
U4
.
The suffix number (4 in Packed4
) means minimal alignment of the whole type, in bytes.
Therefore, while u8
aligns to 1 byte, [u8; 16]
also aligns to 1 byte, u8x16
aligns to
16 bytes (because it uses the Packed16
type). This allows the compiler to use 128bit vector
instructions (SSE) as these expect such alignment.
Vectorization of slices
While it might be better for performance to store all data already in the vector types, it
oftentimes happen that the input is in form of a slice or multiple slices of the primitive
types. It would be possible to chunk the input and load them into the vectors one at a time,
either manually or by using something like the chunks_exact
and zip
. Nevertheless, it turns out to be inconvenient and often
too complex for the compiler to make sense of and vectorize properly.
Therefore, the crate provides its own means for splitting the data into vectors, using the
Vectorizable
trait. This is implemented on const and mutable slices as well as tuples and
small (fixed-sized) arrays of these. The trait adds the vectorize
and vectorize_pad
methods.
As the methods can't know into how wide vectors the input should be split, it is often needed to provide a type hint somewhere.
fn dot_product(l: &[f32], r: &[f32]) -> f32 { let mut result = f32x8::default(); // This assumes l and r are of the same length and divisible by 8 for (l, r) in (l, r).vectorize() { // Force the exact type of l and r vectors let (l, r): (f32x8, f32x8) = (l, r); result += l * r; } // Sum the 8 lanes together result.horizontal_sum() }
Multiversioning and dynamic instruction set selection
If used as in the examples above, the compiler chooses an instruction set at compile time, based on the command line arguments. By default these are conservative, to run on arbitrary (old) CPU. It is possible to either enable newer instructions at compile time (at the cost of not being able to run the program on the older CPUs) or compile multiple versions of the same function and choose the right one at runtime, depending on what the CPU actually supports.
While this library doesn't provide any direct support for multiversioning, it has been observed
to work reasonably well in combination with the multiversion
crate.
Note that using a newer and richer instruction set is not always a win. In some cases it can even lead to performance degradation. In particular:
- Wide enough vectors must be used to take advantage of the 256 or more bits of the newer instruction set (using these with older instruction set is not a problem; the vector operations will simply translate to multiple narrower instructions). This might create larger „leftovers“ on the ends of slices that need to be handled in non-vectorized manner.
- The CPU may need to switch state, possibly negotiate a higher power supply. This might lead to slow down before that happens and might degrade performance of neighboring cores.
- Some AMD processors (Buldozers) know the instructions, but simulate them by dispatching the narrower instructions internally (at least it seems so, one 256bit instruction takes a bit longer than two 128bit ones).
Depending on the workload, both slowdowns and full 2* speedups were observed. The chances of speedups are higher when there's a lot of data to crunch „in one go“ (so the CPU has time to „warm up“, the leftovers don't matter that much, etc).
Performance tuning tips
The sole purpose of this library is to get faster programs, so here are few things to keep in mind when trying.
This library (or SIMD in general) is not a silver bullet. It's good to tackle a lot of data
crunching by sheer force (the hammer style approach), but can yield only multiplicative
speedups (depending on the width of the instructions, on the size of the base type, etc, one
can't expect more than 10 or 20 times speedup, usually less). Oftentimes, more high level
optimizations bring significantly better results ‒ choosing a better algorithm, reordering the
data in memory to avoid cache misses. These can give you orders of magnitude in some cases.
Also, besides instruction level parallelism, one can try using threads to parallelize across
cores (for example using rayon
). Therefore, vectorization should be used in the latter
stages of performance tuning.
Also note that when used on a platform without any SIMD support, it can lead to both speed ups (due to loop unrolling) and slowdowns (probably due to exhaustion of available CPU registers).
It is important to measure and profile. Not only because you want to spend the time optimizing the hot parts of the program which actually take significant amount of time, but because the autovectorizer and compiler optimizations sometimes produce surprising results.
Performance characteristics
In general, simple lane-wise operations are significantly faster than horizontal operations
(when neighboring lanes may interact) and complex ones. Therefore, adding two vectors using the
+
operator is likely to end up being faster than the
horizontal_sum
or the gather_load
constructor.
It is advisable to keep as much in vectors as possible instead of operating on separate lanes.
Therefore, to compute a sum of bunch of numbers, split the input into vectors, sum these up and
do single horizontal_sum
at the very end.
Also keep in mind that there's usually some „warm up“ for vectorized part of code. This partly comes from the need to somehow deal with uneven ends (if the input is not divisible by the vector size). Also, some instructions require the CPU to switch state, possibly lower frequency and negotiate higher power supply, which may even hinder performance of neighboring cores (this is more of a problem for „newer“ instruction sets like AVX-512 than eg. SSE).
Therefore, there's little advantage of interspersing otherwise non-vectorized code with occasional vector variable. The best results are for crunching big inputs all at once.
Suggested process
- Write the non-vectorized version first. Make sure to use the correct algorithm, avoid unnecessary work, etc.
- Parallelize it across threads where it makes sense.
- Prepare a micro-benchmark exercising the hot part.
- Try rewriting it using the vector types in this crate, but keep the non-vectorized version around for comparison. Make sure to run the benchmark for both.
- If the vectorized version doesn't meet the expectations (or even make things slower), you can
check these things:
- If using the
multiversion
crate, watch out for (not) inlining. The detected instruction set is not propagated to other functions called from the multiversioned one, only to the inlined ones. - Make sure to use reasonably sized vector type. On one side, it needs to be large enough to fill the whole SIMD register (128 bit for SSE and NEON, 256 for AVX, 512 bits for AVX-512). On the other side, it should not be too large ‒ while wider vectors can be simulated by executing multiple narrower instructions, they also take multiple registers and that may lead to unnecessary „juggling“.
- See the profiler output if any particular part stands out. Oftentimes, some constructs like
the
zip
iterator adaptor were found to be problematic. If a construct is too complex for rustc to „see through“, it can be helped by rewriting that particular part manually in a simpler way. Pulling slice range checks before the loop might help too, as rustc no longer has to ensure a panic from the violation would happen at the right time in the middle of processing. - Check the assembler output if it looks sane. Seeing if it looks vectorized can be done
without extensive assembler knowledge ‒ SIMD instructions have longer names and use
different named registers (
xmm?
ones for SSE,ymm?
ones for AVX).
- If using the
See if the profiler can be configured to show inlined functions instead of counting the whole runtime to the whole function. Some profilers can even show annotated assembler code, pinpointing the instruction or area that takes long time. In such case, be aware that an instruction might take a long time because it waits on a data dependency (some preceding instruction still being executed in the pipeline) or data from memory.
For the perf
profile, this can be done with perf record --call-graph=dwarf <executable>
,
perf report
and perf annotate
. Make sure to profile with both optimizations and debug
symbols enabled (but if developing a proprietary thing, make sure to ship without the debug
symbols).
[profile.release]
debug = 2
When all else fails, you can always rewrite only parts of the algorithm using the explicit
intrinsics in core::arch
and leave the rest for autovectorizer. The vector types should be
compatible for transmuting to the low-level vectors (eg. __m128
).
Alternatives
There are other crates that try to help with SIMD:
packed_simd
: This is the official SIMD library. The downside is, this works only on nighty compiler and the timeline when this could get stabilized is unclear.faster
: Works only on nightly and looks abandoned.simdeez
: Doesn't have unsigned ints. Works on stable, but is unsound (can lead to UB without writing a single line of userunsafe
code).safe_simd
: It has somewhat more complex API than this library, because it deals with instruction sets explicitly. It supports explicit vectorization (doesn't rely on autovectorizer). It is not yet released.
Re-exports
pub use iterators::Vectorizable; |
pub use mask::Mask; |
pub use types::*; |
Modules
iterators | The |
mask | Bool-like types used for masked operations. |
prelude | Commonly used imports |
types | Type aliases of the commonly used vector types. |
vector | Low-level definitions of the vector types and their traits. |
Traits
Vector | A trait with common methods of the vector types. |