Data Oriented Design Game Dev

There has been a lot of recent discussion (and criticism) on Data Oriented Design recently. I want to address some of the issues that have been raised, but before that, I'll start with this reprint from my most recent Game Developer Magazine. If you have any questions you'd like addressed, add write a comment and I'll try to answer everything I can.

Last year I wrote about the basics of Data-Oriented Design (see the September 2009 issue of Game Developer). In the time since that article, Data-Oriented Design has gained a lot of traction in game development and many of teams are thinking in terms of data for some of the more performance-critical systems. Continue reading →

I've been meaning to put up the rest of the Inner Product columns I wrote for Game Developer Magazine, but I wasn't finding the time. With all the recent discussion on data-oriented design, I figured it was time to dust some of them off.

This was one of the first columns I wrote. At first glance it might seem a completely introductory topic, not worth spending that much time on it. After all, all experience programmers know about pointers and indices, right? True, but I don't think all programmers really take the time to think about the advantages and disadvantages of each approach, and how it affects architecture decisions, data organization, and memory traversal.

It should provide a good background for this coming Thursday's #iDevBlogADay post on how to deal with heterogeneous objects in a data-oriented way.

From a 10,000-Foot view, all video games are just a sequence of bytes. Those bytes can be divided into code and data. Code is executed by the hardware and it performs operations on the data. This code is generated by the compiler and linker from the source code in our favorite computer language. Data is just about everything else. [1]

As programmers, weâ€™re obsessed with code: beautiful algorithms, clean logic, and efficient execution. We spend most of our time thinking about it and make most decisions based on a code-centric view of the game.

Modern hardware architectures have turned things around. A data-centric approach can make much better use of hardware resources, and can produce code that is much simpler to implement, easier to test, and easier to understand. In the next few months, weâ€™ll be looking at different aspects of game data and how everything affects the game. This month we start by looking at how to manage data relationships.

Data Relationships

Data is everything that is not code: meshes and textures, animations and skeletons, game entities and pathfinding networks, sounds and text, cut scene descriptions and dialog trees. Our lives would be made simpler if data simply lived in memory, each bit totally isolated from the rest, but thatâ€™s not the case. In a game, just about all the data is intertwined in some way. A model refers to the meshes it contains, a character needs to know about its skeleton and its animations, and a special effect points to textures and sounds.

How are those relationships between different parts of data described? There are many approaches we can use, each with its own set of advantages and drawbacks. There isnâ€™t a one-size-fits-all solution. Whatâ€™s important is choosing the right tool for the job.

Pointing The Way

In C++, regular pointers (as opposed to â€œsmart pointersâ€ which weâ€™ll discuss later on) are the easiest and most straightforward way to refer to other data. Following a pointer is a very fast operation, and pointers are strongly typed, so itâ€™s always clear what type of data theyâ€™re pointing to.

However, they have their share of shortcomings. The biggest drawback is that a pointer is just the memory address where the data happens to be located. We often have no control over that location, so pointer values usually change from run to run. This means if we attempt to save a game checkpoint which contains a pointer to other parts of the data, the pointer value will be incorrect when we restore it.

Pointers represent a many-to-one relationship. You can only follow a pointer one way, and it is possible to have many pointers pointing to the same piece of data (for example, many models pointing to the same texture). All of this means that it is not easy to relocate a piece of data that is referred to by pointers. Unless we do some extra bookkeeping, we have no way of knowing what pointers are pointing to the data we want to relocate. And if we move or delete that data, all those pointers wonâ€™t just be invalid, theyâ€™ll be dangling pointers. They will point to a place in memory that contains something else, but the program will still think it has the original data in it, causing horrible bugs that are no fun to debug.

One last drawback of pointers is that even though theyâ€™re easy to use, somewhere, somehow, they need to be set. Because the actual memory location addresses change from run to run, they canâ€™t be computed offline as part of the data build. So we need to have some extra step in the runtime to set the pointers after loading the data so the code can use them. This is usually done either by explicit creation and linking of objects at runtime, by using other methods of identifying data, such as resource UIDs created from hashes, or through pointer fixup tables converting data offsets into real memory addresses. All of it adds some work and complexity to using pointers.

Given those characteristics, pointers are a good fit to model relationships to data that is never deleted or relocated, from data that does not need to be serialized. For example, a character loaded from disk can safely contain pointers to its meshes, skeletons, and animations if we know weâ€™re never going to be moving them around.

Indexing

One way to get around the limitation of not being able to save and restore pointer values is to use offsets into a block of data. The problem with plain offsets is that the memory location pointed to by the offset then needs to be cast to the correct data type, which is cumbersome and prone to error.

The more common approach is to use indices into an array of data. Indices, in addition to being safe to save and restore, have the same advantage as pointers in that theyâ€™re very fast, with no extra indirections or possible cache misses.

Unfortunately, they still suffer from the same problem as pointers of being strictly a many-to-one relationship and making it difficult to relocate or delete the data pointed to by the index. Additionally, arrays can only be used to store data of the same type (or different types but of the same size with some extra trickery on our part), which might be too restrictive for some uses.

A good use of indices into an array are particle system descriptions. The game can create instances of particle systems by referring to their description by index into that array. On the other hand, the particle system instances themselves would not be a good candidate to refer to with indices because their lifetimes vary considerably and they will be constantly created and destroyed.

Itâ€™s tempting to try and extend this approach to holding pointers in the array instead of the actual data values. That way, we would be able to deal with different types of data. Unfortunately, storing pointers means that we have to go through an extra indirection to reach our data, which incurs a small performance hit. Although this performance hit is something that we're going to have to live with for any system that allows us to relocate data, the important thing is to keep the performance hit as small as possible.

An even bigger problem is that, if the data is truly heterogeneous, we still need to cast it to the correct type before we use it. Unless all data referred to by the pointers inherits from a common base class that we can use to query for its derived type, we have no easy way to find out what type the data really is.
On the positive side, now that weâ€™ve added an indirection (index to pointer, pointer to data), we could relocate the data, update the pointer in the array, and all the indices would still be valid. We could even delete the data and null the pointer out to indicate it is gone. Unfortunately, what we canâ€™t do is reuse a slot in the array since we donâ€™t know if thereâ€™s any data out there using that particular index still referring to the old data.

Because of these drawbacks, indices into an array of pointers is usually not an effective way to keep references to data. Itâ€™s usually better to stick with indices into an array of data, or extend the idea a bit further into a handle system, which is much safer and more versatile.

Handle-Ing The Problem

Handles are small units of data (32 bits typically) that uniquely identify some other part of data. Unlike pointers, however, handles can be safely serialized and remain valid after theyâ€™re restored. They also have the advantages of being updatable to refer to data that has been relocated or deleted, and can be implemented with minimal performance overhead.

The handle is used as a key into a handle manager, which associates handles with their data. The simplest possible implementation of a handle manager is a list of handle-pointer pairs and every lookup simply traverses the list looking for the handle. This would work but itâ€™s clearly very inefficient. Even sorting the handles and doing a binary search is slow and we can do much better than that.

Here's an efficient implementation of a handle manager (released under the usual MIT license, so go to town with it). The handle manager is implemented as an array of pointers, and handles are indices into that array. However, to get around the drawbacks of plain indices, handles are enhanced in a couple of ways.

In order to make handles more useful than pointers, weâ€™re going to use up different bits for different purposes. We have a full 32 bits to play with, so this is how weâ€™re going to carve them out:

The index field. These bits will make up the actual index into the handle manager, so going from a handle to the pointer is a very fast operation. We should make this field as large as we need to, depending on how many handles we plan on having active at once. 14 bits give us over 16,000 handles, which seems plenty for most applications. But if you really need more, you can always use up a couple more bits and get up to 65,000 handles.
The counter field. This is the key to making this type of handle implementation work. We want to make sure we can delete handles and reuse their indices when we need to. But if some part of the game is holding on to a handle that gets deletedâ€"and eventually that slot gets reused with a new handleâ€"how can we detect that the old handle is invalid? The counter field is the answer. This field contains a number that goes up every time the index slot is reused. Whenever the handle manager tries to convert a handle into a pointer, it first checks that the counter field matches with the stored entry. Otherwise, it knows the handle is expired and returns null.
The type field. This field indicates what type of data the pointer is pointing to. There are usually not that many different data types in the same handle manager, so 6â€"8 bits are usually enough. If youâ€™re storing homogeneous data, or all your data inherits from a common base class, then you might not need a type field at all.

struct Handle {     Handle() : m_index(0), m_counter(0), m_type(0)     {}      Handle(uint32 index, uint32 counter, uint32 type)         : m_index(index), m_counter(counter), m_type(type)     {}      inline operator uint32() const;          uint32 m_index : 12;     uint32 m_counter : 15;     uint32 m_type : 5; };  Handle::operator uint32() const {     return m_type << 27 | m_counter << 12 | m_index; }

The workings of the handle manager itself are pretty simple. It contains an array of HandleEntry types, and each HandleEntry has a pointer to the data and a few other bookkeeping fields: freelist indices for efficient addition to the array, the counter field corresponding to each entry, and some flags indicating whether an entry is in use or itâ€™s the end of the freelist.

struct HandleEntry { 	HandleEntry(); 	explicit HandleEntry(uint32 nextFreeIndex); 	 	uint32 m_nextFreeIndex : 12; 	uint32 m_counter : 15; 	uint32 m_active : 1; 	uint32 m_endOfList : 1; 	void* m_entry; };

Accessing data from a handle is just a matter of getting the index from the handle, verifying that the counters in the handle and the handle manager entry are the same, and accessing the pointer. Just one level of indirection and very fast performance.

We can also easily relocate or invalidate existing handles just by updating the entry in the handle manager to point to a new location or to flag it as removed.

Handles are the perfect reference to data that can change locations or even be removed, from data that needs to be serialized. Game entities are usually very dynamic, and are created and destroyed frequently (such as enemies spawning and being destroyed, or projectiles). So any references to game entities would be a good fit for handles, especially if this reference is held from another game entity and its state needs to be saved and restored. Examples of these types of relationships are the object a player is currently holding, or the target an enemy AI has locked onto.

Getting Smarter

The term smart pointers encompasses many different classes that give pointer-like syntax to reference data, but offer some extra features on top of â€œrawâ€ pointers.

A common type of smart pointer deals with object lifetime. Smart pointers keep track of how many references there are to a particular piece of data, and free it when nobody is using it. For the runtime of games, I prefer to have very explicit object lifetime management, so Iâ€™m not a big fan of this kind of pointers. They can be of great help in development for tools written in C++ though.

Another kind of smart pointers insert an indirection between the data holding the pointer and the data being pointed. This allows data to be relocated, like we could do with handles. However, implementations of these pointers are often non- serializable, so they can be quite limiting.

If you consider using smart pointers from some of the popular libraries (STL, Boost) in your game, you should be very careful about the impact they can have on your build times. Including a single header file from one of those libraries will often pull in numerous other header files. Additionally, smart pointers are often templated, so the compiler will do some extra work generating code for each data type you instantiated templates on. All in all, templated smart pointers can have a significant impact in build times unless they are managed very carefully.

Itâ€™s possible to implement a smart pointer that wraps handles, provides a syntax like a regular pointer, and it still consists of a handle underneath, which can be serialized without any problem. But is the extra complexity of that layer worth the syntax benefits it provides? It will depend on your team and what youâ€™re used to, but itâ€™s always an option if the team is more comfortable dealing with pointers instead of handles.

Conclusion

There are many different approaches to expressing data relationships. Itâ€™s important to remember that different data types are better suited to some approaches than others. Pick the right method for your data and make sure itâ€™s clear which one youâ€™re using.

In the next few months, weâ€™ll continue talking about data, and maybe even convince you that putting some love into your data can pay off big time with your code and the game as a whole.

This article was originally printed in the September 2008 issue of Game Developer.

[1] I'm not too happy about the strong distinction I was making between code and data. Really, data is any byte in memory, and that includes code. Most of the time programs are going to be managing references to non-code data, but sometimes to other code as well: function pointers, compiled shaders, compiled scripts, etc. So just ignore that distinction and think of data in a more generic way.

This is my first entry into #iDevBlogADay. It all started very innocently with a suggestion from Miguel, but the ball got rolling pretty quickly. The idea is to have one independent iPhone game developer write a blog entry each day of the week. At first we thought we would be hard-pressed to get 7 developers, but it's starting to seem we might have multiples per day!

Check out the new sidebar with all the #iDevBlogADay blogs. We're also putting together a common RSS feed if you want to subscribe to that instead.

Writing is addictive, so don't be surprised if this once-a-week minimum turns into multiple-times-a-week.

Every developer who's been working on a team for a while is able to tell the author of a piece of code just by looking at it. Sometimes it's even fun to do a forensic investigation and figure out not just the original author, but who else modified the source code afterwards.

What I find interesting is that I can do the same thing with my own code… as it changes over time. Every new language I learn, every book I read, every bit of code I see, every open-source project I browse, every pair-programming session, every conversation with a fellow developer leaves a mark behind. It slightly changes how I think of things, and realigns my values and priorities as a programmer. And those new values translate into different ways to write code, different architectures, and different coding styles.

It never happens overnight. I can't recall a single case where I changed my values in a short period of time, causing dramatic changes to my coding style. Instead, it's the accumulation of lots of little changes here and there that slowly shifts things around. It's like the movement of the Earth's magnetic pole: very slow, but changes radically over time (although maybe just a tad bit faster).

Why Talk About Coding Styles

Coding style in itself is purely a personal thing, and therefore, very uninteresting to talk about. However, in its current form, my coding style goes against the grain of most general modern "good practices". A few weeks ago I released some sample source code and it caused a bit of a stir because it was so unconventional. That's when I realized it might be worth talking about it after all (along with George bugging me about it), and especially the reasons why it is the way it is.

Before I even start, I want to stress that I'm not advocating this approach for everybody, and I'm certainly not saying it's the perfect way to go. I know that in a couple of years from now, I'll look back at the code I'm writing today and it will feel quaint and obsolete, just like the code I wrote during Power of Two Games looks today. All I'm saying is that this is the style that fits me best today.

Motivation

This is my current situation which shapes my thinking and coding style:

All my code is written in C and C++ (except for a bit of ObjC and assembly).
It's all for real-time games on iPhone, PCs, or modern consoles, so performance and resource management are very important.
I always try to write important code through Test-Driven Development.
I'm the only programmer (and only designer).
Build times in my codebase are very fast.

And above all, I love simplicity. I try to achieve simplicity by considering every bit of code and thinking whether it's absolutely necessary. I get rid of anything that's not essential, or that's not benefitting the project by at least two or three times as much as it's complicating it.

How I Write Today

So, what does my code look like these days? Something like this (this is taken from a prototype I wrote with Miguel of Mystery Coconut fame):

namespace DiverMode {     enum Enum     {         Normal,         Shocked,         Inmune,     }; }  struct DiverState {     DiverState()         : mode(DiverMode::Normal)         , pos(0,0)         , dir(0)         , o2(1)         , boostTime(0)         , timeLeftInShock(0)         , timeLeftImmune(0)     {}      DiverMode::Enum mode;     Vec2 pos;     float dir;     float o2;      float boostTime;     float timeLeftInShock;     float timeLeftImmune; };  namespace DiverUtils {     void Update(float dt, const Vec2& tiltInput, GameState& state);     void Shock(DiverState& diver);     void StartSprint(DiverState& diver);     void StopSprint(DiverState& diver); }

The first thing that stands out is that I'm using a struct and putting related functions in a namespace. It may seem that's just a convoluted way of writing a class with member functions, but there's more to it than that.

By keeping the data in a struct instead of a class, I'm gaining several advantages:

I'm showing all the data there is and how big it is. Nothing is hidden.
I'm making it clear that it's free of pointers and temporary variables.
I'm allowing this data to be placed anywhere in memory.

The fact that the functions are part of a namespace is not really defensible; it's pure personal preference. It would have been no different than if I had prefixed them with DriverUtils_ or anything else, I just think it looks clearner. I do prefer the functions to be separate and not member functions though. It makes it easier to organize functions that work on multiple bits of data at once. Otherwise you're stuck deciding whether to make them members of one structure or another. It also makes it easier to break up data structures into separate structures later on and minimize the amount of changes to the code.

Probably one of the biggest influences on me starting down this path was the famous article by Scott Meyers How Non Member Functions Improve Encapsulation. I remember being shocked the first time I read it (after having read religiously Effective C++ and More Effective C++). That reasoning combined with all the other changes over the years, eventually led to my current approach.

Since everything is in a structure and everything is public, there's very little built-in defenses against misuse and screw-ups. That's fine because that's not a priority for me. Right now I'm the only programmer, and if I work with someone else, I expect them to have a similar level of experience than me. Some codebases written with a defensive programming approach have an amazing amount of code (and therefore complexity) dedicated to babysitting programmers. No thanks. I do make extensive use of asserts and unit tests to allow me to quickly make large refactorings though.

Another thing to note that might not be immediately obvious from the example above is that all functions are very simple and shallow. They take a set of input parameters, and maybe an output parameter or just a return value. They simply transform the input data into the output data, without making extensive calls to other functions in turn. That's one of the basic approaches of data-oriented design.

Because everything is laid out in memory in a very simple and clear way, it means that serialization is a piece of cake. I can fwrite and fread data and have instant, free serialization (you only need to do some extra work if you change formats and try to support older ones). Not only that, but it's great for saving the game state in memory and restoring it later (which I'm using heavily in my current project). All it takes is this line of code:

oldGameState = currentGameState

This style is a dream come true for Test-Driven Development (TDD). No more worrying about mocks, and test injections, or anything like that. Give the function some input data, and see what the output is. Done! That simple.

One final aspect of this code that might be surprising to some is how concrete it is. This is not some generic game entity that hold some generic components, with connections defined in XML and bound together through templates. It's a dumb, POD Diver structure. Diver as in the guy going swimming underwater. This prototype had fish as well, and there was a Fish structure, and a large array of sequential, homogeneous Fish data. The main loop wasn't generic at all either: It was a sequence of UpdateDivers(), UpdateFish(), etc. Rendering was done in the same, explicit way, making it extra simple to minimize render calls and state changes. When you work with a system like this, you never, ever want to go back to a generic one where you have very little idea about the order in which things get updated or rendered.

Beyond The Sample

To be fair, this sample code is very, very simple. The update function for a reasonable game element is probably larger than a few lines of code and will need to do a significant amount of work (check path nodes, cast rays, respond to collisions, etc). In that case, if it makes sense, the data contained in the structure can be split up. Or maybe the first update function generates some different output data that gets fed into later functions. For example, we can update all the different game entities, and as an output, get a list of ray cast operations they want to perform, do them all in a later step, and then feed the results back to the entities either later this frame or next frame if we don't mind the added latency.

There's also the question of code reuse. It's very easy to reuse some low level functions, but what happens when you want to apply the same operation to a Diver and to a Fish? Since they're not using inheritance, you can't use polymorphism. I'll cover that in a later blog post, but the quick preview is that you extract any common data that both structs have and work on that data in a homogeneous way.

What do you think of this approach? In which ways do you think it falls short, and in which ways do you like it better than your current style?

Memory CPU gap A few days ago, Tony Albrecht posted the slides of his presentation titled "Pitfalls of Object-Oriented Design" [1]. Even though the title is really broad and could easily be misinterpreted, it's not just a general bash on OOD. Instead, it's very much focused on how object-oriented design is not a good match for high-performance apps (games) on modern hardware architectures with slow memory access and deep memory hierarchies. His proposed solution: Data-oriented design.Â Spot on!

If you haven't seen the presentation, go download it right now. It's really well put together and he has some great detailed examples on how caches are affected with traditional object-oriented design vs. a more data-oriented approach.

[1] Thanks to Christer Ericson for pointing that out.

Picture this: Toward the end of the development cycle, your game crawls, but you donâ€™t see any obvious hotspots in the profiler. The culprit? Random memory access patterns and constant cache misses. In an attempt to improve performance, you try to parallelize parts of the code, but it takes heroic efforts, and, in the end, you barely get much of a speed-up due to all the synchronization you had to add. To top it off, the code is so complex that fixing bugs creates more problems, and the thought of adding new features is discarded right away. Sound familiar?

That scenario pretty accurately describes almost every game Iâ€™ve been involved with for the last 10 years. The reasons arenâ€™t the programming languages weâ€™re using, nor the development tools, nor even a lack of discipline. In my experience, itâ€™s object- oriented programming (OOP) and the culture that surrounds it that is in large part to blame for those problems. OOP could be hindering your project rather than helping it!

It's All About Data

OOP is so ingrained in the current game development culture that itâ€™s hard to think beyond objects when thinking about a game. After all, weâ€™ve been creating classes representing vehicles, players, and state machines for many years. What are the alternatives? Procedural programming? Functional languages? Exotic programming languages?

Data-oriented design is a different way to approach program design that addresses all these problems. Procedural programming focuses on procedure calls as its main element, and OOP deals primarily with objects. Notice that the main focus of both approaches is code: plain procedures (or functions) in one case, and grouped code associated with some internal state in the other. Data-oriented design shifts the perspective of programming from objects to the data itself: The type of the data, how it is laid out in memory, and how it will be read and processed in the game.

Programming, by definition, is about transforming data: Itâ€™s the act of creating a sequence of machine instructions describing how to process the input data and create some specific output data. A game is nothing more than a program that works at interactive rates, so wouldnâ€™t it make sense for us to concentrate primarily on that data instead of on the code that manipulates it?

Iâ€™d like to clear up potential confusion and stress that data-oriented design does not imply that something is data- driven. A data-driven game is usually a game that exposes a large amount of functionality outside of code and lets the data determine the behavior of the game. That is an orthogonal concept to data-oriented design, and can be used with any type of programming approach.

Ideal Data

If we look at a program from the data point of view, what does the ideal data look like? It depends on the data and how itâ€™s used. In general, the ideal data is in a format that we can use with the least amount of effort. In the best case, the format will be the same we expect as an output, so the processing is limited to just copying that data. Very often, our ideal data layout will be large blocks of contiguous, homogeneous data that we can process sequentially. In any case, the goal is to minimize the amount of transformations, and whenever possible, you should bake your data into this ideal format offline, during your asset-building process.

Because data-oriented design puts data first and foremost, we can architect our whole program around the ideal data format. We wonâ€™t always be able to make it exactly ideal (the same way that code is hardly ever by-the-book OOP), but itâ€™s the primary goal to keep in mind. Once we achieve that, most of the problems I mentioned at the beginning of the column tend to melt away (more about that in the next section).

When we think about objects, we immediately think of treesâ€" inheritance trees, containment trees, or message-passing trees, and our data is naturally arranged that way. As a result, when we perform an operation on an object, it will usually result in that object in turn accessing other objects further down in the tree. Iterating over a set of objects performing the same operation generates cascading, totally different operations at each object (see Figure 1a).

To achieve the best possible data layout, itâ€™s helpful to break down each object into the different components, and group components of the same type together in memory, regardless of what object they came from. This organization results in large blocks of homogeneous data, which allow us to process the data sequentially (see Figure 1b). A key reason why data-oriented design is so powerful is because it works very well on large groups of objects. OOP, by definition, works on a single object. Step back for a minute and think of the last game you worked on: How many places in the code did you have only one of something? One enemy? One vehicle? One pathfinding node? One bullet? One particle? Never! Where thereâ€™s one, there are many. OOP ignores that and deals with each object in isolation. Instead, we can make things easy for us and for the hardware and organize our data to deal with the common case of having many items of the same type.

Does this sound like a strange approach? Guess what? Youâ€™re probably already doing this in some parts of your code: The particle system! Data-oriented design is turning our whole codebase into a gigantic particle system. Perhaps a name for this approach that would be more familiar to game programmers would have been particle-driven programming.

Advantages of Data-Oriented Design

hinking about data first and architecting the program based on that brings along lots of advantages.

Parallelization.

These days, thereâ€™s no way around the fact that we need to deal with multiple cores. Anyone who has tried taking some OOP code and parallelizing it can attest how difficult, error prone, and possibly not very efficient that is. Often you end up adding lots of synchronization primitives to prevent concurrent access to data from multiple threads, and usually a lot of the threads end up idling for quite a while waiting for other threads to complete. As a result, the performance improvement can be quite underwhelming.

When we apply data-oriented design, parallelization becomes a lot simpler: We have the input data, a small function to process it, and some output data. We can easily take something like that and split it among multiple threads with minimal synchronization between them. We can even take it further and run that code on processors with local memory (like the SPUs on the Cell processor) without having to do anything differently.

Cache utilization.

In addition to using multiple cores, one of the keys to achieving great performance in modern hardware, with its deep instruction pipelines and slow memory systems with multiple levels of caches, is having cache-friendly memory access. Data-oriented design results in very efficient use of the instruction cache because the same code is executed over and over. Also, if we lay out the data in large, contiguous blocks, we can process the data sequentially, getting nearly perfect data cache usage and great performance. Possible optimizations. When we think of objects or functions, we tend to get stuck optimizing at the function or even the algorithm level; Reordering some function calls, changing the sort method, or even re-writing some C code with assembly.

That kind of optimization is certainly beneficial, but by thinking about the data first we can step further back and make larger, more important optimizations. Remember that all a game does is transform some data (assets, inputs, state) into some other data (graphics commands, new game states). By keeping in mind that flow of data, we can make higher-level, more intelligent decisions based on how the data is transformed, and how it is used. That kind of optimization can be extremely difficult and time- consuming to implement with more traditional OOP methods.

Modularity.

So far, all the advantages of data-oriented design have been based around performance: cache utilization, optimizations, and parallelization. There is no doubt that as game programmers, performance is an extremely important goal for us. There is often a conflict between techniques that improve performance and techniques that help readability and ease of development. For example, re-writing some code in assembly language can result in a performance boost, but usually makes the code harder to read and maintain.

Fortunately, data-oriented design is beneficial to both performance and ease of development. When you write code specifically to transform data, you end up with small functions, with very few dependencies on other parts of the code. The codebase ends up being very â€œflat,â€ with lots of leaf functions without many dependencies. This level of modularity and lack of dependences makes understanding, replacing, and updating the code much easier.

Testing.

The last major advantage of data-oriented design is ease of testing. As we saw in the June and August Inner Product columns, writing unit tests to check object interactions is not trivial. You need to set up mocks and test things indirectly. Frankly, itâ€™s a bit of a pain. On the other hand, when dealing directly with data, it couldnâ€™t be easier to write unit tests: Create some input data, call the transform function, and check that the output data is what we expect. Thereâ€™s nothing else to it. This is actually a huge advantage and makes code extremely easy to test, whether youâ€™re doing test-driven development or just writing unit tests after the code.

Drawbacks of Data-Oriented Design

Data-oriented design is not the silver bullet to all the problems in game development. It does help tremendously writing high-performance code and making programs more readable and easier to maintain, but it does come with a few drawbacks of its own.

The main problem with data-oriented design is that itâ€™s different from what most programmers are used to or learned in school. It requires turning our mental model of the program ninety degrees and changing how we think about it. It takes some practice before it becomes second-nature.

Also, because itâ€™s a different approach, it can be challenging to interface with existing code, written in a more OOP or procedural way. Itâ€™s hard to write a single function in isolation, but as long as you can apply data-oriented design to a whole subsystem you should be able to reap a lot of the benefits.

Applying Data-Oriented Design

Enough of the theory and overview. How do you actually get started with data-oriented design? To start with, just pick a specific area in your code: navigation, animations, collisions, or something else. Later on, when most of your game engine is centered around the data, you can worry about data flow all the way from the start of a frame until the end.

The next step is to clearly identify the data inputs required by the system, and what kind of data it needs to generate. Itâ€™s OK to think about it in OOP terms for now, just to help us identify the data. For example, in an animation system, some of the input data is skeletons, base poses, animation data, and current state. The result is not â€œthe code plays animations,â€ but the data generated by the animations that are currently playing. In this case, our outputs would be a new set of poses and an updated state.

Itâ€™s important to take a step further and classify the input data based on how it is used. Is it read- only, read-write, or write-only? That classification will help guide design decisions about where to store it, and when to process it depending on dependencies with other parts of the program.

At this point, stop thinking of the data required for a single operation, and think in terms of applying it to dozens or hundreds of entries. We no longer have one skeleton, one base pose, and a current state, and instead we have a block of each of those types with many instances in each of the blocks.

Think very carefully how the data is used during the transformation process from input to output. You might realize that you need to scan a particular field in a structure to perform a pass on the data, and then you need to use the results to do another pass. In that case, it might make more sense to split that initial field into a separate block of memory that can be processed independently, allowing for better cache utilization and potential parallelization. Or maybe you need to vectorize some part of the code, which requires fetching data from different locations to put it in the same vector register. In that case, that data can be stored contiguously so vector operations can be applied directly, without any extra transformations.

Now you should have a very good understanding of your data. Writing the code to transform it is going to be much simpler. Itâ€™s like writing code by filling in the blanks. Youâ€™ll even be pleasantly surprised to realize that the code is much simpler and smaller than you thought in the first place, compared to what the equivalent OOP code would have been.

If you think back about most of the topics weâ€™ve covered in this column over the last year, youâ€™ll see that they were all leading toward this type of design. Now itâ€™s the time to be careful about how the data is aligned (Dec 2008 and Jan 2009), to bake data directly into an input format that you can use efficiently (Oct and Nov 2008), or to use non- pointer references between data blocks so they can be easily relocated (Sept 2009).

Is Thre Room For OOP?

Does this mean that OOP is useless and you should never apply it in your programs? Iâ€™m not quite ready to say that. Thinking in terms of objects is not detrimental when there is only one of each object (a graphics device, a log manager, etc) although in that case you might as well write it with simpler C-style functions and file-level static data. Even in that situation, itâ€™s still important that those objects are designed around transforming data.

Another situation where I still find myself using OOP is GUI systems. Maybe itâ€™s because youâ€™re working with a system that is already designed in an object-oriented way, or maybe itâ€™s because performance and complexity are not crucial factors with GUI code. In any case, I much prefer GUI APIs that are light on inheritance and use containment as much as possible (Cocoa and CocoaTouch are good examples of this). Itâ€™s very possible that a data-oriented GUI system could be written for games that would be a pleasure to work with, but I havenâ€™t seen one yet.

Finally, thereâ€™s nothing stopping you from still having a mental picture of objects if thatâ€™s the way you like to think about the game. Itâ€™s just that the enemy entity wonâ€™t be all in the same physical location in memory. Instead, it will be split up into smaller subcomponents, each one forming part of a larger data table of similar components.

Data-oriented design is a bit of a departure from traditional programming approaches, but by always thinking about the data and how it needs to be transformed, youâ€™ll be able to reap huge benefits both in terms of performance and ease of development.

Thanks to Mike Acton and Jim Tilander for challenging my ideas over the years and for their feedback on this article.

It's All About Data

Ideal Data

Call sequence with an object-oriented approach

Figure 1a. Call sequence with an object-oriented approach

Call sequence with a data-oriented approach

Figure 1b. Call sequence with a data-oriented approach

Advantages of Data-Oriented Design

Thinking about data first and architecting the program based on that brings along lots of advantages.