Your comment and the linked post made me curious. I benchmarked the AoE and EoA representations in both Rust and Zig and the perf was nearly the same. If anything the EoA variant was very slightly faster in Rust. The idiomatic (enum) Rust version was initially ~5% slower but making it match the semantics (union) of the “naive” Zig variant equalized them.
I work with unsafe Rust code in my professional work and making a union of arrays hadn’t come up before although unions themselves had on many occasions so this was a fun little investigation.
I used Vecs in Rust and with_capacity 1 million, I used alloc 1 million in Zig so it should be relatively apples to apples.
I alternated which was getting written or read based on the mod 2 of the index in both Rust and Zig. TBQH the Rust version is doing more work, I decided to sandbag the Rust version a little and made it allocate and populate two Vecs in the EoA variant. A more apples-to-apples comparison would likely push Rust further ahead unless Zig has auto-vectorization magic that Rust doesn’t (unlikely, given the toolchain overlap)
Both “spam” and “eggs” get tabulated into a spam_total and eggs_total in both versions.
If folks are interested, I have a similar thing in (safe) Rust: columnar.
One seemingly significant difference for sum types is that it preserves the heterogenous sequences, but using homogenous containers and a list of discriminants. You seem to need this if you want things to compose: to store a list of (Result<A,B>, Result<S,T>) you need some way to re-interleave the variants. Good news: it’s ~one bit for Result, and still supports random access! :D (( using succinct data structures )).
The performance can be dramatically better than using owned types in Rust, at least once you get in to list types (replacing Vec rather than Result) and recursive types (e.g. trees). I think in these cases it’s less SIMD and more just avoiding the allocator by using fewer, larger allocations.
AoS to SoA is a non-obvious transformation that’s tricky to automate.
AoE to EoA isn’t remotely related. It sounds special when you write it that way. But it’s just a lot of words for “Keep one type of object in one array at a time”. Something people have been doing since the beginning of time. Both obvious and trivial to do.
[1.] No, people aren’t stupid. [2.] On average, people are of average intelligence. [3.] When you say “people are stupid,” you mean stupid compared to your expectations. [4.] What you’re really saying is “other people aren’t as smart as me.”
2 appears to be merely a tautology. It seems irrelevant to me unless one specifically defines “stupid” as “of below average intelligence”, and neither of these people is bothering to say what they mean by “stupid”. If one defines “stupid” as “of insufficient intelligence” (for some value of “insufficient”), then certainly people could be simultaneously of average intelligence and stupid. 3 approaches what I might say, which is “Define ‘stupid’.”, but in a more confrontational way. 4 is merely an uncharitable assumption. 1 appears to be merely an opinion, with neither an actual argument to substantiate it nor a definition of “stupid” to pin down what the claim means.
Thank you for the nostalgia blast of reading blogspot blogs like “xkcd sucks” and “xkcd isn’t funny”, which were both sometimes accurate and always cringeworthy in their own ways. Man, xkcd sucks, but it is funny.
This is cool, though I am very interested in the “full” version where each entry gets a tag.
For example arrow has two different layouts for an array of enums (it always uses the SoA approach for everything) - with dense or sparse layouts for payloads. I’m not sure I’ve seen a lot of this inside programming languages not data formats… maybe the zig AST stuff mentioned uses that?
Why batch in that way?
(Vec<Egg>, Vec<Ham>)is simpler thanVec<Either<Vec<Egg; Max=4096>, Vec<Ham; Max=4096>>>.Nice to see more awareness about this topic. Made a post last year that may be relevant: https://lobste.rs/s/0d6jxz/when_zig_outshines_rust_memory_efficient
My motivating example was ASTs and memory efficiency, but SIMD-ability is probably the greatest benefit of these transformations.
Your comment and the linked post made me curious. I benchmarked the AoE and EoA representations in both Rust and Zig and the perf was nearly the same. If anything the EoA variant was very slightly faster in Rust. The idiomatic (enum) Rust version was initially ~5% slower but making it match the semantics (union) of the “naive” Zig variant equalized them.
I work with unsafe Rust code in my professional work and making a union of arrays hadn’t come up before although unions themselves had on many occasions so this was a fun little investigation.
I used Vecs in Rust and with_capacity 1 million, I used alloc 1 million in Zig so it should be relatively apples to apples.
Did you only read a subset of the fields?
I alternated which was getting written or read based on the mod 2 of the index in both Rust and Zig. TBQH the Rust version is doing more work, I decided to sandbag the Rust version a little and made it allocate and populate two Vecs in the EoA variant. A more apples-to-apples comparison would likely push Rust further ahead unless Zig has auto-vectorization magic that Rust doesn’t (unlikely, given the toolchain overlap)
Both “spam” and “eggs” get tabulated into a spam_total and eggs_total in both versions.
Everything old is new. BASIC programmers will remember having no structs, and instead having to make them up from arrays using an integer as a handle.
If folks are interested, I have a similar thing in (safe) Rust:
columnar.One seemingly significant difference for sum types is that it preserves the heterogenous sequences, but using homogenous containers and a list of discriminants. You seem to need this if you want things to compose: to store a list of
(Result<A,B>, Result<S,T>)you need some way to re-interleave the variants. Good news: it’s ~one bit forResult, and still supports random access! :D (( using succinct data structures )).The performance can be dramatically better than using owned types in Rust, at least once you get in to list types (replacing
Vecrather thanResult) and recursive types (e.g. trees). I think in these cases it’s less SIMD and more just avoiding the allocator by using fewer, larger allocations.What did you use to make those diagrams?
Looks like excalidraw
That’s silly.
AoS to SoA is a non-obvious transformation that’s tricky to automate.
AoE to EoA isn’t remotely related. It sounds special when you write it that way. But it’s just a lot of words for “Keep one type of object in one array at a time”. Something people have been doing since the beginning of time. Both obvious and trivial to do.
https://xkcd.com/1386/
2 appears to be merely a tautology. It seems irrelevant to me unless one specifically defines “stupid” as “of below average intelligence”, and neither of these people is bothering to say what they mean by “stupid”. If one defines “stupid” as “of insufficient intelligence” (for some value of “insufficient”), then certainly people could be simultaneously of average intelligence and stupid. 3 approaches what I might say, which is “Define ‘stupid’.”, but in a more confrontational way. 4 is merely an uncharitable assumption. 1 appears to be merely an opinion, with neither an actual argument to substantiate it nor a definition of “stupid” to pin down what the claim means.
Thank you for the nostalgia blast of reading blogspot blogs like “xkcd sucks” and “xkcd isn’t funny”, which were both sometimes accurate and always cringeworthy in their own ways. Man, xkcd sucks, but it is funny.
It becomes a lot easier if you have an array programming language that lets you abstract over the rank of function arguments.
This is cool, though I am very interested in the “full” version where each entry gets a tag.
For example arrow has two different layouts for an array of enums (it always uses the SoA approach for everything) - with dense or sparse layouts for payloads. I’m not sure I’ve seen a lot of this inside programming languages not data formats… maybe the zig AST stuff mentioned uses that?