The idea that arrays of structs are inherently more cache friendly and thus data-oriented-er is a bit reductive of the whole practice of data-oriented code. The point is to optimize data layout for access patterns. Putting fields of a struct into their own arrays is only actually an optimization if you're only accessing that field in-bulk. And if so, why is it even in a struct in the first place? If you use all fields of a struct in your algorithm, then an array of structs is the optimal way.
Same with row-major vs. column major, accessing contiguous data is faster than non-contiguous data, so you should align your algorithms and data structures.
Worth mentioning that you can always safely switch between AoS and SoA. Either can represent the other; all you've done is transpose the data. The same is not true of AoE/EoA. The AoE [Spam1, Egg1, Spam2, Spam3, Egg2] has no corresponding EoA that can represent it.
What they're actually doing is an AoE => AoEoA transformation: find batches elements with the same tag and reorder the elements so that redundant tags can be eliminated. Essentially, a kind of run-length encoding. It's a nice idea.
an Enum of Arrays would be an enum where each enumerator was a product of each possible enumerator. there would be N^M enumerators where N is the length of the array and M is the number of enumerators. for example, if the original type was enum { red, green } then the enum of array[3] would have to be an enum containing the 8 enumerators:
so that's essentially completely useless. i think the exact same problem would occur with array-of-tagged-union to tagged-union-to-array "transformation".
you can't just say "hey: arrays and structs and unions are words and if you can do array of struct and struct of array and enum is also a similar word, then why not enum-of-array?".
while tfa talks about "batches" of items with the same tag, and the advantages therein, that isn't something captured by the example given, at least without extending the EoA to a variable sized array of EoA and something else to track the number of items in a "run" (as in RLE).
this is better thought of as a data-structure problem than a type theory.
I don't think I've had the need for a uniformly tagged array of enums. Generally, when I do an AoS to SoA transform that includes tagged data, I just factor out the tag into its own array. In fact, if the tag is 2-valued, I just build a bitmap, rather than burning a whole byte. If the tag is a resource indicator, then I have a group of 1-hot bitmaps.
The SoA transformation makes sense to me and is quite general. The EoA transformation on the other hand feels like a rare special case though it seems perhaps less rare for the OP.
Either way, these types of optimizations are typically marginal in the context of end to end performance of most programs. It's good to have some knowledge of these kinds of techniques, but most of the time it makes sense to do the thing that is most straightforward to implement and optimize later once the program is already working. Of course if the problem maps neatly onto EoA then that should be preferred in the initial implementation. I though in my 30+ years of programming cannot think of a particular problem that I have solved that would have been enhanced by this.
It's an alternative to OOP. You can get there via a series of transformations:
1. Start with OOP (heap-allocated objects with shared base structs)
2. Transform to using tagged unions instead
3. Transform to the approach outlined in the OP (I call it the "encoding" approach in this talk: https://vimeo.com/649009599)
It's handy because you get to use an index to refer to an object, and you get serialization benefits. The zig compiler uses this pattern in quite a few places:
Rough idea: model everything as relational data - define 1 table for each state. membership of a record in the table corresponding to state X implies that record is in the given state X.
> the reason why you would put an enum in table form, is to reduce control flow impact. Given this, it's when we aren't using the enumerations to control instruction flow that it's fine to leave them alone
An example of the latter might be some kind of state machine, where you can write branch-free code to determine the successor state from current state, and no other processing needs to branch on the state tag.
This is a somewhat, hmm, bilingual post. The enum in question here is what Zig calls a tagged union, while Rust calls it an enum, with what Zig calls an enum being the degenerate case where the tag is the only payload.
I thought this would be about std.enum.EnumArray[0], an array of some T which is indexed by an enum. I've gotten a lot of mileage out of those as well. But it's about std.MultiArrayList[1], as used with a tagged union. I've had occasion to use that with structs, but not with unions, and didn't actually know that you could, although finding out it makes sense.
Actually a variation on MultiArrayList which is optimized for homogenous collections of one specific union variant, since if that's the useful way to structure the data then the tag would be redundant to store one of per element.
Good read, mostly wanted to add a few links for those who want to know more. The comptime metaprogramming used in MultiArrayList is a great illustration of what Zig is capable of IMHO.
> This is a somewhat, hmm, bilingual post. The enum in question here is what Zig calls a tagged union, while Rust calls it an enum, with what Zig calls an enum being the degenerate case where the tag is the only payload.
To be fair, I think that most languages typically use enum to refer to the same thing as Zig; if anything, Rust (and Swift, iirc) are somewhat outliers for using that term for tagged unions.
I often use the term "sum types" for them, since I think it helps explain why they're useful compared to "product" types like structs or objects or tuples. I've heard people refer to them as "algebraic" types, but I don't really like that as a term for them because that feels like it should refer to sum and product types as a categorization rather than one of the categories specifically. Unfortunately, "sum type" doesn't really work super clearly in verbal conversations that often; people often tend to hear it as "some types".
Yeah, I wish the author had just mentioned what language they were using in the blog post text. I was looking at it and I couldn't identify it. Now I know it is Zig, but I'm not familiar with Zig so I can't identify it by sight. I was looking at it and thinking "this looks a bit like Rust but isn't Rust".
All the same is true for enums.
What they're actually doing is an AoE => AoEoA transformation: find batches elements with the same tag and reorder the elements so that redundant tags can be eliminated. Essentially, a kind of run-length encoding. It's a nice idea.
you can't just say "hey: arrays and structs and unions are words and if you can do array of struct and struct of array and enum is also a similar word, then why not enum-of-array?".
while tfa talks about "batches" of items with the same tag, and the advantages therein, that isn't something captured by the example given, at least without extending the EoA to a variable sized array of EoA and something else to track the number of items in a "run" (as in RLE).
this is better thought of as a data-structure problem than a type theory.
Either way, these types of optimizations are typically marginal in the context of end to end performance of most programs. It's good to have some knowledge of these kinds of techniques, but most of the time it makes sense to do the thing that is most straightforward to implement and optimize later once the program is already working. Of course if the problem maps neatly onto EoA then that should be preferred in the initial implementation. I though in my 30+ years of programming cannot think of a particular problem that I have solved that would have been enhanced by this.
1. Start with OOP (heap-allocated objects with shared base structs)
2. Transform to using tagged unions instead
3. Transform to the approach outlined in the OP (I call it the "encoding" approach in this talk: https://vimeo.com/649009599)
It's handy because you get to use an index to refer to an object, and you get serialization benefits. The zig compiler uses this pattern in quite a few places:
* https://github.com/ziglang/zig/blob/77c63ac36034db577a9287c5...
* https://github.com/ziglang/zig/blob/77c63ac36034db577a9287c5...
* https://github.com/ziglang/zig/blob/77c63ac36034db577a9287c5...
* https://github.com/ziglang/zig/blob/77c63ac36034db577a9287c5...
One example that I frequently deal with that can benefit from this is compiler data structures.
So why not simply default to this instead of defaulting to Interfaces/traits doing dynamic polymorphism?
Makes everyone a bit more happy.
https://www.dataorienteddesign.com/dodbook/node4.html
Rough idea: model everything as relational data - define 1 table for each state. membership of a record in the table corresponding to state X implies that record is in the given state X.
> the reason why you would put an enum in table form, is to reduce control flow impact. Given this, it's when we aren't using the enumerations to control instruction flow that it's fine to leave them alone
An example of the latter might be some kind of state machine, where you can write branch-free code to determine the successor state from current state, and no other processing needs to branch on the state tag.
I thought this would be about std.enum.EnumArray[0], an array of some T which is indexed by an enum. I've gotten a lot of mileage out of those as well. But it's about std.MultiArrayList[1], as used with a tagged union. I've had occasion to use that with structs, but not with unions, and didn't actually know that you could, although finding out it makes sense.
Actually a variation on MultiArrayList which is optimized for homogenous collections of one specific union variant, since if that's the useful way to structure the data then the tag would be redundant to store one of per element.
Good read, mostly wanted to add a few links for those who want to know more. The comptime metaprogramming used in MultiArrayList is a great illustration of what Zig is capable of IMHO.
[0]: https://ziglang.org/documentation/master/std/#std.enums.Enum... [1]: https://ziglang.org/documentation/master/std/#std.multi_arra...
To be fair, I think that most languages typically use enum to refer to the same thing as Zig; if anything, Rust (and Swift, iirc) are somewhat outliers for using that term for tagged unions.
Yeah, I wish the author had just mentioned what language they were using in the blog post text. I was looking at it and I couldn't identify it. Now I know it is Zig, but I'm not familiar with Zig so I can't identify it by sight. I was looking at it and thinking "this looks a bit like Rust but isn't Rust".