Data structure in .Net keeping heterogeneous structs contiguous in memory

Question

I'm looking for a data structure in .Net which keep heterogeneous structs contiguous in memory in order to be cpu-cache-friendly.

This type of data structure is explained in this blog : T-machine.org at the Iteration 4.

In .Net an array of value types (structs) keeps data contiguous in memory, but this is only working for a no-generic array. I tried to create a ValueType[], but structs are boxed. So the references are contiguous in memory but not the real data.

After many tries I don't think this is possible natively in .Net. The only possible solution I see, it's to manually managed the seralization and deserialization of structs in a byte array, but I don't think it will be performant.

Did you find a native solution? or a better solution that mine?

Edit 1: I'm trying to implement an entity-component-system as described in the T-Machine.org blog.

If the types of datastructures you need is fixed, you can put them in another struct... So `struct PositionVelocity { Position Pos; Velocity Vel }` — xanatos, May 03 '15 at 08:40
You could use two different arrays, that can also result in less padding and it's especially good if not all fields of the "big struct" are equally hot. Anyway can you give more detail about what you're doing? Then we can give a more focused solution. — harold, May 03 '15 at 08:50
@xanatos Unfortunately not, I don't know at the compile time all the struct types. Besides, I can have a Position followed by a Velocity, and then another Velocity. — Romain Rastel, May 03 '15 at 08:50

score 3 · Accepted Answer · edited Jun 20 '20 at 09:12

No. There is no way to do Iteration 4 in C#. You can't decide where in memory a .NET struct or class will be put. There is nothing similar to Placement New of C++.

But note that even Iteration 4 seems to have more problems than solutions:

At this point, our iterations are quite good, but we’re seeing some recurring problems:

Re-allocation of arrays when Components are added/removed (I’ve not covered this above – if you’re not familiar with the problem, google “C dynamic array”)

Fragmentation (affects every iteration after Iteration 1, which doesn’t get any worse simple because it’s already as bad as it could be)

Cross-referencing (which I skipped)

but

if you have struct of around the same size, the union trick could be enough...

public enum StructType
{
    Velocity = 0,
    Position = 1,
    Foo = 2,
    Bar = 3,
}

public struct Velocity
{
    public int Vx;
    public int Vy;
}

public struct Position
{
    public int X;
    public int Y;
    public int Z;
}

public struct Foo
{
    public double Weight;
    public double Height;
    public int Age;
}

public struct Bar
{
    public int ColorR;
    public int ColorG;
    public int ColorB;
    public int Transparency;
}

[StructLayout(LayoutKind.Explicit)]
public struct SuperStruct
{
    [FieldOffset(0)]
    public StructType StructType;

    [FieldOffset(4)]
    public Velocity Velocity;

    [FieldOffset(4)]
    public Position Position;

    [FieldOffset(4)]
    public Foo Foo;

    [FieldOffset(4)]
    public Bar Bar;
}

"officially" in C# there are no C unions. But thorugh the use of FixedLayout and FieldOffset you can create them. Note that they are totally incompatible with reference types, and clearly the size of the SuperStruct will be the size of the biggest possible element. In this case, 32 bytes, because Foo is 20 bytes, but there is some padding needed before and after it to align to the 8 bytes boundary.

Clearly your array would be of SuperStruct types. Note that by following the Iterion 4 example, the StructType isn't strictly necessary, because the types of the elements is written in other places.

Thank you, that's what I thought, but I could'nt be 100% sure. I think I will go with multiple arrays, one for each struct type. Doing this I will have cache misses (when accessing multiple component type in a system) but less than component as class. — Romain Rastel, May 03 '15 at 08:55
@Romain Wait... wait... If you only need to keep non-reference types, you could use the union trick. Give me five minutes... — xanatos, May 03 '15 at 08:57
@harold Clearly :-) This isn't the magic perfect bullet. It works if you have various `struct` of similar size. — xanatos, May 03 '15 at 09:08
@xanatos OK I understand the union trick, but I don't think I can use this. For example, I cannot have a SuperStruct with a Velocity and a Position, since they have the same FieldOffset. Nice trick though :-) — Romain Rastel, May 03 '15 at 09:20
@Romain ??? Following Iteration 3, you could create two structs `PositionVelocity` and `PositionPhysics` that are mutually exclusive, and place both of them at FieldOffset(4) of the SuperStruct... Or you could simply use atomic elements of the structure, so that if you need both `Position` and `Velocity`, you simply put them in two elements of the array — xanatos, May 03 '15 at 09:23
@xanatos Yes I could, but for me this iteration leads to more problems: *When a new Entity is created that intends to have Position, Velocity, and Physics … do we include it as “Pos, Vel”, “Pos, Phys” … or create a new template, and append it at end of our MegaArray?* — Romain Rastel, May 03 '15 at 09:29

Data structure in .Net keeping heterogeneous structs contiguous in memory

1 Answers1