Enum of Arrays
tigerbeetle.com
tigerbeetle.com
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.
Ah... category theory :-)
Array-of-Stuct (AoS) treats order in arrays as meaningful, arrays as lists, so AoS => Struct-of-Array (SoA) doesn't loose information. It is a sound transformation because it is a homomorphism.
Some languages (homoiconic, or with macros or template support) can express this code transformation: e.g. Julia, https://github.com/JuliaArrays/StructArrays.jl, or Rust, https://www.abubalay.com/blog/2019/02/16/struct-of-arrays
In a sense, you can see this transformation through the concept of monads (although Haskell monads or F# computational expressions cannot directly express it, as far as I know). Then the corresponding category diagrams leads to sets or multi-sets (run-length encoding requires or implies some concept of identity, so unordered lists with repetitions = bags and multi-sets are equivalent in this specific context), as the right concept for Enums of Arrays.
If the order doesn't matter, you could use a separate field for each variant of the enum.
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...
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".
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.
All the same is true for enums.
Sounds like you mean structs-of-arrays?
Performance issues start to crop up with naive pre-fetching, and thus 100% guaranteed cache misses if the arrays are larger than L2.
This is why LLM AI generated slop degrades blogs into slop delivery services. =3
Not sure what LLMs and AI have to do with any of this.
This is wrong! Cache optimization isn't the only factor here. Even given an algorithm that seemingly handles each object one-by-one and uses all fields, SIMD turns individual operations into a hidden bulk access, and giving each field its own array will speed things up. This is counter-intuitive at first but becomes obvious if you write SIMD by hand (the article mentions this but doesn't make it super clear IMO)
Yes. That's the point.
> Putting fields of a struct into their own arrays is only actually an optimization if you're only accessing that field in-bulk.
Yes, that's the scenario.
> And if so, why is it even in a struct in the first place?
Because that's how everyone is taught to model domains.
> If you use all fields of a struct in your algorithm, then an array of structs is the optimal way.
No. Your personal belief goes against both theoretical and empirical evidence. Others already talked about cache, padding, vectorized instructions, etc. I recommend you do a quick googling on the topic.
{ red-red-red, red-red-green, red-green-red, red-green-green ... green-green-green }
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...
First like any language, I go to indeed.com and put in "Zig" to see if there are any jobs listed which use it. I don't see any.
Then I click to https://ziglang.org/ and it describes Zig as "robust, optimal and reusable". Well that doesn't really say much of anything.
I read the example listed, which appears to be a test case, and I wonder how the 'try' mechanism works without a 'catch'
Then I go to https://ziglang.org/documentation/master/ and see that it says: Robust Behavior is correct even for edge cases such as out of memory.
I wonder how that works, but there are no links to support this claim.
I read a little more then move on.
This isn't to say anything one way or another about Zig, its just my 30 minutes of reading about Zig.
What does that have to do with anything? Zig is still in beta and they explicitly do not recommend that you use it in production yet unless you're ok with frequent breaking changes. Of course there will be very few jobs (though it's being used by a few notable projects already, including Tigerbeetle - authors of the post we're discussing - and Bun, the JS runtime).
Makes me wonder why you felt the need to create a burner account.
This isn't to say anything one way or another about you, its just my 2 second of reading about you.
So why not simply default to this instead of defaulting to Interfaces/traits doing dynamic polymorphism?
Makes everyone a bit more happy.
One example that I frequently deal with that can benefit from this is compiler data structures.
Which breaks down if any of your unions hold different alternatives. The "array of structs to struct of arrays" transformation, OTOH, cannot break.
It's also common to transform an "array of unions" (or "array of [pointers to] polymorphic types") into a "struct of shorter [homogeneous] arrays."
inb4: "The concepts are language independent."
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.
now this can then be wrapped in another layer (SoSoA?) when partitioning a set of heterogeneous enum values but the post makes no mention of that
If your abstract domain description is fundamentally a collection of things that have a few parts each, then have your data type represent that, instead of turning it inside out for cache effects. If those become relevant at some point, try to abstract that away and do the optimized internal representation under the hood. But don't preemptively design your data structures in a cumbersome way just in case. That's bad advice.
You are assuming the poster is doing something like your typical IO-bound backend, and not, say, a High Performance Computing simulation on a compute cluster.
I have done this kind of optimization to go from 24 hour compute time to 6 hour compute time instead for instance -- per simulation run.
How can you say "a few milliseconds" when you know absolutely nothing about the context?
I do not consider your advice any better at all; you assume all computer code is in the same context -- it really is not. Not all code is written as backend to websites.
You could have said "keep in mind that if you service is IO-bound, these kinds of optimizations are likely a waste" or similar to make the context clear.
This is a great question for the article's author, I think! They give very little information as to when this class of optimization makes sense, and because it's much more complex to implement than the AoS -> SoA transformation in the general case when the total ordering of enums is important, either a case-study or some general heuristics as to when this transformation is worth the effort would make the article more useful and interesting.
I'm sure there are workloads where this kind of optimization makes a lot of sense. But they are comparatively rare. And they are not for free, in terms of code complexity and robustness. So, for the broad masses reading HN, its a premature optimization.
> How can you say "a few milliseconds" when you know absolutely nothing about the context?
Most code that gets written is not performance critical. Programmers would generally be better advised to think about robustness, correctness and maintainability of their code than about cache effects. The world would be a better place and we'd see fewer app crashes and fewer security holes.