Skip to main content
GameDev.net gamedev.net
🔒 Locked

Data-oriented design, containers for components

Started by BattleMetalChris Jan 14, 2011 at 11:50 PM 10 replies 7k views
Original Post
BattleMetalChris
BattleMetalChris
I've been reading up on using data-oriented design principles (I now use c++, but came into programming through Java and strict OOP) and component based design, and trying to bend my head round towards the newer way of thinking about things.

One part I'm having trouble with is containers to actually hold the assorted components. In an OOP design (or at least, the things I've been writing in the past) any new objects are created on the heap, and a collection of pointers stored in say, a std::vector. This lets you store multiple pointers to the objects in various lists and also lets you add and delete objects happily. A problem is that because the objects are created dynamically, they're all over the place in memory which is really bad for cache misses, hence the more modern movement over to data oriented design. Am I right so far?

This involves splitting big classes with lots of inheritance into smaller components dealing with specific tasks and linking everything together with composition. The components themselves are stored in contiguous memory and this plus their smaller size means that as these containers are iterated over, several objects can be loaded into the cache at once from memory, improving performance significantly. Again, please correct me if I've got this wrong.

My problem is how are the containers of components to be implemented? To keep the memory they use contiguous, the objects have to be created on the stack and the objects themselves stored in a container, rather than just storing pointers in a container. How then do you cope when you have a changing number of objects? You can't use a std::vector because as you add more objects to the world, the vector would reassign it's arrays and have to create all the components again. This would also mean you wouldn't be able to store pointers to them as the memory location of the components would change if the vector changes size.

You could use an ordinary array, resized to some large arbitrary size (or a vector, and use reserve) but this would mean keeping every object you ever create in memory, and reserving memory for every object you are ever going to create, which is plainly ridiculous.

Can anyone guide me in the right direction?
stonemetal
stonemetal
If you need to keep pointers into the data structure data oriented design probably isn't the right way to go. Data oriented design is more for situations where you don't really care which element is which. like in a particle system each particle doesn't have a unique identity so you should not keep references to individual particles, all you do is loop over the particle collection and update each particle.
deepdene
deepdene
Well you don't keep every object you ever created in memory.

Ideally though you'd be deleting objects where you can do it in bulk to avoid memory fragmentation.

i.e. most games I've worked on you don't have virtual memory like you do in Win32 land, so memory fragmentation is the all important.

One typical approach if you have a bucket of memory, i.e. a layer. So a bucket for objects that should persist at all time, then buckets for the current level. When the current level is finished, the bucket is wiped freeing up large blocks of memory ready for the next level to load up memory. Normally the memory is persistent in the concept of a level, or in larger games in terms of a "region" etc.

This is just one way of dealing with the memory.

DoD is focusing on making sure you are dealing with memory in such a way to avoid cache hits by dealing with common elements all at once. i.e. As Mike Acton showed with the collision objects, your going to be dealing with more than just one collision object, so why you having your functions dealing with only a small subset at once?
dmatter
dmatter

In an OOP design (or at least, the things I've been writing in the past) any new objects are created on the heap, and a collection of pointers stored in say, a std::vector. This lets you store multiple pointers to the objects in various lists and also lets you add and delete objects happily. A problem is that because the objects are created dynamically, they're all over the place in memory which is really bad for cache misses, hence the more modern movement over to data oriented design. Am I right so far?
Reasonably so, yes. It's not quite fair to say that this has anything to do with OOP though, certainly you could end up with a similar sounding design (many micro-allocations with pointers flailing around everywhere) without using any OO whatsoever.

This involves splitting big classes with lots of inheritance into smaller components dealing with specific tasks and linking everything together with composition.[/quote]That's more specific to a component based design, than to data-oriented design. The term "composition" has well a defined meaning in programming parlance and doesn't quite suit when you think of a data-oriented design even though, in the abstract, an object is a composition of its parts, even in a DoD.

The components themselves are stored in contiguous memory and this plus their smaller size means that as these containers are iterated over, several objects can be loaded into the cache at once from memory, improving performance significantly. Again, please correct me if I've got this wrong.[/quote]There more to it here too. Not only will the cache pre-fetch data ahead of the current iteration point (hint: don't iterate backwards!) but because you are now presumably dealing with far simpler objects which are updated in more predictable ways it means you don't need to (and should not) be relying on dynamic dispatch (virtual functions) and conditional branching; instead you apply the same operation to all the components in the list so you suffer less on branch misprediction and cache misses for the purpose of locating code.

To keep the memory they use contiguous, the objects have to be created on the stack[/quote]No, this isn't true at all. Objects held in a std:: container are usually stored on the heap (but that's an implementation detail decided mostly by the allocator).

How then do you cope when you have a changing number of objects? You can't use a std::vector because as you add more objects to the world, the vector would reassign it's arrays and have to create all the components again. This would also mean you wouldn't be able to store pointers to them as the memory location of the components would change if the vector changes size.[/quote]Use indices The 5th item is always the 5th item, regardless of the memory location. Keep in mind, though, that random access (as opposed to sequential access) puts you back in the realm of bad cache performance because, well, it's random (i.e. non-predictable) access.
raigan
raigan
The "how to handle changing number of objects"/memory use question is something I've often wondered myself, that no one really seems to explicitly address.

As far as I can tell the assumption is that the application defines some maximum number of each type and at game/level load time an array of the appropriate max size is created, with each entry in each array containing an instance that stays there for the duration of the game/level. At least this seems to be the underlying assumption in articles such as A Dynamic Component Architecture for High Performance Gameplay

My guess would be that such systems require some design constraints, for example any object that can spawn other objects has some maximum number that can be spawned, and has to handle the "out of objects" case explicitly. For instance each Canon in Super Mario Bros is allocated 3 Bullet Bills and if they need to fire a 4th, they recycle the oldest one or simply don't fire until one of the 3 active Bullet Bills becomes inactive.

If you define such constraints, then you can know exacly the maximum number of each type of object that will be required for a given level. A looser approach would be to initially use gigantic arrays, and then log the maximum number of each type used as each level is played, then set the maximum array lengths based on the recorded values (with some additional headroom added). Neither approach seems amazing though, and I also have no idea how you would deal with a more dynamic game design, i.e users can create/destroy entities arbitrarily (a-la Little Big Planet).

There is also the issue of having to manage several dozens or hundreds of arrays since each concrete type needs its own array; it seems a bit messy/ugly.

I'd love to hear other peoples' experience/thoughts on this, to me it's the most interesting/confusing aspect of DoD since most of the presentations are very vague/abstract and don't explicitly discuss this sort of implementation detail that is nevertheless of supreme importance.
Chr0n1x
Chr0n1x

I'd love to hear other peoples' experience/thoughts on this, to me it's the most interesting/confusing aspect of DoD since most of the presentations are very vague/abstract and don't explicitly discuss this sort of implementation detail that is nevertheless of supreme importance.


A number of presentations I have seen go for the MAX_OBJECTS approach with arrays, but in a lot of cases this would probably depend on the game itself. If you are working with particles, you could probably work with a reasonable cap and not need to go past it, just be careful with how fast you emit the particles.

Preventing extra allocation is probably the best way to go, maybe even at the expense of some memory; or you can be smart about extra allocations. That is what std::vector does when extending itself, it increases by say 1.5x (actual amount is up to implementation) and that way the allocation cost is amortised.
Short-lived objects should still make use of a pool system for re-use later on to avoid allocations, and the rest of the objects are usually created at load time. If not, you could probably get away with occasionally (read: rarely) increasing the size of the array, as long as it remains contiguous so you can iterate over it sequentially and make good use of the cache.
Antheus
Antheus
Don't think about frameworks and hierarchy and such. Think about what really needs to be done.

- Physics. Ok, position + acceleration + velocity:
vector<Vector3D> position;
vector<Vector3D> acceleration;
vector<Vector3D> velocity;1:1:1 relation.

Some logic:vector<int> health;

Textures:vector<Texture *> textures;
vector<int> texture_indices;

Now look at actual and concrete use cases. Let's say this stuff needs to be renderer. Let's minimize state changes. Ideally, like textures would be grouped together. So sort by texture indices, but rearrange the positions as well. struct Renderable {
Vector3D position;
int texture_index;
}
vector<Renderable> rends;
...
// copy from position + texture_indices into rends
sort(rends, by_texture_index);
// render all rends

Or, let's do collision detection:
- //test all positions against all positions. Uses only one of data arrays.
- emit indices of colliding entities into vector>
- process all pairs, adjust one or more of position, acceleration, velocity

Culling:
- again, process only position array
- output list of indices of elements which are visible

PS. The position would probably need dimensions of sprite or AABB or similar, the above is just small simplification.

There is no inherent structure. Transformations are constructed as needed. Data is not necessarily normalized, it may be copied, grouped or filtered.

Such approach looks somewhat inefficient at first - copies and sorts. But in reality, copying is very cheap and sorting is done rarely - even if done semi-frequently on 10,000 objects it's not that big a deal.

What one gains - ability to reach full utilization of CPU and memory and ability to parallelize each of these operations. Sorting can be concurrent. Physics update can be concurrent. So can be logic updates.


At the same time this type of design makes it harder to experiment, since the underlying systems are always fully exposed and changing relations may require reorganization of some structures. It's less convenient, but can drastically improve throughput. The typical difference is anywhere up to factor 50.

Whether it's needed or not and whether it's cost effective is another thing.
raigan
raigan

// copy from position + texture_indices into rends


The question is how can you support this step AND support a dynamic number of positions? Or is this simply an impossible requirement to meet?
In most examples the lists are fixed-length and the rend knows the index of the position it uses, but such a system can't cope with a dynamic number of positions (since adding/removing screws up all the indices).
Antheus
Antheus

The question is how can you support this step AND support a dynamic number of positions? Or is this simply an impossible requirement to meet?
In most examples the lists are fixed-length and the rend knows the index of the position it uses, but such a system can't cope with a dynamic number of positions (since adding/removing screws up all the indices).

Why do you need a fixed index? What would the use case for this be? Which operation could not be implemented without having a fixed pointer to some particular component?
raigan
raigan

Why do you need a fixed index? What would the use case for this be? Which operation could not be implemented without having a fixed pointer to some particular component?


In most examples I've seen, the indices of the components are used as handles, and you need a fixed index so that e.g the rend component can refer to the components it depended on (position/texture/etc.) by their index in their respective list. A fixed pointer would have the same problem as a fixed index: you can't relocate entries, which means you can't delete components without leaving holes in the list. Which means you can no longer process the list uniformly, you need to have some sort of "active" flag in them which seems really wrong. Or you need some mechanism that lets you fix up the indices/pointers if you move/copy the last active entry into the space left by a deleted entry to fill the holes.

I guess I'm missing something obvious though.
BattleMetalChris
BattleMetalChris
The way I've been playing with is to have a std::vector holding the objects, so the memory is contiguous and as dmatter says, if I need to refer to a particular one, refer to it by index.
The vector can resize as necessary in the normal way.

The way I'm handling deletion of objects, and avoiding having 'holes' in my object vector is to hold a vector of which is just a list of indices which contain a 'dead' object. When I add another object, it'll check the first item on this list and put the new object there instead of using push_back.

When a std::vectors has to reallocate it's array are the objects copied over using something like memcpy so it's a quick operation? The only thing I can think of that would be a problem is if this resizing of the vector is slow.
Hodgman
Hodgman

... Am I right so far? ... Again, please correct me if I've got this wrong.
Yeah, pretty much
My problem is how are the containers of components to be implemented? To keep the memory they use contiguous, the objects have to be created on the stack and the objects themselves stored in a container, rather than just storing pointers in a container. How then do you cope when you have a changing number of objects? You can't use a std::vector because as you add more objects to the world, the vector would reassign it's arrays and have to create all the components again. This would also mean you wouldn't be able to store pointers to them as the memory location of the components would change if the vector changes size.[/quote]Resizing a std::vector isn't that bad. It's a big memcpy, sure, but not the end of the world. All the existing items keep the same indices so you can still keep track of individual items.
Instead of using a pointer to keep track of an item, use it's index instead.

Some engines even support "defragmentation" of these arrays, where "deleted" objects are moved to the end, and all used objects are compacted together. Do achieve this, you need a way to inform "link-holders" that [font="Courier New"]index x[/font] is now located at [font="Courier New"]index y[/font] (assuming that there are things holding links/pointers/indices to these items).
You could use an ordinary array, resized to some large arbitrary size (or a vector, and use reserve) but this would mean keeping every object you ever create in memory, and reserving memory for every object you are ever going to create, which is plainly ridiculous.[/quote]This really isn't ridiculous at all. When you're developing for consoles with a fixed (small) amount of RAM, you've got to set a memory budget and stick to it.
When you load a level, you can look at all the objects in the level, including things that create new objects, like spawn points. From that inspection pass, you can set an upper limit on the number of each object type that you'll require to be allocated at one time, and then simply allocate that number of objects.
When you "create" a new object, you're just fetching an unused one from this allocation. When you "delete" an object, you're adding it to a free-list so it can be recycled.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.