Tell me more ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 0 down vote favorite

Over every entity system I see implemented in C++, or even in Java/C# (e.g. the Artemis framework). I see components not allocated via a new operator (or something similar, e.g. std::make_shared). For example:

entity.addComponent(new Position(32, 4, 5));
entity2.addComponent(new Position(5, 6, 7));
// those two position components that were just created
// may/may not be together in memory

// or even:
// how can you avoid using new here? (in the implementation)
entity.addComponent<Position>(32, 4, 5);

Doesn't this harm performance, as there would be cache misses (since new can allocate data anywhere from the heap)? How would you implement a system in such a way that the components of each type are allocated contiguously in memory, so you avoid cache misses? I mainly want to know how one would do so in C++.

share|improve this question
 
If you use C++11 you can just push elements to a vector<Position>. Be sure to implement move operations and delete copy operations. –  Luke B. Jul 10 at 17:09
 
@LukeB. Not what I am trying to ask... –  miguel.martin Jul 11 at 10:36
 
You asked for a way to have components aligned in memory to avoid cache misses, if you use a vector you have the elements aligned. You won't use new, just emplace a component. Isn't this what you wanted? –  Luke B. Jul 11 at 14:42
 
Of course the vector manages its memory using new, but you can't get dynamic memory without new somewhere –  Luke B. Jul 11 at 15:00

3 Answers

up vote 4 down vote accepted

Most entity systems don't use Data Oriented Design. Note that entity system doesn't necessarily imply DOD, it just means splitting gameplay functionality into different component classes giving entities certain features and behavior. You can (very easily) create a bloated and horribly slow Object-Oriented version of an entity system. So entity systems are just a design concept. DOD is a completely orthogonal code design concept that can however be applied very easily to entity systems.

So on to your questions:

Doesn't this harm performance, as there would be cache misses (since new can allocate data anywhere from the heap)?

Yes. Well, maybe. It all depends on access patterns. But yeah, if you want to update all Position components in one go, well designed and aligned data can be far more efficient. Still, know your data and know how you use your data te be sure.

How would you implement a system in such a way that the components of each type are allocated contiguously in memory, so you avoid cache misses?

There are multiple ways to do that using preallocated memory and such, you could use multiple smaller pools for finegrained memory control or if you know how much a level is going to use, you can just allocate that much memory etcetera etcetera. This is all described in the answers the others gave.

That could be a solution, but I think you're treating a symptom, not the real problem: You want to use classes. Don't do that, if possible. It's bad for a number of reasons, among which is cache locality. There is no reason for either the entity or the components to be classes. Now I've talked about this at more length in my answer here: When/where to update components I'll give you a very quick rundown though, or just read the long answer there and skip the next two paragraphs

All the entity is is an identifier that binds together a number of components. The entity could just be a unique integer. It can also be a class with a set of pointers pointing to all component data if you need that. Still, I don't see the necessity for that. If an entity is a unique integer, you could just as easily write a helper function to get a component given an entity id.

So now to get rid of the component classes themselves. There's no actual need for that either. What you need is two things: some data stored somewhere for each component (component data) and some way to update that data (component behavior). What a component class does is combine those two, but there are other ways. For instance, creating a component system where there are managers for each component type. All component data is stored in arrays in the manager, accessed using the entity id (which is just an integer as I said above, more about that in my answer here). The behavior is one simple update() function in the manager class which updates all components it manages in one go, fully utilizing the cache locality and optimization benefits a single update loop provides.

The same thing could be done using component classes which are aligned in memory, but there are still a lot of issues with that approach, most important of which are memory/cache related. What happens when you delete a component from memory? You can't just move one of the other components into the empty space, since that would mess up all pointers pointing to that component. How big is your component class data? It may very well be about the size of one cache line (64 bytes in modern x86). If that's the case, your system will hardly be any faster than one where data is all over memory.

The biggest issue is how you use your data. How much component data do you need each update? Say you have a component with a position (vec3), velocity (vec3) and two other 4 byte variables. That's 32 bytes of data per component (assuming you don't use any virtual function crap). Now when you update your component, you may need all variables and you need to load all data. That's fine. Cache line size is 64 and your components are all packed in memory, so when you load one component, you automatically load the next one into cache. Great. Now what happens when you only need to access the position for another unrelated update loop. You load 64 bytes of data, but it's only got 2 vec3's you need. You've just wasted 40 loaded bytes of data. This is exactly what DOD is about avoiding.

If on the other hand, you had a component manager class which stores component data in number of arrays, one for positions, one for velocities and two for the other data, your cache will be utilized fully in both situations. So if you only need velocities, when it loads one, it will load 64 bytes around it into cache. That's more than five velocity vectors. When you need all data, it will do the same for the data in the other arrays.

So to summarize, I'll quote a bit from another answer I gave here

So the goal of DOD isn't using linear arrays, it's maximizing cache utilization by placing data that is accessed at (about) the same time adjacent in memory. If you nearly always access 3 variables at the same time, you don't need to create 3 arrays for each variable, you could just as easily create a struct which contains only those 3 values and create an array of these structs. The best solution always depends on the way you use the data. If your access patterns are linear, but you don't always use all variables, go for separate linear arrays. If your access patterns are more irregular but you always use all variables at the same time, put them in a struct together and create an array of those structs.

Hope this helps! Let me know if anything is unclear or if I missed something!

share|improve this answer
 
Seems a bit more complicated if I want to have a full blown data oriented design, but thanks for the answer! –  miguel.martin Jul 18 at 15:32
up vote 0 down vote

If you absolutely want to do this, you can use a custom memory allocator that reserves a chunk for each Entity and places its components continously inside that chunk. However this may waste memory again, which can (in theory) cause more cache misses too...

However... unless you have solid proof that this causes slowdowns for you, don't worry about it. Premature optimization can eat up a lot of your time, not only when creating the system, but also when maintaining it later. Most likely your game engine's speed isn't going to be determined by trivial things like this, not to mention that complex components (the ones that may actually slow things down for you) are most likely larger and would cause cache misses anyway.

Having said that, your particular example may be somewhat valid. I think the position of an entity should be bundled together with the entity itself (part of the class, not a component) for two reasons. First of all, if you do a lot of data processing on the entities, it may improve performance. But more importantly, each entity can only have one position, and the possibility of adding several position components breaks this rule, causing problems.

share|improve this answer
 
Entities can absolutely have more than one position once interpolation handling for fixed-timestep physics and network updates are in. –  Sean Middleditch Jul 10 at 17:30
up vote 0 down vote

entity.addComponent<Position>(32, 4, 5);

Is definitely possible using C++11 variadic templates, with no performance difference from the original versions.

struct Entity
{
    std::vector<std::unique_ptr<Component>> components;

    template<typename T, typename... TArgs> T& createComponent(TArgs&&... mArgs)
    {
        auto result(new T(std::forward<TArgs>(mArgs)...));
        components.push_back(std::unique_ptr<Component>(result));
        return *result;
    }
}

Entity entity;
entity.createComponent<Position>(32, 4, 5); // valid

Cache misses will be present when allocating with new, but it's not so bad. In my entity system I can create/destroy >10000 components without noticeable frame loss. It will probably never be a bottleneck, unless you require an amazingly high amount of entities/components.

If you want to check my implementation, it's on GitHub.

If you want to check a data-oriented component entity system, check out Artemis.

share|improve this answer
 
I already know entity.addComponent<Position>(32, 4, 5); is possible. What I'm asking is how would you avoid using new to create components, so that components are aligned in memory. –  miguel.martin Jul 10 at 12:01
 
@miguel.martin unless you pre allocate them and pool them, there is no other way of creating new items. –  Sidar Jul 10 at 12:12
 
@Sidar this interest me too - is there any implementation of custom allocators that work in this way? –  Vittorio Romeo Jul 10 at 12:30
 
@VittorioRomeo Not that I'm aware of. In the end you are still allocating memory. Pre-allocate too much and you are wasting memory. Pre-allocate too little and you are bound to use the "new" operator anyways. unless Miguel is facing bottlenecks, I wouldn't even be bothered by it. –  Sidar Jul 10 at 12:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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