Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Enum of Arrays

tigerbeetle.com

Post reply on HN
Print view View original

11–20 of 52 posts

Re: Enum of Arrays

#11

Post by dist1ll »

norir wrote: post #6
thechao wrote: post #2

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 t…

> 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.

One example that I frequently deal with that can benefit from this is compiler data structures.

Re: Enum of Arrays

#12

Post by dist1ll »

saghm wrote: post #5
samatman wrote: post #3

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 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.

Scala also calls them enums fyi. Personally, I wish everyone would call them variant types.

Re: Enum of Arrays

#13

Post by shwestrick »

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.

Re: Enum of Arrays

#14

Post by fargle »

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:

    { red-red-red, red-red-green, red-green-red, red-green-green ... green-green-green }
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.

Re: Enum of Arrays

#15

Post by moth-fuzz »

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.

All the same is true for enums.

Re: Enum of Arrays

#16

Post by saghm »

dist1ll wrote: post #12
saghm wrote: post #5

Earlier quoted context omitted.

> 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.

Scala also calls them enums fyi. Personally, I wish everyone would call them variant types.

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".

Re: Enum of Arrays

#17

Post by aragilar »

moth-fuzz wrote: post #15

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 fiel…

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.

Re: Enum of Arrays

#19

Post by [deleted] »

moth-fuzz wrote: post #15

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 fiel…

[deleted]

Re: Enum of Arrays

#20

Post by benatkin »

samatman wrote: post #3

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 wit…

In wit for wasm they call them variants, which makes more sense to me. Enum is kind of an odd name for them. https://component-model.bytecodealliance.org/design/wit.html...
Post reply on HN