Everyone Should Know SIMD

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 like putting high-performance racing tires on a lemon with a broken engine.

It was the root-of-all-evil-type-premature-optimization, because I wasn't measuring performance, and I wasn't thinking about where the allocations were, etc. Now, I try to model my data as if it were SQL tables, see what my potential "primary keys" could be, and build my data structures around my access patterns.

For example, I used to model trees as structs pointing to other structs on the heap:

    struct Tree {
        tag: TreeTag,
        children: Vec<&Tree>
    }

Now my tree has all the bad characteristics of a linked list (* n nodes * m children), all the fragmentation of multiple heap vectors (* n nodes), and terrible set-up / tear-down time (in this case, Drop alone was taking up a good chunk of runtime).

But a tree can be represented a million ways, and can always be linearized. So now I really consider my access/insert patterns of the tree, whether it's really a tree or some other sort of graph, whether I can store it in a Vec or a Struct of Vecs, etc. Since really looking at things through their access patterns and "primary keys", my code has been much faster and simpler.

This has the added effect that a lot of your data ends up in homogeneous arrays / vecs, which means that the compiler can do its SIMD magic, the CPU can read it from your L1 cache a million times faster, etc. And then when you need to drop down into SIMD yourself, you can write some awesome branchless code.

1. https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...

"More importantly, when this loop matters enough for me to care about a 5x speedup, 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."

Only tangentially related but this is by far the most painful part about optimizing code for JIT compilers like V8. Even changing a constant from 1 to 1.0 somewhere else can change the optimizations performed and lead to an unexpected performance decrease.

Here's a helpful video about leveraging SIMD to solve a concrete performance problem for the dev team that made the game The Witness by Casey Muratori: https://www.youtube.com/watch?v=Ge3aKEmZcqY

I don’t know zig syntax, but wouldn’t it be possible to put this common pattern into a macro and simplify it to mostly a lambda on V?

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 times, and then pack it back into a vector).

- a lot of `std.math` is scalar-only (some functions support vectors, though, and i've got a pr open for one of them and plan to do more).

- i'm certainly missing some intrinsics that i get from xmmintrin.h (rcp, rsqrt, few others).

in general though i'm finding it pretty capable.

mitchell, i know you hang around some of these comments sometimes – i noticed that in ghostty you bring in some c++ libs to do the simd heavy lifting for you. any plans to port that to zig? anything missing from the language or libs that's preventing it?

I just do gcc -O3 and get SIMD without having to learn it