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

21–30 of 52 posts

Re: Enum of Arrays

#21

Post by 10000truths »

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…

Access patterns matter, but just as important is to have less stuff to access. That's why arrays-of-structs are considered cache friendly - columnar data layouts open the door to optimizations that significantly reduce memory footprint. You no longer waste memory with struct padding. Boolean fields can become bitsets. Enums can be bit-packed. Often-null optional fields can become sparse maps. 8-byte pointers can become narrower-sized indices into object pools.

Re: Enum of Arrays

#22

Post by tugu77 »

This thing should be a poster example of premature optimization. Sure you can squeeze a few milliseconds out in a performance critical task. Most things won't measurably benefit though, while making all handling super awkward.

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.

Re: Enum of Arrays

#23

Post by rlupi »

shwestrick wrote: post #13

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…

Good insight.

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.

Re: Enum of Arrays

#24

Post by mbrock »

rlupi wrote: post #23
shwestrick wrote: post #13

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…

Good insight. 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.ab…

Zig can represent AoS to SoA very nicely, it's a favored technique for the Zig compiler itself and well supported by the standard library where it's known as a MultiArrayList.

Re: Enum of Arrays

#25

Post by midnightchair »

AndyKelley wrote: post #8
norir wrote: post #6

Earlier quoted context omitted.

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

I'll tell you my experience with Zig. I don't have any. I saw maybe Primagen talking about it and I see your post here. I watched 10 minutes of your vimeo video. I see it has 30k+ stars on github. So now I have to try to understand it in a nutshell.

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.

Re: Enum of Arrays

#26

Post by pavlov »

10000truths wrote: post #21
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…

Access patterns matter, but just as important is to have less stuff to access. That's why arrays-of-structs are considered cache friendly - columnar data layouts open the door to optimizations that significantly reduce memory footprint. You no longer waste memory with struct padding. Boolean fields can become bitsets. Enums can be bit-packed. Often-null optional fields can become sparse maps. 8-byte pointers can beco…

> “That's why arrays-of-structs are considered cache friendly”

Sounds like you mean structs-of-arrays?

Re: Enum of Arrays

#27

Post by brabel »

midnightchair wrote: post #25
AndyKelley wrote: post #8

Earlier quoted context omitted.

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

I'll tell you my experience with Zig. I don't have any. I saw maybe Primagen talking about it and I see your post here. I watched 10 minutes of your vimeo video. I see it has 30k+ stars on github. So now I have to try to understand it in a nutshell. 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 i…

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

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

Re: Enum of Arrays

#28

Post by 10000truths »

pavlov wrote: post #26
10000truths wrote: post #21

Earlier quoted context omitted.

Access patterns matter, but just as important is to have less stuff to access. That's why arrays-of-structs are considered cache friendly - columnar data layouts open the door to optimizations that significantly reduce memory footprint. You no longer waste memory with struct padding. Boolean fields can become bitsets. Enums can be bit-packed. Often-null optional fields can become sparse maps. 8-byte pointers can beco…

> “That's why arrays-of-structs are considered cache friendly” Sounds like you mean structs-of-arrays?

Oops, brainfart on my part. Unfortunately, the edit window has passed.

Re: Enum of Arrays

#29

Post by keybored »

midnightchair wrote: post #25
AndyKelley wrote: post #8

Earlier quoted context omitted.

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

I'll tell you my experience with Zig. I don't have any. I saw maybe Primagen talking about it and I see your post here. I watched 10 minutes of your vimeo video. I see it has 30k+ stars on github. So now I have to try to understand it in a nutshell. 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 i…

What a random and untimely user report.

Re: Enum of Arrays

#30

Post by ratmeadow »

The representation of enum of arrays reminds me of a technique for "de-polymorphicking" or devirtualisation in an object oriented paradigm. Instead of having an array of polymorphic base class instances, you have a separate array for each concrete derived type. This takes advantage of the observation that often the set of derived types is quite limited. As a result, indirection and virtual calls disappear, improving optimisation, cache performance, and branching performance. I think it's quite a smart technique, noticing that the degree of polymorphism provided is unnecessary for the actual use case.
Post reply on HN