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.
"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
no macros in zig, but yes you could metaprogram it. types are first class values at compile time so you could do that sort of specialization if you wanted.
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?
> 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 precision you care about (you might not want full precision)
i don't disagree – i have my own internal vector lib of approximations and whatnot for various tradeoffs of precision and speed, so i just use those. it's just that zig has a pretty strong stance of "no unexpected/obscured code execution" so it was surprising to see a vector-capable function that was just a bunch of scalar functions in a trench coat.
maybe functions that don't actually support actual vector execution just shouldn't work on vector arguments. i also wouldn't expect `@sin()` to expand in-place out to a full cephes-like sin implementation. maybe a function call.
> mitchell, i know you hang around some of these comments sometimes
hi im here
> 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?
The major limitation of Zig's vectors is that they're compile-time only. So if you're building redistributed software that compiles for a baseline CPU target, it won't be as optimized as it could be for YOUR possible machine.
Highway compiles our SIMD modules for different hardware configurations and at startup does a CPUID fingerprint to figure out which to load. That way even baseline has AVX512 etc. implementations, and we just activate the right one at runtime.
We only use Highway for our hottest hot paths that we feel benefit from that specialization.
No plans to port that (although, I spent hundreds of dollars and slop-forked it into Zig with the help of this good boy GPT and it worked great actually, but I didn't want to maintain it).
ahaaa, yeah, i don't personally do any runtime switching but i hear that as a deal-breaker from other folks.
it's interesting – i've found that zig tends to extend my vectors to the native width of the platform and then operate on them there. e.g. i had a `@Vector(2, f32)` that i was using as a demo and the generated assembly was promoting it to 256 bits and using avx2 instructions on it!
Most scalar-to-SIMD conversion requires changing the design of data structures and algorithms to be effective. Compilers are required to exactly reproduce the specified data structures in a deterministic way for obvious reasons.
Even if compilers were clever enough to transform your data structures and algorithms for SIMD (they're not), the data structures are a contract that can't be unilaterally modified.
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.
And -march=native or at least -march=x86-64-v3 or similar, alternatively identifying relevant functions and manually invoking FMV and uarch specialization via target_clones. Plus non-integer code can generally not be autovectorized in normal-math mode since FP is non-commutative.
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:
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...
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.
- 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?
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 precision you care about (you might not want full precision)
maybe functions that don't actually support actual vector execution just shouldn't work on vector arguments. i also wouldn't expect `@sin()` to expand in-place out to a full cephes-like sin implementation. maybe a function call.
hi im here
> 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?
No plans to port it. For others, this is referencing highway: https://github.com/google/highway
The major limitation of Zig's vectors is that they're compile-time only. So if you're building redistributed software that compiles for a baseline CPU target, it won't be as optimized as it could be for YOUR possible machine.
Highway compiles our SIMD modules for different hardware configurations and at startup does a CPUID fingerprint to figure out which to load. That way even baseline has AVX512 etc. implementations, and we just activate the right one at runtime.
We only use Highway for our hottest hot paths that we feel benefit from that specialization.
No plans to port that (although, I spent hundreds of dollars and slop-forked it into Zig with the help of this good boy GPT and it worked great actually, but I didn't want to maintain it).
it's interesting – i've found that zig tends to extend my vectors to the native width of the platform and then operate on them there. e.g. i had a `@Vector(2, f32)` that i was using as a demo and the generated assembly was promoting it to 256 bits and using avx2 instructions on it!
oh interesting. though i suspect that isn't zig and thats llvm.
Even if compilers were clever enough to transform your data structures and algorithms for SIMD (they're not), the data structures are a contract that can't be unilaterally modified.
The best SIMD optimizations likely require changing your data format from AoS to SoA.