1

I am currently working on adding more customization to an entity component system library, although the problem is a little more general than that. In essence, I currently have hard coded containers for almost everything I do.

I use a flat map* for storing components (for those unfamiliar with ECS, just consider it as storing some generic data), a flat map of flat sets(!) for storing groupings** (which are used to speed up look up times that the user can create), and finally I return a vector of entities (thin reference semantic wrappers) when the user requests them.

As you can see, there is a number of places that customization would be desirable, especially in the storage of components. Notice that none of the library is even allocator aware, which would definitely deter some serious game developers.

What would be the correct way to add custom container (and/or allocator) support?

Currently, my interface looks roughly like this, simplified slightly to fit the question better:

auto manager = entity_manager<Components...>{};
auto grouping = manager.create_grouping<Some components...>();
std::vector entities = manager.get_entities<Some components...>();

The components are already part of the type system, and so adding another layer of indirection on top of that would not be so bad. That is, instead of the user supplying Components..., the would instead supply some trait class that would encompass all the information required to storing the component. This feels like a natural answer.

However, we still have the issue of groupings. Since they are created at run time and stored internally, we can't store arbitrary types. Having a polymorphic solution would be a nightmare as well, since a common use would be a std::{unordered}_map, so it seems natural to either move them into the type system (just as components are) or allow the create_grouping function to accept some std::memory_resource and use a polymorphic allocator. I am not sure which of the two is better, and if the user would ever care about such fine grained control. There's also no way to specify what the containers that holds all the groupings (the flat map) is.

Returning a vector can be changed to take in a Container template argument that would use that container as a return type, but again it clutters the interface a bit.

One final thing to consider is that the user has no real way to initialize these data structures. A solution would be to inherit from a user defined type and deal with everything in that way.

Basically my question boils down to what is the best pattern for allowing the usage of custom containers or allocators in public APIs, and if there are any good examples out in the wild that I can refer to. I understand there's probably no silver bullet, I am just hoping to get some different viewpoints.

* The flat containers have the same interfaces as their std counterparts, but are internally sorted vectors.

** A user may want to query entities by the components they contain, a grouping is a list of all the entities that contain the components of that grouping. The reason why you need a map of them (the flat sets) is so you can add/remove the groupings later.

3

Generally speaking, there is no good way to allow customizing the actual container type being used. That is, picking between unordered_map and flat_map. The reason being that the algorithms that code uses will be based on which container you use.

Even ignoring the differences in the interface, how you use an unordered_map or a flat_map are very different. If you design your code around a flat_map, you're designing for a situation where iteration is common, fetching by key is less common, and insertion is relatively rare. If you design your code around an unordered_map, then you're designing for a situation where fetching by key from large data sets is common, insertion is less common, and iteration is fairly rare.

But from outside of your engine, the user has little control over these things. While they do control how much data is involved, they have little control over broad access patterns and the algorithms being used by your engine.

It's best to let the code that is in control of how the object is used also be responsible for picking the container.

As for customizing the allocator, if you're wed to doing things the C++ standard library way, just use std::memory_resource and PMRs. In performance code, you should be trying to avoid memory allocations of any kind. And if you have to allocate memory, unless you're using a basic arena allocator, the virtual overhead will likely be overshadowed by the cost of the allocation itself.

  • 1
    While I agree with the general sentiment about engines, with my ECS framework the user has a lot of control about data access and data insertion/modification, making it useful to store rarely iterated but often accessed data inside something like an unordered_map. You mention that if I'm wed to the std, but what if I am not? What would be an alternative? – user975989 Nov 4 '17 at 17:30
1

In my humble opinion, trying to allow an ECS to let clients use their own containers and allocators is overkill. An ECS doesn't have that many responsibilities to be experimenting with an endless variety of data structures and allocators. It boils down to simply associating components to an entity aggregate and querying available components and entities in the system. There should be data structures and allocation strategies available which cover the needs of a wide range of people very efficiently without the temptation to try other data structures or allocators. Personally I'd rather have an ECS library which uses minimal memory and is super fast for all my needs over one where I can explore endless combinations of data structures and allocation strategies. The latter doesn't necessarily lead to the former.

That said, I'll get to how to do this later but first I want to offer a different perspective to try to persuade you why it's not necessarily so fruitful to do this.

For me, I have an ECS where I can actually create a particle emitter which emits 2 million particles where every single little particle is implemented as a separate entity with a particle component attached while animating all 2 millions particle entities/components and visualizing them at over 30 FPS. Every single frame has the particle system querying the ECS for all entities which have a particle component attached. Now this is normally a very dumb thing to do -- to represent every single particle as a separate entity with a separate component, but it was a stress test to demonstrate the efficiency of the system. The memory overhead of an entity is 8 bytes while the memory overhead of a component is 16 bytes (24 bytes of unnecessary overhead per particle when representing each individual one as an entity with a component attached, but not bad).

In my case the data structures used are very simple and coded in C for ABI compatibility with a C API (though with C++ wrappers on top):

struct Entity
{
    /// Stores an index to the first component contained in the entity.
    int first_comp;

    /// Stores an index to the first component's list.
    unsigned short first_list;
};

struct Component
{
    /// Stores an index to the entity which contains this component.
    int entity;

    /// Stores an index to the next component contained in the entity.
    int next;

    /// Stores an index to the component's list.
    unsigned short list;

    /// Stores an index to the next component's list.
    unsigned short next_list;

    /// Stores data for the component (variable-length struct).
    char mem[1];
};

enter image description here

Then there's a big random-access sequence which is mostly contiguous (big blocks storing 64 elements each which get freed when a block becomes empty) storing all the components and entities above which are accessed by index. Accessing a component requires two indices: a 16-bit index to the component list (basically a component type index) and then a 32-bit index into that list. The components contained in an entity are stitched together through indices which basically form a singly-linked list (but without requiring any memory allocation for each individual list node since the list pointers are just indices into a giant contiguous structure).

I see no reason to use any other data structure or memory allocation pattern for the ECS. The memory overhead of it is already quite minimal at 8 bytes per entity and 16 bytes per component and the processing is already very cache-friendly and largely contiguous. Component and entity insertion and removal occurs in constant time with no room for improvements in terms of algorithmic complexity.

The system can fetch all the components of a particular type, like ParticleComponent, by just iterating through the list (mostly contiguous) of ParticleComponents. It's about as cheap as it conceptually gets with support for parallel processing like so:

// Invoke 'animate_particle' in parallel for up to 256 particles to process
// per thread.
ecs.pfor_each<ParticleComponent>(animate_particle, 256);

If we want to fetch all the entities that implement two or more components, like both ParticleComponent and MotionComponent, we simply iterate through the list of ParticleComponents and MotionComponents and gather up the entity indices associated with each. Then we sort the indices in parallel and linearly look for entity indices which occur in the two resulting lists. If we have:

{1,2,3,4,5,6} // entity indices gathered from list of `ParticleComponents`
{1,3,5,7,9}   // entity indices gathered from list of `MotionComponents`

... then entity indices 1, 3, and 5 appear in both lists so that's the set intersection for entities which implement both ParticleComponent and MotionComponent. That's a fairly cheap query only requiring a linear traversal through two integer arrays, a couple of parallel sorts, and one more linear pass. The client can process the resulting entities like so:

// Do something to entities which contain both a motion and particle
// component in parallel, processing up to 256 entities at once per
// thread.
ecs.pfor_each<ParticleComponent, MotionComponent>(do_something, 256);

It's not something to do every single frame for millions of particles (though it's still reasonably fast in spite of doing this), but we can avoid that by simply allowing clients to memoize the entities that contain those two components and be notified when a ParticleComponent or MotionComponent has been removed from or added to the system, only updating the memoized entity list (a vector of ints, e.g.) then.

If you have a formal grouping concept for this, then the system can be responsible for memoizing the filtered list of entities that contain the group of components and only updating it as necessary. That doesn't require a more sophisticated data structure necessarily; a couple of linear passes and sorts (which can be done in linear time with, say, a radix sort because we're just sorting integers) should be good enough if you are only doing this in a lazy fashion when the client requests a list of entities that are filtered for a given component group and only when components matching the types in the group have been added or removed.

Even if you want something cheaper than a couple of linear passes and sorts of indices to fetch an updated list of entities which match the group filter, there should be a good enough data structure to fulfill the widest range of needs without the temptation to allow clients to specify what data structure to use for these purposes.

Policy-Based Design

With that aside, if you still feel like there's a strong compelling reason in your case to allow clients to specify data structures and allocators, then policy-based design might be the right fit for you. There you have classes which accept one or more template parameters indicating what policies to use (which could basically boil down to what data structures and allocators to use). Ex:

template <class SequencePolicy, 
          class AssociativePolicy, 
          class AllocationPolicy,
          ...>
class EntityManager
{
    ...
};

Modern C++ Design by Alexandrescu covers policy-based designs in detail.

However, I would move away from the standard library interfaces in that case because standard concepts like Sequence and Associative Container are likely too low-level for an ECS. I'd try to come up with the highest-level interface you can, especially for the data structures, that provide high-level methods suitable for an ECS system's needs. That could be considerably higher level than, say, push_back, insert, and erase and in a higher-level realm like query_components. Make it as high-level as you can, especially for non-sequence containers, to allow the maximum number of data structures to be used efficiently by the ECS.

Also unless you need to do dynamic allocations beyond these containers, I don't think you need to be able to specify allocators as policies to the ECS. Instead allocators can be policies for the data structure policies on how to allocate their data, and data structure policies are for the ECS.

There's also issues of how to reference a particular component or entity. That could vary based on the data structure. For example, I use 16-bit and 32-bit indices which is possible since I use random-access sequences to store component and entity data. However, I might have to use something different and more expensive like pointers if I used linked structures like a tree or a linked list where every node is allocated separately in ways that offer no guarantees about contiguity and don't provide random access. In that case, you might want Reference type(s) as template parameters which indicates what data type(s) you use to refer to specific entities or components in the system or something of this sort (perhaps this is a typedef the data structure policies specify). My brain hurts a bit trying to think of all the possibilities, but policy-based design tends to be the most flexible when you want to explore endless behavioral combinations without runtime abstraction costs.

That said, policy-based designs often fail to amass appeal for similar reasons I mentioned above. People have tried to come up with policy-based designs to allow you to customize a smart pointer's behavior to your heart's content only for people to just settle on unique_ptr and shared_ptr with their hard-coded behaviors. The idea of being able to explore endless combos of policies is generally more exciting conceptually than it is in practice. In practice, such flexibility tends to lead to a cumbersome solution which tends to get abandoned in favor of something with hard-coded behaviors but ones which are generally applicable enough and efficient enough for the widest range of people. Cumbersome solutions which allow exploring infinite possibilities will often be set aside from simple, featherweight solutions that only allow one very good and useful possibility. Hard-coding policies also carries the bonus that optimizations can be applied centrally in ways that can benefit everyone using the library without changing their own code.

  • 1
    Very interesting ideas, thanks for the answer. I'll have to mull it over, but doesn't your approach degrade when an entity has many components but you need the last one? Have you benchmarked this approach as opposed to others (say a sparse set, which I am considering currently). – user975989 Nov 30 '17 at 2:47
  • If you have many, many components attached to an entity, yeah, this won't hold up so well since it has to operate in linear time to find a specific component within an entity. It'll tend to outperform more sophisticated data structures for smaller cases like, say, 16 or fewer components attached. But if you have like 100+ component types attached to a single entity, then definitely that might call for some kind of acceleration, at least in those cases. In my system most entities tend to only have a handful of components attached -- for a single entity to have more than a dozen is a [...] – user204677 Dec 5 '17 at 0:33
  • [...] very unusual and pathological case, and so a simple linear search tends to actually be the best option for the common case here. Where this implementation shines is just really low memory use for entities and components, relatively speaking, and the ability to query what components are available system-wide really quickly in a cache-friendly way. – user204677 Dec 5 '17 at 0:33
  • And yes, benchmarked -- the 2 million entity particle demo was mainly a presentation I made comparing some other ECS approaches focusing on the type of speed we wanted for the engine. About using a sparse associative container instead, that would shine if you do have a boatload of components attached to one entity since you can search "vertically", not "horizontally" in linear time, with rows aligned to entities (like a giant sparse matrix). That said, I find it generally inapplicable to my case at least, where an entity with just 6-12 components or so is, by far, the common case... – user204677 Dec 5 '17 at 0:40
  • ... however, if it was, then the low memory footprint of this tends to make it easy enough to build the data structure on top for select use cases without feeling redundant. If the fundamental structure used to represent everything takes very little memory and processing to do its usual work, then building additional structures on top for select use cases tends to not feel so wasteful. – user204677 Dec 5 '17 at 0:41

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.