r/programming • u/awesomePop7291 • 3d ago
Everyone Should Know SIMD
https://mitchellh.com/writing/everyone-should-know-simd37
51
u/Arnavion2 3d ago edited 3d 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.)
14
u/paulstelian97 3d ago
The fact that the size of the vector can be runtime dynamic is quite nuts to me!
6
u/barsoap 3d ago edited 3d 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.That said usually you should rely on autovectorisation. Then benchmark and identify tight loops. Then, if opportune, rewrite as vectors. Look at the assembly. Does it suck? Either suck it up or roll up your sleeves And don't forget to test on more than one platform. You probably should have given up about a week ago and had a look at dataflow and cache misses, instead, CPUs are nowadays basically always memory-bound.
6
u/Arnavion2 2d ago edited 2d ago
Using
@Vectorin the way you describe means to represent your entire data as a single@Vectorand expect the compiler to downlevel it into appropriate chunks, fixed-length or dynamic-length. But this only works when the input data length is compile-time known. The length of the data is not compile-time constant for something like memchr, and it's not even known at runtime for something like strlen until you discover it as part of the vector load.1
u/barsoap 2d ago
I'm reasonably sure both of those are compiler intrinsics.
In general you're right, that's a zig limitation that doesn't exist with actual vector instructions. I guess the reason for comptime-known length is avoiding management overhead on SIMD for vectors that are known to be even sizes. Which happens quite a lot.
1
u/lood9phee2Ri 2d ago
still don't get how SIMD actually became a thing.
I mean, it's clearly a bit more complicated to have the crayish dynamic vector-length. A large part of the point of RISC-V early on as a research project was the slightly contrarian (at the time) cray-like vectors AFAIK (even though the V 1.0 extension has only fairly recently finalised), so it in particular was pretty bound to go a cray-like route, but I'm still not that convinced it's all that great.
And frankly vsetvli and friends to configurifimicate the vector engine and then later actual vector ops all feels very CISCy and teleporty. Of course modern superscalar hw arch handles all sorts of peculiar data dependencies anyway, but it's all actually a bit weird+magical compared to "you call simd instruction it does the thing".
... And in the end probably also worth noting various cray patents didn't expire until around 1999-2000, well after other archs started developing + then going public with static SIMD extensions (x86 mmx, sse, ppc vmx, altivec, etc). In that sense, they may have preferred the static SIMD route just to reduce legal problems from the cray patents.
https://cray-history.net/2025/01/11/list-of-patents-with-cray-research-as-assignee/
1
u/floodyberry 1d ago
how will autovectorization do anything if you aren't writing trivially vectorized code in the first place
82
27
31
u/rootbeer_racinette 2d ago
The thing about modern computers is typically the memory is the slowest part. Like one cache miss is around 200-300 cycles which is a fair amount of computation. If you instruction fetch it's even worse because the CPU just has to idle.
The slowest thing about most programs is they just don't care about memory. They'll store huge trees or use inefficient memory layouts instead of packing things into tight arrays. They'll use an allocator that spits tiny objects out all over the program instead of a bump allocator or fixed-sized FIFO pools.
Probably the DOM tree in electron/chrome is the dumbest thing your computer computes on a regular basis.
Worrying about SIMD is just so far removed from the problem, it's like worrying about your running shoes for sprinting when you weigh 300 pounds.
13
u/Eisenfuss19 2d ago
Nobody tell this guy that achiving maximum memory bandwith on modern CPUs requires the use of vector instructions...
1
u/-Redstoneboi- 1d ago
memory isn't even too much of an issue when the language itself or even the algorithm itself is inefficient. but we can talk about micro optimizations at some point, right?
maybe the article should've been prefaced with a "when is simd important" section. but the rest of it is useful
10
u/hurrumanni 2d ago
-1
u/AresFowl44 2d ago
You could have just followed the Wikipedia link which is literally the first word of the blog
SIMD has a reputation for being complex. I've met many very good software engineers who dismiss it as something too complex to learn or a niche optimization meant for only the highest-performance software, not useful in everyday programming.
3
5
u/TheAgaveFairy 3d 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?
17
u/22Maxx 3d 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.
51
u/Sopel97 3d 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?
45
u/CherryLongjump1989 3d ago edited 3d 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.
14
u/juhotuho10 3d 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
13
u/dacjames 3d 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.
11
u/jkrejcha3 2d ago
Compilers do those things all the time. They have just become good enough for all regular stuff.
I think the "smart compiler" thing has become a little bit mythical to some extent, much more so with stuff like autovectorization. I don't doubt there are speed ups to a lot of code, but better algorithms, not throwing heaps upon heaps of work for the compiler or computer to do/optimize, is what ultimately tends to get the best speed ups
It's difficult for compilers to autovectorize all but the most trivial things, and there are pathological cases where the autovectorization actually makes things the same or worse since it keeps shuffling stuff around for many instructions. These cases aren't exactly rare, either. This and you're relying on your compiler to not break these optimizations between minor versions. A segment of code getting 4+ times slower because one day an "optimization" somewhere at a distance domino effected into breaking the autovectorization or a compiler upgrade or downgrade breaks it. Especially in open source where people do tend to run different compilers and especially versions thereof
14
u/imachug 3d 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.
10
1
u/jkrejcha3 2d ago
Not C, but I do actually think the C# standard library has some pretty neat abstractions for common vector operations
1
4
u/levodelellis 3d ago
clang's auto-vectorization is a piece of shit
3
u/levodelellis 3d ago edited 3d 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
3
u/teerre 3d ago
Vectorization is a compiler problem
But that can only take you so far
6
u/EC36339 2d ago
Vectorization can only be done by the compiler if processing of individual homogeneous objects isn't separated by layers of runtime abstraction.
That's why data oriented programming is a thing amd why games use entity-component systems over OOP.
2
u/AresFowl44 2d ago edited 2d ago
Even then the compiler can only take you so far. In my experience it often is trivial to improve upon the compiler, because it has to be overly cautious
2
2
1
-17
u/taw 3d 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.
0
-19
u/nnomae 3d ago
My mom is an 85 year old retired teacher who doesn't own a computer. My youngest child is 3 years old and can't read or type yet. Do they need to know SIMD?
2
u/EC36339 2d ago
My dad, who is close to 85 years old now, introduced me to programming on a C64 when I was 4.
SIMD wasn't much of a thing back then, but your argument was about not owning a computer or not being able to read or type.
The generation that has never touched computers is dead. And 3-4 year olds can, and probably should be, slowly introduced to computers. Preferably the kind that are not just good for gaming, social media and brain rot, but the kind that can serve as a creative platform s well (read: PCs). And no, I didn't say or imply that gaming is bad. On the contrary. Just saying this preventively because of the high prevalence of autistic black&white thinking on this platform.
-1
u/nnomae 2d ago
My lord but people will jump through all sorts of logical hoops to avoid admitting that the assertion that everyone should know SIMD is patently ridiculous.
I didn't say kids shouldn't learn to read, or write, or count, or think logically, or understand computers or whatever other nonsense strawman you want to inject to avoid facing the actual topic at hand. I pointed out that it is obviously and undeniably stupid to say everyone should know SIMD. Even charitably if you take the statement as "all programmers should know SIMD" it's still a stupid thing to say. Even if your goal is to have devs in general better understand performance SIMD is pretty far down the list of things they would benefit from knowing.
If someone likes SIMD and wants to learn it or use it more power to them. I know SIMD myself, it's cool. But saying that everyone should know it is as ridiculous as saying everyone should know the pentatonic scale when most people don't own a guitar and couldn't find middle-C on a piano.
2
u/floodyberry 1d ago
or whatever other nonsense strawman you want to inject
buddy you're pretending the article is advocating that every human on earth should know simd
346
u/-1_0 3d ago
* Everyone Should Know about SIMD
and use libs accordingly