2
\$\begingroup\$

I like the Unity's entity-component-system approach, I'm working on something similar. However I'm not sure where and how I should store the components.

An easy answer would be: "store the components in the corresponding system" - this is logical (who else is interested in the component if not the handler system?), and cache-friendly (continuous memory, so iterating through the collection would/could cause less cache miss).

However there are two major problems with this approach. Actually it's only one which generates the other. The generated problem is the simpler, I start with that:

A Behaviour (aka. custom user script) component can be added to the GameObject (aka. entity). The Behaviour must be able to get other components which are added to this object (similar to Unity's MonoBehaviour). However the object is not storing any component directly, so we have to query the component from the corresponding system. In a simple world, this query can be done only once after the required component is created, because its address won't change until its actually removed. This way, the Behaviour component can query other components in its constructor/init function and everyone is happy. But what if the other component's address can change? Actually this is the root cause of this problem and it's generated by the next one:

Storing components in an array can be a good thing because it's memory(bus) friendly. However it's not ideal in some cases, eg. when I have a spatial partitioner tree (QuadTree right now). I have two choices:

1)

I can keep the "global" continuous array representation and store pointers only in the QuadTree. However, this way when I query the components which belongs to a QuadTree node and iterate on the result, cache misses are introduced (jumping back and forth in the memory).

// pseudo-code

// "global" storage
pool<RigidBody> rigidBodies;
pool<Mesh> meshes;
// etc.

QuadTreeNode
{
    // only pointers to the "global" array elements
    vector<RigidBody*> rigidBodies;
    vector<Mesh*> meshes;
}

2)

I can use node-based component array which means the iteration is more cache-friendly. But when the component has to be moved to a different QuadTree node, it must be removed from the current node and must be copied to the new one. This means the component's memory address is changed which also generates my first problem (cannot query only once, because the address can change).

// pseudo-code

// not-partitioned components
pool<Behavior>

QuadTreeNode
{
    // these are not pointers, but the actual data
    pool<RigidBody> rigidBodies;
    pool<Mesh> meshes;
}

I probably pick the 1st solution, because the cache-miss is probably less noticable than the constant remove-copy and query operations (at least for "moving" components).

However, I'm interested in any better representation/storage of the components which is both cache-friendly and operation-friendly.

\$\endgroup\$
0
\$\begingroup\$

I'd suggest the first solution but use indices instead of pointers. Pointers will still be invalidated if you resize/realloc the array (or std::vector in C++) unless you used unrolled blocks with division/modulo (or right shift and bitwise AND) for random-access plus they take twice as much memory on 64-bit which will also more incur more cache misses if you sequentially access a massive array of 64-bit pointers as opposed to 32-bit indices, e.g.

However, you can make quad-tree traversal more cache-friendly if you can afford a radix sort here and there by radix sorting the indices it stores at the leaves periodically if the quad-tree has changed a lot.

\$\endgroup\$
  • 1
    \$\begingroup\$ You are right. Pointers are only allowed when the storage is stable. Since there is no other answer here and I agree with you, I accept this one. :) \$\endgroup\$ – csisy Dec 12 '17 at 13:35
  • 1
    \$\begingroup\$ Cheers. Also I think periodically radix sorting the indices can be more than good enough, whenever a lot of changes have occurred. One linear pass and you end up having sorted indices which avoid going back and forth in memory, evicting cache lines only to load the same memory region again. Trying to make ECS engines access components in a way that's perfectly contiguous is usually an impractical goal -- too little bang for too much buck, and that's even without spatial indexing involved. Accessing them in a fashion where you don't zig-zag back in memory is practical though. \$\endgroup\$ – user77245 Dec 12 '17 at 13:38
  • 1
    \$\begingroup\$ Good point. Anyway, premature optimization is evil. :) Probably this will be more than enough. \$\endgroup\$ – csisy Dec 13 '17 at 5:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.