Data oriented access to several indexed data arrays

Question

I am working on an entity component system for a game engine. One of my goals is to use a data oriented approach for optimal data processing. In other words, I want to follow the guideline of rather wanting structs of arrays than arrays of structs. However, my problem is that I haven't managed to figure out a neat way to solve this for me.

My idea so far is that every component in the system is responsible for a specific part of the game logic, say that the Gravity Component takes care of calculating forces every frame depending on mass, velocity etc. and other components take care of other stuff. Hence every component is interested in different data sets. The Gravity Component might be interested in mass and velocity while the Collision Component might be interested in bounding boxes and position etc.

So far I figured I could have a data manager which saves one array per attribute. So say that entities may have one or more of weight, position, velocity, etc and they would have a unique ID. The data in the data manager would be represented as follows where every number represents an entity ID:

weightarray ->   [0,1,2,3]
positionarray -> [0,1,2,3]
velocityarray -> [0,1,2,3]

This approach works good if all entities have each one of the attributes. However if only entity 0 and 2 have all tree attributes and the other ones are entities of the type that does not move, they will not have velocity and the data would look:

weightarray ->   [0,1,2,3]
positionarray -> [0,1,2,3]
velocityarray -> [0,2]     //either squash it like this
velocityarray -> [0  ,2  ]     //or leave "empty gaps" to keep alignment

Suddenly it isn't as easy to iterate throught it. A component only interested in iterating over, and manipulating the velocity would have to either somehow skip the empty gaps if I went by the second approach. The first approach of keeping the array short wouldn't work well either in more complicated situations. Say if I have one entity 0 with all three attributes, another entity 1 having only weight and position, and an entity 2 which only has position and velocity. Finally there is one last entity 3 which only has weight. The arrays squashed would look like:

weightarray ->   [0,1,3]
positionarray -> [0,1,2]
velocityarray -> [0,2]

The other approach would leave gaps like so:

weightarray ->   [0,1, ,3]
positionarray -> [0,1,2, ]
velocityarray -> [0, ,2, ]

Both of these situations are nontrivial to iterate if you are only interested in iterating over the set of entities that only has a few of the attributes. A given component X would be interested in processing entities with position and velocity for instance. How can I extract iterable array pointers to give to this component to do its calculations? I would want to give it an array where the elements are just next to each other, but that seems impossible.

I've been thinking about solutions like having a bit field for every array, describing which spots are valid and which are gaps, or a system that copies over data to temporary arrays that have no holes and are then given to the components, and other ideas but none that I thought of was elegant and didn't have additional overhead for the processing (such as extra checks if data is valid, or extra copying of data).

I am asking here because I hope that someone of you might have experience with something similar or might have ideas or thoughts helpful in pursuing this issue. :) Also if this whole idea is crap and impossible to get right and you have a much better idea instead, please tell me. Hopefully the question isn't too long or cluttery.

Thanks.

Answer 1

Good question. However, as far as I can tell, there is no straightforward solution to this problem. There are multiple solutions (some of which you've mentioned) but I don't see an immediate silver bullet solution.

Let's look at the goal first. The goal isn't to put all data in linear arrays, that just the means to reach the goal. The goal is optimizing performance by minimizing cache misses. That's all. If you use OOP-Objects, your Entities data will be surrounded by data you don't necessarily need. If your architecture has a cache line size of 64 bytes and you only need weight (float), position (vec3) and velocity (vec3) you use 28 bytes, but the remaining 36 bytes will be loaded anyway. Even worse is when those 3 values are not side by side in memory or your data structure overlaps a cache line boundary, you will load multiple cache lines for just 28 bytes of actually used data.

Now this isn't that bad when you do this a few times. Even if you do it a hundred times, you will hardly notice it. However if you do this thousands of times each second, it may become an issue. So enter DOD, where you optimize for cache utilization, usually by creating linear arrays for each variable, in situations where there are linear access patterns. In your case arrays for weight, position, velocity. When you load the position of one entity, you again load 64 bytes of data. But because your position data is side by side in an array, you don't load 1 position value, you load the data for 5 adjacent entities. The next iteration of your update loop will probably need the next position value, which was already loaded in cache, and so on, until only at the 6th entity it will need to load new data from main memory.

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.

So there is your answer in short form: it all depends on your data usage. This is the reason I can't answer your question directly. I can give you some ideas on how to deal with your data, and you can decide for yourself which would be the most useful (if any of them are) in your situation, or maybe you can adapt/mix them up.

You could keep most accessed data in a continuous array. For instance, position is used often by many different components, so it is a prime candidate for a continuous array. Weight on the other hand is only used by the gravity component, so there can be gaps here. You've optimized for the most used case and will get less performance for data that is used less often. Still, I'm not a big fan of this solution for a number of reasons: it's still inefficient, you will load way too much empty data, the lower the ratio of # specific components/ # total entities is the worse it gets. If only one in 8 entities have gravity components, and these entities are spread evenly throughout the arrays, you still get one cache miss for each update. It also assumes all entities will have a position (or whatever is the common variable), it's hard to add and remove entities, it's inflexible and plain ugly (imho anyway). It may be the easiest solution though.

Another way to solve this is using indexes. Every array for a component will be packed, but there are two extra arrays, one to get entity id from a component array index and a second one to get the component array index from an entity id. Let's say position is shared by all entities while weight and velocity are only used by Gravity. You can now iterate over the packed weight and velocity arrays, and to get/set the corresponding position, you can get the gravityIndex -> entityID value, go to the Position component, use it's entityID -> positionIndex to get the correct index in the Position array. The advantage is your weight and velocity accesses will no longer give you cache misses, but you still get cache misses for the positions if the ratio between # gravity components / # position components is low. You also get an extra 2 array lookups, but a 16-bit unsigned int index should be enough in most cases so these arrays will fit nicely into the cache, meaning this might not be a very expensive operation in most cases. Still, profile profile profile to be sure of this!

A third option is data duplication. Now, I'm pretty sure this isn't going to be worth the effort in the case of your Gravity component, I think it's more interesting in computationally heavy situations, but let's take it as an example anyway. In this case, the Gravity component has 3 packed arrays for weight, velocity and position. It also has a similar index table to what you saw in the second option. When you start the Gravity component update, you first update the position array from the original position array in the Position component, using the index table as in example 2. Now you have 3 packed arrays that you can do your calculations with linearly with maximum cache utilization. When you're done, copy the position back to the original Position component using the index table. Now, this won't be faster (in fact probably slower) than the second option if you use it for something like Gravity, because you only read and write position once. However, suppose you have a component where entities interact with each other, with each update pass requiring multiple reads and writes, this may be faster. Still, all depends on access patterns.

The last option I'll mention is a change-based system. You can easily adapt this into something like a messaging system. In this case, you only update data that's changed. In your Gravity component, most objects will be lying on the floor without change, but a few are falling. The Gravity component has packed arrays for position, velocity, weight. If the position is updated during your update loop, you add the entity ID and the new position to a list of changes. When you're done, you send those changes to any other component that's keeping a position value. The same principle if any other component (for instance, the player control component) changes the position, it will send the new positions of changed entities, the Gravity component can listen to that and update only those positions in its positions array. You'll duplicate a lot of data just like in the previous example, but instead of rereading all data every update cycle, you only update data when it changes. Very useful in situations where small amounts of data actually change each frame, but might get ineffective if large amounts of data change.

So there is no silver bullet. There are a lot of options. The best solution is entirely dependent on your situation, on your data and the way you process that data. Maybe none of the examples I gave are right for you, maybe all of them are. Not every component has to work in the same way, some might use the change/message system while others use the indexes option. Remember that while many DOD performance guidelines are great if you need the performance, it is only useful in certain situations. DOD is not about always using arrays, it is not about always maximizing cache utilization, you should only do this where it actually matters. Profile profile profile. Know your data. Know your data access patterns. Know your (cache) architecture. If you do all of that, solutions will become apparent when you reason about it :)

Hope this helps!