How should I arrange storage for components referenced in a quad tree?

Question

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.

Answer 1

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.