Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Everyone should know SIMD

mitchellh.com

Post reply on HN
Print view View original

51–60 of 263 posts

Re: Everyone should know SIMD

#51

Post by groundzeros2015 »

Rendello wrote: post #24

I like SIMD, but before super-optimizing your code with SIMD and the like, really consider your data structures and access patterns. I've been singing Data-Oriented Design's praises, so I'll just collect all my comments here [1], but I think it's a good approach to optimization. I played around with SIMD in my old code (in Zig), but my approach to modelling datastructures was so antithetical to optimization, it was l…

This. Tables are an efficient implementation of general graphs. It’s the best one I know of (unless your graph can be specialized).

Re: Everyone should know SIMD

#52

Post by to11mtm »

boricj wrote: post #46

Everyone doesn't need to know SIMD. Mechanical sympathy is an important passive perk for software architects to cut down the number of reworks down the line, but I would rate benchmarking and being able to identify bottlenecks as more important everyday skills. I'm working on a voxel space renderer homebrew for the PlayStation. I only have so many cycles to spend on rendering before it becomes a slideshow, so I count…

> Mechanical sympathy is an important passive perk for software architects to cut down the number of reworks down the line

We might be talking on different levels but when it comes to, on an opposite end of 'Should I use SIMD'... a databases a level of mechanical sympathy at a 'base' level is still important. e.x. row-by-row updates vs batching or bad logic where a 21k entry in clause forgot about unicode rules on columns and breaks an index [0]... is still super important.

[0] - That one is real, thanks lazy bodyshop having their people use copilot and yet, we get the same billable hours, nothing is done faster, and management is too stupid to pay attention...

Re: Everyone should know SIMD

#53

Post by mitchellh »

ivanjermakov wrote: post #49

I respect (and fear a little) those who intentionally utilize SIMD in their implementations, but I believe it's a bit too much of a semantic shift for 2-5x performance gain. Good news is that modern compilers are more than capable of emitting SIMD code even if original source is nothing but. Most software's poor performance would be fixed long before SIMD comes into play. Reduce obvious DB/server round trips, bad dat…

> Good news is that modern compilers are more than capable of emitting SIMD code even if original source is nothing but.

They're really not (I have a whole section on it in the blog post). This example in the post doesn't auto-vectorize, for example. And its a pretty big part of the overall throughput for plain text runs (ascii or unicode). Really, the point of that section is that almost nothing auto-vectorizes, backed up by LLVM docs and published research.

Instead, writing 12 lines for a 5x gain is way easier than crossing your fingers and hope someone else pays your bills.

Bigger picture, the real point is that this stuff isn't complicated. You wouldn't copy and paste 100 lines because you hope the compiler "lifts this into a for loop", you just write the for loop cause you know how and its simple.

Similarly, the common case of "process N values in parallel" is very simple. Write a dozen lines of code you're comfortable with. No need to pray the compiler people saved your bacon.

Re: Everyone should know SIMD

#54

Post by yunnpp »

mitchellh wrote: post #11
ashton314 wrote: post #4

Earlier quoted context omitted.

In the article, Mitchel mentions how this doesn’t always work. In fact, as someone who’s worked in compiler development, I can say it’s a small miracle when it does work.

Case-in-point, the example in my own post doesn't auto-vectorize with LLVM or GCC at highest optimization levels. Basically, compilers will never auto-vectorize loops with an early loop break afaik.

You need to let the compiler know that there are at least 4 or 8 elements to process. This may require padding data and/or having a second loop after the main one that processes the remainder You start the post with:

> There is an opportunity to use SIMD. SIMD turns those into this: > > for (8 byte chunk in bytes) { /* ... */ }

If you actually wrote that loop, there is a good chance the compiler (gcc specifically) will auto-vectorize.

In any case, the more manual SIMD optimizations I have seen require reworking the data altogether, not just processing N elements at a time. For example, instead of packing two 4-vectors into two registers to do a dot product, pack the XXXXs, YYYYs, etc. into 4 vectors and compute 4 dot products for the price of one. That not only requires having 4 vectors to process, but also thinking how exactly they are packed in registers.

I don't know why qurren is downvoted. You really should see if you can get the compiler to auto-vectorize first (possibly padding data structures and loops) before you write anything by hand.

Re: Everyone should know SIMD

#56

Post by BoingBoomTschak »

dnautics wrote: post #21
wrl wrote: post #14

i was having a conversation with a friend recently about simd in zig (which i have recently picked up and been having a pretty good time with). i find that simd writes decently well, though there's a few weird things: - some builtins purport to work on simd vectors but actually just unpack the vectors and do their work per-element (e.g. running `@sin()` on a `@Vector(4, f32)` will unpack the vector, run `@sin()` 4 ti…

> some builtins purport to work on simd vectors but actually just unpack the vectors and do their work per-element (e.g. running `@sin()` on a `@Vector(4, f32)` will unpack the vector, run `@sin()` 4 times, and then pack it back into a vector). this is reasonable because there isn't really a generalizable "good way" to unroll trig functions for simd. if you really care about speed youre better off implementing to the…

https://sourceware.org/glibc/wiki/libmvec ?

Re: Everyone should know SIMD

#57

Post by AlotOfReading »

dnautics wrote: post #21
wrl wrote: post #14

i was having a conversation with a friend recently about simd in zig (which i have recently picked up and been having a pretty good time with). i find that simd writes decently well, though there's a few weird things: - some builtins purport to work on simd vectors but actually just unpack the vectors and do their work per-element (e.g. running `@sin()` on a `@Vector(4, f32)` will unpack the vector, run `@sin()` 4 ti…

> some builtins purport to work on simd vectors but actually just unpack the vectors and do their work per-element (e.g. running `@sin()` on a `@Vector(4, f32)` will unpack the vector, run `@sin()` 4 times, and then pack it back into a vector). this is reasonable because there isn't really a generalizable "good way" to unroll trig functions for simd. if you really care about speed youre better off implementing to the…

The loop dependency on a poly isn't all that hard for compilers to unroll, and most correctly rounded implementations are polys. You're often paying only a couple cycles' worth of stalls.

We can see this in action. LLVM implements sin() with a correctly rounded double poly [0]. Let's ignore range reduction and throw the core into compiler explorer to be autovectorized [1]. uiCA estimates a theoretical latency for the inner loop of 15 cycles, and the code achieves 18.

I suspect most custom implementations would do worse than this.

[0] https://github.com/llvm/llvm-project/blob/165c472d65cd62eb33...

[1] https://godbolt.org/z/rGGq8aG38

Re: Everyone should know SIMD

#58

Post by tapirl »

wrs wrote: post #45
losvedir wrote: post #44

This is an interesting article. I don't really work with low level enough languages for this to matter (unless - does this ever show up in Javascript somehow?). I guess I don't understand the "reduce" step. It seems like you have to be careful not to "undo" all the benefit from SIMD. Sure, it can compare 8 values in parallel, but then if you have to look at each of the 8 answers in turn you're back to where you began…

Yes. "`@reduce(.And, ...)` combines every boolean using `and` and returns a single boolean." If it's true (the common case here) then you proceed to look at the next 8 bytes. If it's false, you apply a @bitcast (turn the booleans into bits) and @ctz (find the first 0) to get the index of where it was false.

Maybe I'm wrong, but should it be @clz instead?

Re: Everyone should know SIMD

#59

Post by bigwhite »

The Go language has long lacked official support for SIMD instructions, which means it has been at a disadvantage in terms of performance optimization. In recent years, with Go 1.26, an experimental version of the SIMD/ArchSIMD packages was introduced for AMD64 architecture. With Go 1.27, a portable version of the SIMD package was also added. Now, we can fully utilize native SIMD instructions to optimize go program performance.

- https://pkg.go.dev/simd/archsimd@go1.26.5

Re: Everyone should know SIMD

#60

Post by Rendello »

ktimespi wrote: post #43

The biggest barrier I faced learning SIMD is the weird naming convention for intrinsics. Once I got past that, it was fairly simple. mcyoung's articles were also super helpful

One of my favourite articles is "SIMD-friendly algorithms for substring searching" by Wojciech Muła [2]. If you were unfamiliar with SIMD and just jumped into the code, it'd be incomprehensible due to the intrinsics, but the generic algorithm description at the top is pretty simple if you take some time understand it.

It blew my mind once I understood what was happening, because it's quite clever but one of those "I could've thought of that" algorithms. There was some pretty good discussion on it last year (feat. ripgrep). [2]

1. http://0x80.pl/notesen/2016-11-28-simd-strfind.html

2. https://news.ycombinator.com/item?id=44274001

Post reply on HN