Stream: ideas

Topic: Struct Of Arrays

Lucas Rosa (Nov 17 2021 at 15:02):

would it be worth having some kind of struct of arrays thing as a builtin? similar to zigs MultiArrayList

Lucas Rosa (Nov 17 2021 at 15:03):

after handmade Seattle I was really impressed with how these can improve performance and the control is in "userspace"

Richard Feldman (Nov 17 2021 at 15:11):

I hadn't really thought about it to be honest!

Richard Feldman (Nov 17 2021 at 15:14):

so I guess the idea would be that we have MultiList a as a builtin, and the way it works is that when you put a record type in there, it compiles to a record of Lists, where each List represents a field in the list?

Richard Feldman (Nov 17 2021 at 15:14):

and any non-records you put in there would work like they do in a normal List?

Folkert de Vries (Nov 17 2021 at 15:19):

intuitively. You could imagine that tag unions store the tag id in a separate array

Folkert de Vries (Nov 17 2021 at 15:20):

this idea sounds very attractive to me

Richard Feldman (Nov 17 2021 at 15:29):

and I guess nested product types would get flattened automatically :thinking:

Lucas Rosa (Nov 17 2021 at 15:33):

yea or like an Array of structs

Lucas Rosa (Nov 17 2021 at 15:34):

I forget which is which but MultiArrayList from zig is the exact implementation I’m thinking off

Richard Feldman (Nov 17 2021 at 15:34):

yeah that one's a struct of arrays

Lucas Rosa (Nov 17 2021 at 15:34):

where each field from a record goes into its own list or something

Richard Feldman (Nov 17 2021 at 15:34):

right!

Richard Feldman (Nov 17 2021 at 15:35):

how would iteration work? :thinking:

Lucas Rosa (Nov 17 2021 at 15:35):

So { a, b }
becomes List a and List b under the hood

Richard Feldman (Nov 17 2021 at 15:35):

like if I did a walk on a MultiList { x : I64, y : I64 }

Richard Feldman (Nov 17 2021 at 15:35):

what would that compile to?

Lucas Rosa (Nov 17 2021 at 15:36):

hm not sure, let me think a little and I’ll come back after this appointment I have

Folkert de Vries (Nov 17 2021 at 15:36):

you do the bounds check once, and then just get the value out of each array

Richard Feldman (Nov 17 2021 at 15:36):

ah that makes sense!

Folkert de Vries (Nov 17 2021 at 15:36):

you can re-assemble into the record type that you pretend to be storing. That's just moving values around on the stack

Richard Feldman (Nov 17 2021 at 15:36):

so then like map would be more efficient, but walk might be less efficient

Richard Feldman (Nov 17 2021 at 15:36):

than a List

Folkert de Vries (Nov 17 2021 at 15:36):

and then call the function

Richard Feldman (Nov 17 2021 at 15:38):

wow yeah I think that would Just Work in general :thinking:

Richard Feldman (Nov 17 2021 at 15:38):

and get the efficiency benefits

Richard Feldman (Nov 17 2021 at 15:39):

like even if map and such were all implemented in terms of walk

Richard Feldman (Nov 17 2021 at 15:39):

unless I'm missing something?

Richard Feldman (Nov 17 2021 at 15:43):

MultiArrayList in Zig, for context:

https://zig.news/kristoff/struct-of-arrays-soa-in-zig-easy-in-userland-40m0

https://github.com/ziglang/zig/blob/master/lib/std/multi_array_list.zig

Folkert de Vries (Nov 17 2021 at 15:43):

I thnk that just works yes

Jakub Konka (Nov 17 2021 at 15:46):

If I can drop a comment or two: it's efficient since you don't actually store structs in an array (having to care about padding to satisfy alignment reqs), but store each struct field in a separate array. In zig we then have a "view" into each slice which you can use to iterate on, etc.

Richard Feldman (Nov 17 2021 at 15:47):

I think we wouldn't even need the "view" in our case, right? :thinking:

Folkert de Vries (Nov 17 2021 at 15:48):

the view is hidden in the map/walk/etc functions

Jakub Konka (Nov 17 2021 at 15:48):

I think you always need a view into each array, but you can synthesise into a struct one level up

Jakub Konka (Nov 17 2021 at 15:48):

anyway, example usage: https://github.com/ziglang/zig/blob/3d528161c80c753a9b00cae84cae245526b29c10/src/arch/x86_64/Emit.zig#L60

Folkert de Vries (Nov 17 2021 at 15:48):

is a view more than an index?

Folkert de Vries (Nov 17 2021 at 15:49):

or equivalently, a pointer

Jakub Konka (Nov 17 2021 at 15:50):

Folkert de Vries said:

or equivalently, a pointer

Just an index/pointer

Folkert de Vries (Nov 17 2021 at 15:50):

right

Richard Feldman (Nov 17 2021 at 15:50):

a relevant distinction with Zig's MultiArrayList is that this wouldn't be in userspace in Roc - it would be a language builtin, part of the standard library

Jakub Konka (Nov 17 2021 at 15:50):

You don't actually need to build a struct on the way out always - sometimes it's better to just iterate on fields

Folkert de Vries (Nov 17 2021 at 15:51):

that's true but something we cannot easily do because this is not in userspace

Folkert de Vries (Nov 17 2021 at 15:51):

but I've been doing that a bunch in rust and it's great

Jakub Konka (Nov 17 2021 at 15:51):

Roc is higher level so returning a struct but storing each field in a separate array should be doable and fine, right?

Folkert de Vries (Nov 17 2021 at 15:52):

e.g. using a vector instead of a hashmap, store the keys separately in an array from the elements, and then if the keys are small simd can just tear through that array to find if a key is in there

Folkert de Vries (Nov 17 2021 at 15:52):

yes as a user you could always do that yourself

Folkert de Vries (Nov 17 2021 at 15:53):

but then other functionality is more error prone

Folkert de Vries (Nov 17 2021 at 15:53):

or slower

Jakub Konka (Nov 17 2021 at 15:53):

Folkert de Vries said:

e.g. using a vector instead of a hashmap, store the keys separately in an array from the elements, and then if the keys are small simd can just tear through that array to find if a key is in there

interesting, I never thought of relying on SIMD in a situation like this but this makes sense

Jakub Konka (Nov 17 2021 at 15:54):

Folkert de Vries said:

or slower

Slower? How so? Isn't it just extracting an index and then doing an O(1) * n where n is the number of fields in the struct?

Folkert de Vries (Nov 17 2021 at 15:54):

yes but we do bounds checking always

Jakub Konka (Nov 17 2021 at 15:54):

Folkert de Vries said:

yes but we do bounds checking always

Ah, gotcha

Folkert de Vries (Nov 17 2021 at 15:55):

so it's both slower, and you have to deal with "optionals" every time

Jakub Konka (Nov 17 2021 at 15:55):

Right

Folkert de Vries (Nov 17 2021 at 15:56):

so totally possible, but not ergonomic

Folkert de Vries (Nov 17 2021 at 15:56):

hence why we'd want to bake it into the language

Folkert de Vries (Nov 17 2021 at 15:56):

and then you loose the ability to iterate over just one of the arrays

Folkert de Vries (Nov 17 2021 at 15:57):

but in practice llvm/inlining might elide the lookups that are not used

Lucas Rosa (Nov 17 2021 at 16:45):

Sweet I love how well received the idea is

Lucas Rosa (Nov 17 2021 at 16:45):

I’m down to put it on my queue of roc things to do but I’d probably need help so if someone gets to it without me it’s totally fine

Lucas Rosa (Nov 17 2021 at 16:46):

This feature should do well with game devs

Lucas Rosa (Nov 17 2021 at 16:47):

or anyone looking to reduce padding

Brendan Hansknecht (Nov 17 2021 at 16:53):

Do we have any ideas for enabling users to walk a sub array. Like explicitly saying that they want to loop over the a part of { a, b }. I think this may be important from a compiler optimization perspective. I am not sure that llvm will be able to/will always correct fix a map that only uses a subset of the fields. So generating code to load data from all arrays and build a struct only to use one field may not optimize well.

Lucas Rosa (Nov 17 2021 at 17:09):

hm good point

Folkert de Vries (Nov 17 2021 at 17:51):

I am not sure either, but I think there is a good chance it will. The alternatives are worse: a single array will always load the data, the user making multiple lists is still possible, but super inconvenient and you always pay the cost of the bounds check

Richard Feldman (Nov 17 2021 at 18:36):

I am not sure that llvm will be able to/will always correct fix a map that only uses a subset of the fields.

if it can't, we could potentially do our own dead code elimination pass on that

Richard Feldman (Nov 17 2021 at 18:36):

we have all the info, after all!

Pit Capitain (Nov 18 2021 at 15:59):

Brendan Hansknecht said:

So generating code to load data from all arrays and build a struct only to use one field may not optimize well.

Is it really necessary to effectively build structs out of the multi-array-lists? Couldn't the compiler internally treat an index into a multi-array-list like a stand-alone record? Something like the distinction between short and long strings: both are strings on the surface, but have a different representation in memory?

Folkert de Vries (Nov 18 2021 at 16:01):

it's not required, but it's the easiest way to do it. If that turns out to be inefficient, then, as Richard said, we have all the info to do specific optimizations

Sebastian Fischer (Nov 22 2021 at 08:00):

What would be the downsides / how much would it cost in performance to implement the existing List type like this?

Brendan Hansknecht (Nov 22 2021 at 08:13):

You mean have a list of records in Roc always compile to a record of lists?

Sebastian Fischer (Nov 22 2021 at 08:14):

Yes

Brendan Hansknecht (Nov 22 2021 at 08:16):

i think the worst case would be random access where you care about all elements in a single record. You would be doing n random memory loads where n is the number of fields in the record. Instead of 1 random and the rest cached. That would probably be a large hit on performance. Also, adding a single element could lead to n calls to the allocator.

Brendan Hansknecht (Nov 22 2021 at 08:19):

Also, probably a large cost to sort a list given n locations to move memory from instead of 1 chunk.
Though probably faster lookup if your key is a single element and we can use simd.

Brendan Hansknecht (Nov 22 2021 at 08:20):

So definitely has some hefty potential costs to consider. Very useful when used right, but definitely has bad cases as well.

Lucas Rosa (Nov 22 2021 at 16:09):

yea it's worth giving the control over to the user as a possible optimization if needed

Locria Cyber (Jan 08 2022 at 11:49):

What need to be done to make SOA possible to define in userspace?

Zig uses compile-time execution and reflection to generate a SOA type for a struct, and generate the corresponding pointer type too.

Locria Cyber (Jan 08 2022 at 11:59):

What's the semantic of a struct in Roc? If there is no guarantee of ABI, the members of a struct don't even need to be contiguous in memory. Then SOA or AOS is an implementation detail, not part of the type of a value. It is similar to inline, that I think it should be a hint to the compiler.

Idealistic view of optimization: Humans are terrible are guessing performance of a program. I hope I don't need to tell the compiler how to optimize my code, that the compiler will search in the output-space and find the best assembly implementation for a program.

Richard Feldman (Jan 08 2022 at 12:39):

do you know of any academic research on compilers that can detect at compile time whether AoS versus SoA would have better performance at runtime?

That would be really valuable if someone figured out a way to do it reliably!

Folkert de Vries (Jan 08 2022 at 14:15):

futhark does the transformation, but I think it just always does it

Brendan Hansknecht (Jan 08 2022 at 22:28):

I think a well done SoA tends to be better in most cases, but well done tends to depend on design decisions that a human would make rather than a compiler.

AoS is really only conducive to cases where each struct in the array is accessed randomly and most or all of its fields are used on each access (Where you might also use a hashmap). If that is the case, you are doing something that already sucks on modern hardware, so it still won't be fast.

Brendan Hansknecht (Jan 08 2022 at 22:31):

All that being said, both should be completely doable in roc currently. Just would be done manually.

To make it even close to automatic in our current state i don't think is doable. No current way to map from a struct to the set of arrays.

Brendan Hansknecht (Jan 08 2022 at 22:32):

Also, roc does have a struct abi that defines order, size, and alignment of each field. Because platforms can depend on it, it is not up to the compiler to change it as it sees fit based on AoS or SoA. That being said, a specific data structure could theoretically automatically pick as long as it has an API that deals with the conversion to/illusion of regular structs

Richard Feldman (Jan 09 2022 at 02:44):

yeah the MultiList a builtin idea definitely seems the most promising to me!

Last updated: Jun 16 2026 at 16:19 UTC