next »

[lansing]

Data-oriented design in game programming
http://gamedeveloper.texterity.com/gamedeveloper/200909/?folio=43#pg45

[Glaiel-Gamer]

I don't see how any of that is c++ bashing

Especially considering c++ can be used to implement data-oriented engines.

[mcc]

Yeah... I dunno.

There's clearly some really good advice in here and I appreciate the thought about planning for vectorization but...

The article seems to be framed in a funny way. Like I found the dichonomy he sets up between data driven / object oriented programming a bit weird. It seems like the sorts of designs he describes have their place, and so do OO designs. In particular the nice thing about OO of any form is that it tends to make rapid prototyping very easy-- the "data-driven" designs he's describing seem to me like they'd be of the type that would work best if you know everything about your architecture and you're reasonably certain it's not going to change. I feel like I'd be more likely to rewrite parts of a program in this fashion toward the end of a project when optimizing, and less likely to either start out thinking that way or somehow try to form a whole-program design around it. The article though (aside from a little "well, I guess OO is okay for GUIs" at the end) seems to be suggesting that you somehow need to make a choice, or that OO is something you should avoid if you want to do data-driven programming later. Maybe the three pages he had to work with just didn't have room for a more nuanced view, but still I'd hesitate about showing this article to a beginning programmer lest they take its advice a little too literally over the much more important axiom that "premature optimization is the root of all evil"...

Also... maybe this is just me being ignorant but really, how often is poor cache usage the primary bottleneck in a design? It seems like in order to get to the point where cache is a noticeable limiting factor you'll have to have basically optimized everything else first to an insane degree. And can you even test for / benchmark that sort of thing? Won't most every system your game runs on behave differently w/r/t cache?

[lansing]

Profiling cache misses:
AMD: http://developer.amd.com/cpu/CodeAnalyst/Pages/default.aspx
Intel has VTune for the same purpose.

[Average Software]

Geez, what a sensationalist title.  I didn't even see C++ mentioned in the article.  Why in the world do you think this is C++ bashing?

That said, I do like reading things like this, because I'm going through a sort of cultural backlash against object-oriented programming right now.  I'm just getting sick and tired of it, largely because of the legions of mindless OOP-tards (my term) that have largely been spawned by Java and C#.

It seems like the real gist of the article is the notion of centralization.  One of the common criticisms of OOP is that things are too spread out, both in the code sense and in the memory sense.  OOP (especially "Java" style) tends to encourage having masses of pointers to data "somewhere else" which has the effect of scattering your data like buckshot through your RAM.  This can make rapid processing very difficult.

In the code sense, OOP decentralizes the descriptions of objects.  You can't know everything about an object by looking at its class definition.  You have to go look at its parents, and their parents, and their parents, and so on.  The article seems to be about peeling off some of these mental and physical abstractions and just saying, "Here's the data, let's work with it."

[raigan]

Maybe I'm just brainwashed by OOP, but I've had a hard time trying to figure out how to apply this sort of idea to the majority of use cases in our code, which is "a bunch of different objects which support a given interface".

In such cases, the behaviour is uniform, but the data is mixed.

For instance, all PhysicsJoint objects have a Solve() function, but each has unique internal data: pin joints are described by a local position on each body, distance joints have an added distance parameter on top of that, directed distance joints have an axis direction on top of that, and the data for angle joints is completely dissimilar to the others.

Probably I'm just confused in my approach..

[Triplefox]

I've been practicing more and more data-oriented design in my own code to good effect. The article's author speaks from a bit-bashing viewpoint of building features so that they have good performance characteristics from the outset. I'm interested more from the "minimize source code size and bugs, maximize functionality" viewpoint, but there is something shared in our ideas.

I think the comparison between OO/data-oriented comes down to:

In an OO-heavy design you set up silos of behavior and massage their relationships until they play well.

In a data-oriented design you implement powerful data structures that inherently manage the relationships for you. Then you can build around the data structure with a very small amount of logic to support each feature. 


One particular structure I came up with recently is similar in nature to tables in a relational database: it allows any number of ordered, searchable indexes for a set of integer values. Each value is related to a single property list. (I've gone back and forth between single and multiple lists - multiple is much more complex and I haven't found a use case yet) Indexes may use the actual stored value or a "repr function's" value to turn, e.g., an entity's centerpoint into boundaries for a collision rect. My use case is in actor-to-actor collision though I imagine that others may come up.

Because I can use any number of indexes, I can set up nicely optimized custom queries for various collision behaviors: player vs. enemy shots, player vs. pickups, etc. So a detection rule becomes "search the pickup x index for a range between the player's left and right bounds, and then filter that by y values between the player's top and bottom bounds".

When I update a value, all the indexes are automatically updated. Likewise, when I delete a value, it removes the related property lists and their values.

Net result: Massive amounts of state manipulation have just disappeared, contingent on these structures doing their job(being complex, they're downright scary to test, but I only have to get it right once). Optimization can be driven around considerations of how many indexes and their size, rather than a difficult case-by-case analysis that starts with "oh, the objects are laid out in this tangle." Layering on new features involves less poking at the existing ones.

The main downside is that values in this particular structure take up more memory to store all these explicit relationships. But that's an acceptable tradeoff for getting them out of the logic.

[bateleur]

I tend to look at this issue this way: data-oriented design favours data flow much as functional programming favours control flow.

So just as I want to use some functional programming ideas without necessarily writing in a functional language, similarly I want to use some data-oriented design ideas without building my whole program that way.

(Aside: I tend to see C++ as great for this kind of thing, since it's one of the few OO languages which doesn't allocate thousands of objects all the time even when you don't want it to.)

[mcc]

Profiling cache misses:
AMD: http://developer.amd.com/cpu/CodeAnalyst/Pages/default.aspx
Intel has VTune for the same purpose.

If you do cache profiling with AMD's Code Analyst, or Intel's VTune (or I guess Apple's Instruments?), does this give you information that more or less accurately applies to how cache would perform on a chip different from the model or manufacturer of the chip you performed the testing on?

[Klaim]

This (highly technical and a bit long) discussion might be a good read about the current subject : http://www.ogre3d.org/forums/viewtopic.php?f=1&t=52818

[LemonScented]

I can't help but feel that this is a solution in search of a problem. I don't think I've ever worked on a game in which the performance is poor because of memory access patterns and cache misses rather than just suboptimal code which can be picked up by a profiler and improve on. Okay, I worked on one game that had those problems, but frankly that was caused by some blisteringly stupid architectural decisions.

Yes, particle systems and rendering stuff like vertex arrays and display lists can benefit from this sort of approach, but frankly any engine programmer worth his salt knows to write those parts of the game in that manner anyway. Extending this approach to work across an entire game seems pretty heavy-handed to me.

[Klaim]

Actually, that's the design described by xavier, not the first post that's intersesting in this discussion.

About cache miss, did you ever work on console games with heavy cpu bound calculations?

[LemonScented]

About cache miss, did you ever work on console games with heavy cpu bound calculations?

Yep. A few, in fact. I'm not saying that cache misses aren't something you should take into consideration (they can and do add up), but in my experience if cache misses are the single biggest problem in your game performance, and exist across all areas of the codebase (rather than bottlenecks in specific subsystems), then the chances are you have a retarded engine architect. Compared to all of the other performance problems that can arise, this seems (in my experience) far less common than the article author wants you to believe. Certainly not common enough to warrant a whole new paradigm for code design. The parts of a game which do well under data-oriented design tend to be written that way already, but for the bulk of the code (particularly the higher-level stuff), the performance overheads for OOP are a very reasonable price to pay for maintainable, readable code.

Your mileage may vary, of course. I just kind of got put off by the introduction of "don't you hate this problem you get on every project?" when really, I don't, even when pushing limited hardware as far as it can go. There are always much bigger fish to fry than this.

[David Pittman]

Noel also wrote C++ for Game Programmers, so... No. Not C++ bashing. Just like you can use C-style functions in C++, you can write in an object-oriented fashion in C. It's not about the language, it's about the architecture.

And he cites Mike Acton, which reminded me of this. Making the same point, no less.

For instance, all PhysicsJoint objects have a Solve() function, but each has unique internal data: pin joints are described by a local position on each body, distance joints have an added distance parameter on top of that, directed distance joints have an axis direction on top of that, and the data for angle joints is completely dissimilar to the others.

So solve all the pin joints together in one batch, then all the distance joints, and so forth. And they'd better all be in contiguous memory. (I mean, why wouldn't they be?) Personally, I find that method of coding maddening, but it is provably more efficient, and when you're trying to ship a AAA game at 60 Hz, that matters. (But maybe shipping at 60 doesn't matter all that much.)

[Robotacon]

I call bulls**t!

No, seriously, I'm having a hard time understanding the concepts here so please correct me if I'm wrong. The idea is to have a set of singletons, that takes care of different parts of the game, looping over different data in the system?

If you want to keep your OOP approach can't you let each game object have a pointer and an index into a singleton managing the part of the system that you want to improve performance on?

That way you can write object oriented AI chains as well as applying generic physics calculations over the same set of data handled by the physics singleton.

[mewse]

(But maybe shipping at 60 doesn't matter all that much.)

My informal testing suggests that virtually nobody except for graphics programmers can tell the difference between a stable 30fps and a stable 60fps, without seeing one immediately after the other.

This fact intensely annoys several graphics programmers I know.   


In terms of the article, it sounds basically like component-based programming, to me.  Localising data across object instances according to function and batch-processing it, instead of bundling things together into monolithic "objects" which encapsulate all functionality for a particular instance.  There are plenty of situations where that's a smart thing to do, but I certainly wouldn't advocate using it everywhere.

[Klaim]

About cache miss, did you ever work on console games with heavy cpu bound calculations?

Yep. A few, in fact. I'm not saying that cache misses aren't something you should take into consideration (they can and do add up), but in my experience if cache misses are the single biggest problem in your game performance, and exist across all areas of the codebase (rather than bottlenecks in specific subsystems), then the chances are you have a retarded engine architect. Compared to all of the other performance problems that can arise, this seems (in my experience) far less common than the article author wants you to believe. Certainly not common enough to warrant a whole new paradigm for code design. The parts of a game which do well under data-oriented design tend to be written that way already, but for the bulk of the code (particularly the higher-level stuff), the performance overheads for OOP are a very reasonable price to pay for maintainable, readable code.

Your mileage may vary, of course. I just kind of got put off by the introduction of "don't you hate this problem you get on every project?" when really, I don't, even when pushing limited hardware as far as it can go. There are always much bigger fish to fry than this.

I worked too on console (NDS) games and never got to watch for cache miss either. The only time I got asked about that was for an interview in a Ubisoft studio. I've rad a lot about it on gamasutra. But I'm not yet sure when it's necessary to watch for it, like you it seems.

I think maybe it's only when you see performance problems that are cpu bound that you need to profile your game and then see if cache misses are a big problem in your case.

Robotacon> The real best idea is to organize your data in data set that will be processed by Tasks. Each task is a process that have to be executed to manipulate one or more specific data set that are in a specific state. Now, Tasks are executed automatically when a Thread (called worker thread) is free and the data required for the Task are in the required state. Then the worker thread will execute the task.

That way, there is no lock/mutex (or very minimal) and your application/game goes as fast as it can, getting faster with more cpu units.

Now that's what I know, what is described in the link I gave but I didn't read yet the first link( lack of time at the moment).
Hope it helps understand how to architect your future game engine.

[raigan]

So solve all the pin joints together in one batch, then all the distance joints, and so forth. And they'd better all be in contiguous memory.

Ah.. okay, that makes sense, thanks!

This doesn't really seem that hard to retro-fit, it's simply moving the functions/methods out of the child objects and into the parent, leaving the children as POD.

[powly]

(But maybe shipping at 60 doesn't matter all that much.)

My informal testing suggests that virtually nobody except for graphics programmers can tell the difference between a stable 30fps and a stable 60fps, without seeing one immediately after the other.

This fact intensely annoys several graphics programmers I know.   

I've always programmed mostly graphics, and I'd say I could tell 60 fps and 50 fps apart quite easily. And (to me) the 50fps is very much unplayable, mostly because if a game doesn't run at its maximum framerate, fps tends to wobble a little, which is intolerable. If they were both solid (completely stable) it would be hard but I guess I could see it, also then it wouldn't ruin the gameplay. (Vice City had this kind of limitation for around 30FPS as a default, if my memory serves me correctly and it was quite playable)

I think I'll write a test application to see how good my eye for FPS is :3

[mewse]

I've always programmed mostly graphics, and I'd say I could tell 60 fps and 50 fps apart quite easily. And (to me) the 50fps is very much unplayable, mostly because if a game doesn't run at its maximum framerate, fps tends to wobble a little, which is intolerable.

You've picked an awkward number for your example.    50fps can be a stable, maintained frame rate in traditional PAL resolutions.

My tests showed that when non-graphics-programmers were shown a game running at a stable 30fps (that is, never varying up or down from 30fps), they identified it as 60fps, and when they were shown a game running at an unstable 60fps (randomly dropping a single frame once per second, so actually running at 59fps), they identified it as running at 30fps.

My conjecture is that their mental logic for these two situations ran along these lines:  "This is updating smoothly, 60fps is smooth, therefore this must be 60fps", and "I can see this juddering sometimes.  It's not smooth the way that I remember 60fps games being, so it must be running at 30fps", respectively.

Worth mentioning that I didn't have enough people taking my test to really prove that these results are universal.  But they're still interesting results, and seem to match well with informal observations that others have made.   And yeah, experienced graphics programmers could always identify frame rate well enough to distinguish between 30fps and 60fps.  And anyone else could too, if shown both.  It was only when someone viewed just one or the other that they couldn't correctly identify its frame rate.