[Proposal] "Structure of Arrays" support

[lsoft]

This is pre-pre-pre-alpha proposal for Structure of Arrays support in C#. SoA is preferred over AoS for performance reasons, and it would be huge advantage for C# language to support this with low- or no-cost for programmer.

Any design of this idea is suitable if it does not lead to additional difficulties for the programmer. I want to suggest two drafts, both has a lot of troubles to be implemented, and I hope lang designers and runtime engineers will suggest more viable designs.

First draft.

Mark the type with some special attribute

[SoA]
public struct MyObject
{
    public int A;
    public object B;
}

and then every T[] in the codebase will use SoA instead of AoS:

var array = new MyObject[10]; //soa!
var list = new List<MyObject>(); //soa, because list is powered of array; this will make programmers happy because lack of concers for them
//etc...

//SIMD powered because of SoA data locality:
var sum1 = array.Sum(i => i.A);
var sum2 = list.Sum(i => i.A);

Second draft.

[InlineArray(10_000_000)] //1MB restriction dropped
struct IntFloatInlineArray //this will use SoA
{
    private int _value1;
    private float _value2;
    //etc
}

The first draft is an ideal one, because it is support arrays which size is defined in runtime. The second draft is a "fallback" design if the ideal one is impossible to implement.

I understand that this idea is very complex for lang and runtime (ref tracking for GC etc), and I does not involved in runtime development and lang design, so I only hope someone more knowledgeable will be able to make a more detailed proposal.

Thanks!

[CyrusNajmabadi]

var list = new List(); //soa

How would this work?

Also, this seems highly problematic. NOw that there are actually multiple arrays, anyone expecting reasonably behavior as if there was one, will now have that broken. For example, an atomatic compare/swap on an array will not hit all the SOAs.

[lsoft]

how do you get your original object back?

I see the problem now, thanks. What if we restrict this proposal only to structs? will this help to mitigate this problem?

[AttributeUsage(AttributeTargets.Struct)]
public class SoAAttribute : Attribute
{
}

[SoA]
public struct MyObject
{
    public int A;
    public object B;
}

We will construct new instance of struct instance from its fields... not sure, if it feasible.

[CyrusNajmabadi]

Yes. A struct would at least be feasible. This would need some sort of runtime change those to support.

It's also unclear how you would get any benefit. You'd need some way to actually access the underlying arrays to do anything meaningful on them.

[HaloFour]

Sounds a little bit like an extension of fixed/inline arrays? Feels like something the compiler could emulate somewhat easily, but also would really not work well anywhere else in .NET without some kind of runtime support. Also feels like it would be really awkward with normal APIs which look like they'd be referencing the struct type first but you want to really avoid trying to reconstitute the whole stuct.

[timcassell]

Right, this seems like it would need a new runtime array type that lays out the struct elements contiguously by field, and exposes each as a Memory<T>. This way you could still have regular arrays and SOA arrays separately, and not need an attribute on the struct itself. Though I'm not sure how you would access the Memory<T> for each field, some type of runtime magic that maps the field name to a property on the SoArray<T>? And what about private fields? And generics? It seems rather complicated and infeasible.

[lsoft]

You'd need some way to actually access the underlying arrays to do anything meaningful on them.

Unfortunately, I know a little about runtime impl, so I can suggest nothing here. Also, I can't suggest a way how to compile array.Sum(i => i.A) in SIMD code... hope for any more knowledgeable person can continue...

[bencyoung-Fignum]

Could just be a code generator that finds [SoA] attributed structs and produces helper collections that contain decomposed objects?

[AndersKehlet]

I was just about to say

One possible representation: dotnet lab

Just off the top of my head based on my experience with sg's.

[lsoft]

source generator for SoA exists already, but I think It's much better if one can obtain perf benefits to apply a SoA attribute (or to perform other easy change) to type involved into heavy calculation. Also, I guess supporting run-time sized arrays (and collection based on arrays) will useful too.

[tannergooding]

SoA is preferred over AoS for performance reasons

SoA can be preferred in specific contexts; however, there are equally many constructs where AoS is better. It depends on the payload, how its being operated on, etc.

Further, while SoA can be beneficial, it is typically much more complex than simply turning each field into an array. You often are explicitly accounting for memory layout, sparseness, cache sizes, whether it will be optimized via SIMD or not, what data is needed together or locality in general, etc.

[agocke]

Yeah, I agree -- this is a cool idea but we should carefully design it with a runtime design so that it's actually useful in practice. At minimum I assume we would require LayoutKind.Auto to prevent concerns about treating the struct as a regular struct.

[hez2010]

SoA will require the type carrying the size used for instantiation so that the memory layout can be determined at compile time, which is fully covered by #7508

[tannergooding]

Nothing about SoA requires a constant size or compile time determination of the size. Most uses would not be compile time determined either, they are frequently runtime determined and variable.

[Tyfyter]

Perhaps

public struct[] MyObject
{
    public int A;
    public object B;
}

would be a better syntax for declaring one