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:
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:
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:
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.
