Question Looking for a better data layout

I have a graph which contains a list of shapes, and shapes contain a list segments.
The model is not using ECS, but will use Jobs, Burst. The data will be modified at runtime.
Segments are wasting a lot of memory. Is there a cleaner way to model the segments data?

struct Graph {

     NativeList<Shape> shapes;

}

struct Shape {

    uint ID;

    Bounds bounds;

    Transform transform;

    NativeList<Segment> segments;

}

struct Segment {

    byte Type          { 0 = Linear, 1 = Quadratic, 2 = Cubic }

    float3 p0          always used

    float3 p1          always used

    float3 p2          only used if quadratic or cubic

    float3 p3          only used if cubic

}

Thinking in terms of the actual data needed:

[

    byte Type = linear, float3 p0, float3 p1,

    byte Type = quadratic, float3 p0, float3 p1, float3 p2

    byte Type = cubic, float3 p0, float3 p1, float3 p2, float3 p3

]

I am aware that connected segments could trim data by using the previous segment's last point as the current segment's starting point, but I'm trying to keep the post's code as simple as possible.

Is there a collection type that could support this or would I have to create my own?

 

Well for starters I don't know how your code would even work since you have a NativeList<Shape> and Shape contains a NativeList<Segment>. That's container nesting.

It is difficult to suggest anything without seeing how the code interacts with this structure. Can a Shape have more than one type of segment?

 

I was under the impression that a struct containing a native container simply stored a pointer to the container data kept elsewhere. If this is not the case then I'm even more unsure how to structure this data.

A shape can have multiple segments, and each segment can be any one type of: linear, quadratic, cubic. A linear segment requires 2 points, a quadratic segment requires three points, and a cubic segment requires four points. If you're familiar with SVG the data is somewhat similar to a path element.

I guess what I might be after with regards to segment data is a NativeList<byte>, which I would have to walk through and cast. This seems weird though.

Code (CSharp):

1. NativeList<byte> data;
2. var byteIndex = 0;
3. var segmentIndex = 0;
4.  
5. while (byteIndex < data.Length)
6. {
7.     var type = (SegmentType) data[byteIndex];
8.     byteIndex += 1;
9.     segmentIndex += 1;
10.  
11.     switch(type){
12.         case cubic:
13.             // cast the next 48 bytes into four float3
14.             // do logic
15.             byteIndex += 48;
16.         case quadratic:
17.             // cast the next 36 bytes into three float3
18.             // do logic
19.             byteIndex += 36;
20.         case linear:
21.             // cast the next 24 bytes into two float3
22.             // do logic
23.             byteIndex += 24;
24.     }
25. }

 

In normal cases
Structs contains data.
Classes contain references.

Jobs don't like nested struts containers.
You can play with unsafe containers, pointers etc, but if you are not familiar with these, it is easy to create race conditions.

 

So you say segments are using up a lot of memory. How much? How many are there? What is your budget? Is cutting that in half good enough? If memory is a big concern, than you want to completely encapsulate your compression. Otherwise the union is probably your best option. A second alternative is an indirection array into arrays of your different types.

I doubt this is what you actually meant to say, because it is not true. Nested structs work fine in jobs. What doesn't work is a container containing a struct which contains a container. That breaks both in and out of jobs.

 

So a shape struct would need a pointer to a native container where the segment data is actually stored. In parallel work the jobs working on the same shape would all have the same pointer value to the same data, so the native container would probably need to be something with parallel options -- which I don't know much about yet. I see now how this gets messy quickly.

I assume CRUD operations would have to happen through utility methods so I don't leave a shape's collection dangling by accident.

Not sure how any of this would work yet. I've got some homework to do.

 

You are right, should be containers, thx for a correction.

 

You're almost there, instead of `NativeList<byte>` why not use `NativeList<float3>`

Code (CSharp):

1.  
2. struct Graph
3. {
4.     public NativeList<float3> Points;  // continues points from first segment to last segment
5.     public NativeList<int> SegmentPointIndices; // index of start point of segment (n)
6.     ...
7. }
8.  

or maybe `Blob` if segments and points are not resizable at runtime.

Code (CSharp):

1.  
2. struct Graph
3. {
4.     public BlobArray<float3> Points;
5.     public BlobArray<int> SegmentPointIndices;
6.     ...
7. }
8.  

Additional: `byte` in `struct` won't work as you expect unless with `Explicit` layout or `Sequence, Pack = 1` layout

 

Is there a specific reason not to use ECS?
If using ECS then I would make Shape an IElementBufferData with segments being a BlobAssetReference for a structure containing a BlobArray of Segments.
In the end your Graph would be the DynamicBuffer of Shapes.
This seems pretty straight forward with ECS or I'm missing something.

 

Something small yet possibly impactful:

Your

Segment

contains a

byte

and 12

float

s. The

byte

could just aswell be an

int

- padding insterts 3 empty bytes between it and the first float(https://stackoverflow.com/questions/4306186/structure-padding-and-packing).
Since memory might be a concern (as with my projects...), that might interest you.
Also: Inserting that byte into that struct will most likely disable auto-vectorization completely.

float3

s are generally vectorized with some performance issues (in fact they only get vectorized at all due to special treatment by Burst). But since you have exactly 12 in that struct, which is either three 128 bit SIMD registers or one and a half 256 bit registers, the compiler might perform some magic there.

In general, your approach is an "Array of Structures" approach - also known as "Object-Oriented Programming" You might want to really delve into the fundamental idea behind ECS or "Structure of Arrays" - what it does to your CPU cache and auto-vectorization.