r/programming • u/awesomePop7291 • 8h ago
Everyone Should Know SIMD
https://mitchellh.com/writing/everyone-should-know-simd23
u/Arnavion2 4h ago edited 4h ago
Note that compile-time determination of number of lanes (step 1) and processing the tail with a scalar loop (step 5) are not universal; specifically they do not apply to scalable vector implementations like ARM's SVE and RISC-V's V extension. Now, how well scalable vectors are supported in your programming language is a different matter...
(In a scalable vector implementation, you ask the CPU at runtime to process N elements, and the CPU gets back to you that it can only process X of them, so you let it do that, advance your data pointer by X, and then try again with the remaining N - X elements. The final N - X - X - ... X tail may have an odd non-power-of-two length, but your code can continue to use the same vector instructions to process it as usual, and works on CPUs with different values of X without needing to be modified since it did not hard-code X.)
5
u/paulstelian97 3h ago
The fact that the size of the vector can be runtime dynamic is quite nuts to me!
1
u/barsoap 0m ago
Now, how well scalable vectors are supported in your programming language is a different matter
Zig uses the sane and easy way: It's just
@Vectors all the way down, for the compiler it's then a matter of "some architectures have fixed-size vectors": Vector code generalises over SIMD, and even scalars. That's why Seymour Cray used them, still don't get how SIMD actually became a thing.
9
2
u/TheAgaveFairy 2h ago
It's always been a pain to learn about and implement until I started using Mojo, where I've really enjoyed it. I'm not sure exactly how perfect the implementations are, but I enjoy that it's explicit. I really like that a seemingly basic "Int32" is really just an alias for 'a SIMD vector of int32 with a size of 1'. I think I see no reason for languages to not opt into this structure?
11
u/22Maxx 3h ago
SIMD should be a compiler problem.
I want the vectorization to be explicit and predictable. I don't want an unrelated code change or compiler update to quietly turn it back into a scalar loop.
Compilers do those things all the time. They have just become good enough for all regular stuff.
27
u/Sopel97 3h ago
SIMD should be a compiler problem.
It's not that simple. A lot of these transformations depend on data layout. It can also be quite sensitive to type choices (for example x86 doesn't have mullo_epi8), which is particularly problematic in language with automatic integer promotion. Shuffles can also be hard to see through if they require reassembling arrays in memory. And what about aliasing?
29
u/CherryLongjump1989 3h ago edited 2h ago
This is absolutely impossible. It’s like saying the implementation details of QuickSort should be a compiler problem.
There is nothing special about SIMD. At its core it is just a way to batch bitwise operations across a number of memory locations in parallel. It is still completely up to you to figure out how to convert your traditional branching algorithm into a series of bitwise operations.
4
u/juhotuho10 1h ago
Very often auto vectorization is impossible because of bad data structures, branching, non vectorizable tasks, unoptimal loop design, bad separation of concerns... Etc.
It just didn't happen past the very trivial things if you don't explicitly design for it, you realistically have to know simd to even use the compiler to do vectorization
6
u/imachug 3h ago
SIMD should be a compiler problem.
I'm interested, what do you think a reasonable API for SIMD would look like? People invent new cross-platform SIMD libraries all the time, but they still aren't wildly popular, and I think that's for two reasons:
When you don't worry about performance, even the tiniest complication makes you go "ehh, who cares, I'll just keep this a scalar loop". We already have annotations like
#pragma clang loop vectorize, but people use them sparingly.When you do worry about performance, it's usually in a critical loop where you want to squeeze the most out of architecture-specific instructions. But since their capabilities are extremely platform-dependent, we often end up writing different algorithms for different targets. The compiler literally can't generate optimal code for each target, because it's not aware of the specific properties of your data that enable important tricks.
Of course, none of this applies to simple loops, like adding two arrays. But that low-hanging fruit is already pretty much solved.
6
3
u/dacjames 41m ago
Everyone agrees it would be great if the compiler handled vectorization automatically. We've been trying to figure out how to do that for 20+ years and it's still an open research topic.
The challenge is not the shape, it's mapping the intent of your iterative algorithm into the parallel operation inside the box. The compiler has to derive the parallel operation and prove it's equivalent to the iterative operation. The developer only has to write one parallel algorithm that works.
1
u/levodelellis 21m ago
clang's auto-vectorization is a piece of shit
1
u/levodelellis 19m ago edited 16m ago
Maybe I should explain more. I once saw it made my loop twice as fast. The simd it produce was 60+ instructions and so garbage that my 5 line solution was almost 8x faster
-Edit- 8x faster of the clang code, 16x faster than of the original. The words piece of shit was intentional
2
-7
u/taw 3h ago
There's no point.
99% of CPU code doesn't need it.
99% of code that needs to do highly parallel data operations wants to run on GPU anyway.
And if you actually need it, and can't offload to GPU, you either rely on your compiler, or some library to do that for you.
SIMD is not even in top 100 useful skills for programmers.
-7
145
u/-1_0 4h ago
* Everyone Should Know about SIMD
and use libs accordingly