7
\$\begingroup\$

I'm looking for ways to improve my ECS and I've seen many people suggest storing components in arrays. This seems great, considering fast access for a component using entity id and more importantly, fast iteration over elements of array (because systems do this all the time) and fewer cache misses than if I store components in Entity or use:

std::map<int,std::shared_ptr<Component>> components // where int is a component id 

But I have some questions about this approach.

1) Do I have to create array for each component? Something like:

PositionComponent positionComponents[MAX_OBJECTS];
HealthComponent healthComponents[MAX_OBJECTS];
...

Or is there a better way to store different components contiguously in memory?

2) How can I get components using entity id if I do this?

I'd like to implement some function like this:

template <class T>
T* getComponent(int entityId) const {
    ... // ??
}

so I can then use it like this:

PositionComponent* pc = getComponent<PositionComponent>(entityId);
\$\endgroup\$
11
\$\begingroup\$

This seems great, considering fast access for a component using entity id and more importantly, fast iteration over elements of array (because systems do this all the time) and fewer cache misses than if I store components in Entity or use:

Have you actually measured cache misses? Are they in any way being a problem for you? Would eliminating them for your component accesses be likely to have a measurable impact? Is it valuable for you to spend your optimization time worrying about them instead of focusing on parallelism or better GPU usage? Do you at least have measurements of your code before any such change so you can compare them to measurements from after the change?

Simply putting things in an array doesn't guarantee fewer cache misses, either. It's the first step of several to improving cache usage for components. It may be a false step for improving your overall performance, too.

1) Do I have to create array for each component? Something like:

PositionComponent positionComponents[MAX_OBJECTS];
HealthComponent healthComponents[MAX_OBJECTS];

A std::vector or the like would work just as well. Note that as the vector could reallocate its backing storage and invalidate existing existing iterators/pointers you'll have to use component indices rather than pointers.

You can also easily write a chunked storage means (like a std::deque, but not optimized for queues) that allows the structure to grow, keep fast iteration, and have stable pointers.

2) How can I get components using entity id if I do this?

template <class T>
T* getComponent(int entityId) const {
    ... // ??
}

You can store an additional boost::flat_map or std::unordered_map or a custom high-performance hash table that maps entity IDs to component indices for that component type.

You'll probably just want to map to an index or a temporary pointer (one you promise never to retain) as that allows the component holder to defragment its component collection. That both can potentially allow the holder to release blocks of memory and more importantly (for data-oriented needs) is essential to actually making iteration over components faster. It's likely going to be much faster to use your existing approach than it is to iterate over a huge and sparsely-populated array. Remember that with a sparse array (even if 99% occupied) you have to add an additional if (isInUse) check inside your loop over the components which is an additional read+branch instruction that can have a noticeably negative impact on your overall iteration speed.

See BitSquid's four articles on the topic. Those guys tend to focus on C-like code and eschew modern C++ approaches with identical performance but easier usage, but the underlying approaches they use are applicable in C, C++, C#, Rust, or similar languages.

\$\endgroup\$
  • 1
    \$\begingroup\$ To be honest, I have more problems with the design and lots of virtual casts I have to do at the moment(I store Components in Entity as std::vector<Component*>) than cache misses. I just want to make "pure" ECS where entity is just an id. And how would that unordered map work? I don't quite get it. Can you provide a more specific example, please? And thanks for that link, will definitely check it out. \$\endgroup\$ – Elias Daler Dec 18 '14 at 4:31
  • \$\begingroup\$ @EliasDaler: the articles linked explain the use of a hash table like unordered_map, only they use their own. The concepts are the same. \$\endgroup\$ – Sean Middleditch Dec 18 '14 at 4:35
  • \$\begingroup\$ Unfotrunately, their articles doesn't answer my question. Their component design is very different from mine. But still, thanks, I'll mark this answer as your explanation makes sense to me now. \$\endgroup\$ – Elias Daler Dec 23 '14 at 7:24
  • 1
    \$\begingroup\$ @EliasDaler: perhaps I don't understand the question, then. The article goes over how you use a hash table to map entity IDs to component indices. That bit should work the same even if your components are different. If I'm understanding you properly. \$\endgroup\$ – Sean Middleditch Dec 23 '14 at 18:03
  • 1
    \$\begingroup\$ @Nikos: that's the low-tech way, sure. And totally sufficient for many users. There's more sophisticated implementations of that general idea which are possible (based on "slot maps" or what the bitsquid articles called "packed arrays" or what EnTT calls "sparse sets") but don't over-engineer if you don't have to. :) You might want to check out some other open source C++ hash tables (like those in Abseil) besides unordered_map which has... issues (it's designed for a set of invariants that don't apply here but which impose serious perf overhead for this case). \$\endgroup\$ – Sean Middleditch Oct 8 at 19:23
3
\$\begingroup\$

1) Do I have to create array for each component?

Yes, but a vector would be more convenient, and equally performant.

2) How can I get components using entity id if I do this?

You should store the Entity ID on the components themselves. Keep your vector sorted by that ID, and then use vector::lower_bound to retrieve the components. In my own testing, this lookup is actually faster than a map up to a certain point.

\$\endgroup\$

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.