Enum of Arrays
tigerbeetle.com
Enum of Arrays
1–10 of 52 posts
Re: Enum of Arrays
#2I 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.
Re: Enum of Arrays
#3This 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.
[0]: https://ziglang.org/documentation/master/std/#std.enums.Enum... [1]: https://ziglang.org/documentation/master/std/#std.multi_arra...
Re: Enum of Arrays
#4This 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 wit…
> This is a somewhat, hmm, bilingual post.
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".
Re: Enum of Arrays
#5This 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 wit…
> 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.
Re: Enum of Arrays
#6I 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.
Re: Enum of Arrays
#7Now do a single class pointer for an array of values...
Re: Enum of Arrays
#8I 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 t…
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:
* 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...
Re: Enum of Arrays
#9see also: Richard Fabian's data-oriented design book -- the chapter on existential processing discusses enums
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.
Re: Enum of Arrays
#10I 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 t…
Isn't performance and memory usage generally enhanced by this?
So why not simply default to this instead of defaulting to Interfaces/traits doing dynamic polymorphism?
Makes everyone a bit more happy.