18
\$\begingroup\$

Lately I have been researching and implementing an Entity System for my framework. I think I read most articles, reddits and questions about it that I could find, and so far I think I am grasping the idea well enough.

However, it raised some questions about overall C++ behavior, the language I implement the entity system in, as well as some usability issues.

So, one approach would be to store an array of components in the entity directly, which I didn't do because it ruins the cache locality when iterating through data. Because of this, I decided to have one array per component type, so all components of the same type are contiguous in memory, which should be the optimal solution for quick iteration.

But, when I am to iterate component arrays to do something with them from a system on an actual gameplay implementation, I notice that I almost always am working with two or more component types at once. For example, the render system uses the Transform and the Model component together to actually make a render call. My question is, since I am not iterating linearly one contiguous array at a time in these cases, am I immediately sacrificing the performance gains from allocating components this way? Is it a problem when I iterate, in C++, two different contiguous arrays and use data from both at each cycle?

Another thing that I wanted to ask about, is how one should keep references to components or entities, since the very nature of how the components are laid in memory, they can easily switch positions in the array or the array could be reallocated for expanding or shrinking, leaving my component pointers or handles invalid. How do you recommend to handle these cases, since I often find myself wanting to operate on transforms and other components every frame and if my handles or pointers are invalid, its quite messy to make lookups every frame.

\$\endgroup\$
  • 4
    \$\begingroup\$ I wouldn't bother putting the components into a continuous memory but just allocate memory for each component dynamically. The contiguous memory unlikely gives you any cache performance gains because you are likely to access the components in pretty random order anyway. \$\endgroup\$ – JarkkoL Sep 24 '14 at 12:43
  • \$\begingroup\$ @Grimshaw Here is an interesting article to read: harmful.cat-v.org/software/OO_programming/_pdf/… \$\endgroup\$ – Raxvan Sep 24 '14 at 15:29
  • \$\begingroup\$ @JarkkoL -10 points. It really hurts performance if you build a system cache friendly and access it in random way, it is stupid only by sound of it. The point of it to access it in linear way. The art of the ECS and performance gain is about writing C/S accessed in linear way. \$\endgroup\$ – wondra Sep 24 '14 at 15:36
  • \$\begingroup\$ @Grimshaw do not forget cache is bigger then one integer. You got several KBs of L1 cache available(and MBs of other), if you do not do anything monsterous, it should OK to access few systems at once and while being cache-friendly. \$\endgroup\$ – wondra Sep 24 '14 at 15:40
  • 2
    \$\begingroup\$ @wondra How would you ensure linear access to components? Let say if I gather components for rendering and want entities processed in descending order from camera. The rendering components for these entities wont be linearly accessed in memory. While what you say is nice thing in theory I don't see it working in practice, but I'm glad if you prove me wrong (: \$\endgroup\$ – JarkkoL Sep 24 '14 at 16:05
13
\$\begingroup\$

First, I wouldn't say that in this case you are optimising too early, depending on your use case. In any case though, you've asked an interesting question and as I have experience with this myself, I'll weigh in. I'll try to just explain how I ended up doing things and what I found on the way.

  • Each entity holds a vector of generic component handles which can represent any type.
  • Each component handle can be dereferenced to yield a raw T* pointer. *See below.
  • Each component type has its own pool, a continuous block of memory (fixed size in my case).

It should be noted that no, you won't be able to just always traverse a component pool and do the ideal, clean thing. There are, as you have said, inescapable links between components, wherein you really need to process things an entity at a time.

However, there are cases (as I have found) where indeed, you can literally write a for loop for a particular component type and make great use of your CPU cache lines. For those who are unaware or wish to know more, take a look at https://en.wikipedia.org/wiki/Locality_of_reference. On the same note, when possible, do try to keep your component size less than or equal to your CPU cache line size. My line size was 64 bytes, which I believe is common.

In my case, making the effort of implementing the system was well worth it. I saw visible performance gains (profiled of course). You'll need to decide for yourself whether it is a good idea. The biggest gains in performance I saw at 1000+ entities.

Another thing that I wanted to ask about, is how one should keep references to components or entities, since the very nature of how the components are laid in memory, they can easily switch positions in the array or the array could be reallocated for expanding or shrinking, leaving my component pointers or handles invalid. How do you recommend to handle these cases, since I often find myself wanting to operate on transforms and other components every frame and if my handles or pointers are invalid, its quite messy to make lookups every frame.

I also solved this issue personally. I ended up having a system where:

  • Each component handle holds a reference to a pool index
  • When a component is 'deleted' or 'removed' from a pool, the last component within that pool is moved (literally with std::move) to the now free location, or none if you just deleted the last component.
  • When a 'swap' occurs, I have a callback which notifies any listeners, so that they may update any concrete pointers (e.g T*).

*I found that trying to always dereference component handles at runtime in certain sections of high use code with the number of entities I was dealing with was a performance problem. Because of that, I now maintain some raw T pointers in performance critical parts of my project, but otherwise I do use the generic component handles, which should be used where possible. I keep them valid as mentioned above, with the callback system. You may not need to go as far as that.

Above all though, just try things. Until you get a real world scenario, anything anyone says here is just one way of doing things, which may not be appropriate for you.

Does that help? I will try to clarify anything that is unclear. Also any corrections are appreciated.

\$\endgroup\$
  • \$\begingroup\$ Upvoted, this was a really good answer, and while it might not be a silver bullet, its still good to see someone had similar design ideas. I have some of your tricks implemented in my ES as well, and they seem practical. Thanks a lot! Feel free to comment further ideas if they come up. \$\endgroup\$ – Grimshaw Sep 24 '14 at 20:32
5
\$\begingroup\$

To answer just this:

My question is, since I am not iterating linearly one contiguous array at a time in these cases, am I immediately sacrificing the performance gains from allocating components this way? Is it a problem when I iterate, in C++, two different contiguous arrays and use data from both at each cycle?

No (at least not necessarily). The cache controller should, in most cases, be able to deal with reading from more than one contiguous array efficiently. The important part is to try where possible to access each array linearly.

To demonstrate this, I wrote a small benchmark (the usual benchmark caveats apply).

Starting with a simple vector struct:

struct float3 { float x, y, z; };

I found that a loop summing each element of two separate arrays and storing the result in a third performed exactly the same as a version where the source data was interleaved in a single array and the result stored in a third. I did find however, if I interleaved the result with the source, the performance suffered (by around a factor of 2).

If I accessed the data randomly, the performance suffered by a factor between 10 and 20.

Timings (10,000,000 elements)

linear access

  • separate arrays 0.21s
  • interleaved source 0.21s
  • interleaved source and result 0.48s

random access (uncomment random_shuffle)

  • separate arrays 2.42s
  • interleaved source 4.43s
  • interleaved source and result 4.00s

Source (compiled with Visual Studio 2013):

#include <Windows.h>
#include <vector>
#include <algorithm>
#include <iostream>

struct float3 { float x, y, z; };

float3 operator+( float3 const &a, float3 const &b )
{
    return float3{ a.x + b.x, a.y + b.y, a.z + b.z };
}

struct Both { float3 a, b; };

struct All { float3 a, b, res; };


// A version without any indirection
void sum( float3 *a, float3 *b, float3 *res, int n )
{
    for( int i = 0; i < n; ++i )
        *res++ = *a++ + *b++;
}

void sum( float3 *a, float3 *b, float3 *res, int *index, int n )
{
    for( int i = 0; i < n; ++i, ++index )
        res[*index] = a[*index] + b[*index];
}

void sum( Both *both, float3 *res, int *index, int n )
{
    for( int i = 0; i < n; ++i, ++index )
        res[*index] = both[*index].a + both[*index].b;
}

void sum( All *all, int *index, int n )
{
    for( int i = 0; i < n; ++i, ++index )
        all[*index].res = all[*index].a + all[*index].b;
}

class PerformanceTimer
{
public:
    PerformanceTimer() { QueryPerformanceCounter( &start ); }
    double time()
    {
        LARGE_INTEGER now, freq;
        QueryPerformanceCounter( &now );
        QueryPerformanceFrequency( &freq );
        return double( now.QuadPart - start.QuadPart ) / double( freq.QuadPart );
    }
private:
    LARGE_INTEGER start;
};

int main( int argc, char* argv[] )
{
    const int count = 10000000;

    std::vector< float3 > a( count, float3{ 1.f, 2.f, 3.f } );
    std::vector< float3 > b( count, float3{ 1.f, 2.f, 3.f } );
    std::vector< float3 > res( count );

    std::vector< All > all( count, All{ { 1.f, 2.f, 3.f }, { 1.f, 2.f, 3.f }, { 1.f, 2.f, 3.f } } );
    std::vector< Both > both( count, Both{ { 1.f, 2.f, 3.f }, { 1.f, 2.f, 3.f } } );

    std::vector< int > index( count );
    int n = 0;
    std::generate( index.begin(), index.end(), [&]{ return n++; } );
    //std::random_shuffle( index.begin(), index.end() );

    PerformanceTimer timer;
    // uncomment version to test
    //sum( &a[0], &b[0], &res[0], &index[0], count );
    //sum( &both[0], &res[0], &index[0], count );
    //sum( &all[0], &index[0], count );
    std::cout << timer.time();
    return 0;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ This helps a lot with my doubts about cache locality, thanks! \$\endgroup\$ – Grimshaw Sep 24 '14 at 20:33
  • \$\begingroup\$ Simple yet interesting answer that I also find reassuring :) I'd be interested to see how these results vary for different item counts (ie, 1000 instead of 10,000,000?) or if you had more arrays of values (ie, summing elements of 3-5 separate arrays and storing the value into another separate array). \$\endgroup\$ – Awesomania Dec 13 '14 at 8:34
2
\$\begingroup\$

Short Answer: Profile then optimize.

Long Answer:

But, when I am to iterate component arrays to do something with them from a system on an actual gameplay implementation, I notice that I almost always am working with two or more component types at once.

Is it a problem when I iterate, in C++, two different contiguous arrays and use data from both at each cycle?

C++ is not responsible for cache misses, as it applies for any programming language. This has to do with how modern CPU architecture works.

Your problem might be a good example of what might be called pre-mature optimization.

In my opinion you optimized too early for cache locality without looking at the program memory access patterns. But the bigger question is did you really need this kind (locality of reference) of optimization?

Agner's Fog suggests that you shouldn't optimize before you profile your application and/or know for sure where the bottlenecks are. (This is all mentioned in his excellent guide. Link below)

It is useful to know how a cache is organized if you are making programs that have big data structures with non-sequential access and you want to prevent cache contention. You may skip this section if you are satisfied with more heuristic guidelines.

Unfortunately what you did was actually assume that allocating one component type per array will give you better performance, while in reality you might have caused more cache misses or even cache contention.

You should definitely look at his excellent C++ optimization guide.

Another thing that I wanted to ask about, is how one should keep references to components or entities, since the very nature of how the components are laid in memory.

Personally I will allocate most used components together in a single memory block, so they have "near" addresses. For example an array will look like that:

[{ID0 Transform Model PhysicsComp }{ID10 Transform Model PhysicsComp }{ID2 Transform Model PhysicsComp }..] and then start optimizing from there if the performance was not "good enough".

\$\endgroup\$
  • \$\begingroup\$ My question was about the implications that my architecture could have on performance, the point wasn't to optimize but to choose a way to organize things internally. Regardless of the way it is happening inside, I want my game code to interact with it in an homogeneous way in case I want to change later. Your answer was good even if it could provide additional suggestions on how to store the data. Upvoted. \$\endgroup\$ – Grimshaw Sep 24 '14 at 13:37
  • \$\begingroup\$ From what I see, there are three main ways to store components, all coupled in a single array per entity, all coupled together by type in individual arrays, and if I understood correctly, you suggest to store different Entities contiguously in a big array, and per entity, have all of its components together? \$\endgroup\$ – Grimshaw Sep 24 '14 at 13:39
  • \$\begingroup\$ @Grimshaw As I mentioned in the answer, your architecture is not guaranteed to give better results than the normal allocation pattern. Since you don't really know the access pattern of your applications. Such optimizations are usually done after some study/evidence. Regarding my suggestion, store related components together in the same memory and other components in different locations. This is a middle ground between all or nothing. Yet, I still assume that it's hard to predict how your architecture will affect the outcome given how many conditions come into play. \$\endgroup\$ – concept3d Sep 24 '14 at 14:06
  • \$\begingroup\$ The downvoter care to explain ? Just point the problem in my answer. Better yet give a better answer. \$\endgroup\$ – concept3d Sep 24 '14 at 17:25
1
\$\begingroup\$

My question is, since I am not iterating linearly one contiguous array at a time in these cases, am I immediately sacrificing the performance gains from allocating components this way?

Chances are that you'll get fewer cache misses overall with separate "vertical" arrays per component type than interleaving the components attached to an entity in a "horizontal" variable-sized block, so to speak.

The reason is because, first, the "vertical" representation will tend to use less memory. You don't have to worry about alignment for homogeneous arrays allocated contiguously. With non-homogeneous types allocated into a memory pool, you do have to worry about alignment since the first element in the array could have a totally different size and alignment requirements from the second. As a result you'll often need to add padding, like so as a simple example:

// Assuming 8-bit chars and 64-bit doubles.
struct Foo
{
    // 1 byte
    char a;

    // 1 byte
    char b;
};

struct Bar
{
    // 8 bytes
    double opacity;

    // 8 bytes
    double radius;
};

Let's say we want to interleave Foo and Bar and store them right next to each other in memory:

// Assuming 8-bit chars and 64-bit doubles.
struct FooBar
{
    // 1 byte
    char a;

    // 1 byte
    char b;

    // 6 bytes padding for 64-bit alignment of 'opacity'

    // 8 bytes
    double opacity;

    // 8 bytes
    double radius;
};

Now instead of taking 18 bytes to store Foo and Bar in separate memory regions, it takes 24 bytes to fuse them. It doesn't matter if you swap the order:

// Assuming 8-bit chars and 64-bit doubles.
struct BarFoo
{
    // 8 bytes
    double opacity;

    // 8 bytes
    double radius;

    // 1 byte
    char a;

    // 1 byte
    char b;

    // 6 bytes padding for 64-bit alignment of 'opacity'
};

If you take more memory in a sequential access context without significantly improving accessing patterns, then you'll generally incur more cache misses. On top of that the stride to get from one entity to the next increases and to a variable size, making you have to take variable-sized leaps in memory to get from one entity to the next just to see which ones have the components you're interested in.

So using a "vertical" representation as you do of storing component types is actually more likely to be optimal than "horizontal" alternatives. That said, the problem with cache misses with the vertical representation can be exemplified here:

enter image description here

Where the arrows simply indicate that the entity "owns" a component. We can see that if we were to try to access all the motion and rendering components of entities that have both, we end up jumping all over the place in memory. That kind of sporadic access pattern can have you loading data into a cache line to access, say, a motion component, then access more components and have that former data evicted, only to load the same memory region again that was already evicted for another motion component. So that can be very wasteful loading the exact same memory regions more than once into a cache line just to loop through and access a list of components.

Let's clean up that mess a little bit so that we can see more clearly:

enter image description here

Note that if you encounter this kind of scenario, it's usually long after the game has started running, after many components and entities have been added and removed. In general when the game starts out, you might add all the entities and relevant components together, at which point they might have a very orderly, sequential access pattern with good spatial locality. After a lot of removals and insertions though, you might end up getting something like the above mess.

A very easy way to improve that situation is to simply radix sort your components based on the entity ID/index that owns them. At that point you get something like this:

enter image description here

And that's a much more cache-friendly access pattern. It's not perfect since we can see that we have to skip over some rendering and motion components here and there since our system is only interested in entities that have both of them, and some entities only have a motion component and some only have a rendering component, but you at least end up being able to process some contiguous components (more in practice, typically, since often you'll attach relevant components of interest, like maybe more entities in your system which have a motion component will have a rendering component than not).

Most importantly, once you have these sorted, you won't be loading data a memory region into a cache line only to then reload it in a single loop.

And this doesn't require some extremely complex design, just a linear-time radix sort pass every now and then, maybe after you've inserted and removed a bunch of components for a particular component type, at which point you can mark it as needing to be sorted. A reasonably-implemented radix sort (you can even parallelize it, which I do) can sort a million elements in about 6ms on my quad-core i7, as exemplified here:

Sorting 1000000 elements 32 times...
mt_sort_int: {0.203000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]
mt_sort: {1.248000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]
mt_radix_sort: {0.202000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]
std::sort: {1.810000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]
qsort: {2.777000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]

The above is to sort a million elements 32 times (including the time to memcpy results before and after sorting). And I'm assuming most of the time you won't actually have a million+ components to sort, so you should very easily be able to sneak this in now and there without causing any noticeable frame rate stutters.

\$\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.