Data Oriented Design

[Ragora]

Data oriented design is something that is probably worthwhile implementing into just about any game engine, however, it requires a bit of a flipped perspective on how to set up your data. At the very least, you need to group related sets of data together into structures -- or even more preferably, into contiguous arrays for rapid successive access due to making the most efficient use of CPU cache lines. Mike Acton, Engine director at Insomniac Games spoke about it more in-depth in an hour long speech at CPPCon and outlined why generally the OOP design paradigm is harmful to everyone. There is also this discussion on StackOverflow that talks about it more in-depth than I will in this issue text.

Point being, you're going a lot of the same operations on a large set of data, so why not make it easier for your CPU to do that?

[Phantom139]

Very interesting read. And it does make a load of sense to handle things in the DoD paradigm instead of a standard OOP method

If I'm understanding it correctly, we could do a setup like this (Example, Not guaranteed names):

GlobalObjectManager (Stores a Vector/Array of all object manager instances)
-> ObjectManager (Stores a Vector/Array of all object instances of x type)
-> Object (The Object Itself)

Each engine tick would result in GlobalObjectManager running an .update() code, which in turn does the same for ObjectManager. The difference would instead be at the Manager/Object classes where the Object class only stores a list of the fields that need to be updated, and the Manager runs through each object to update all of those fields at once.

From a perspective of processing requirements, it makes much more sense to have one function update all of the object instances at once instead of processing each object, practically I'll have to see how it works when I get to RC2 and start working on an exampleGame.

[Ragora]

It would mostly be stuff like structs of arrays of elements often used together in computations. If all the arrays are X size (a lot of preallocated memory -- remember what Mike Acton said?) then a single loop could blow through from 0 to X doing whatever operations are necessary at each collection with use of inlined code. This also eliminates use of vtables at your main update since you would be calling the necessary code directly. You could optimize "index misses" (no entry at some index) by using a stack to keep track of ID's that were previously used for some objects but were deleted, so pop off a recycled index and use that for the next object. Otherwise, just increment your global counter by one and use that as an index. Multiple loops may be necessary since you're not really guaranteed to have nearly the same counts of object types, but the code path is still fairly straight-forward for a computer to deal with.

You would have to start by figuring what sets of data are common to everything in your hierarchy. You likely won't have to go so far to apply this to GUI coding. Say... I can safely say that Position, Rotation, Velocity, Scale and various other basic data like that is common across all game object types and Position & Velocity is most likely to be used together more often than the rest, so you'll pretty much have a struct of an array of positions (hell, maybe even straight floats) and an array velocities indexed by object ID or something. As far as the straight floats I mean something like:

   struct GlobalProperties
   {
      float mPosition[MAX_OBJECT_COUNT * 3];
      float mVelocity[MAX_OBJECT_COUNT * 3];
   };

   GlobalProperties* properties = new GlobalProperties; // Done once at engine init

   // With this being set, we just work out respective object positions and velocities from ID by multiplying ID by 3 to work out data start, and once that result is returned, you could just store
the result index somewhere if possible
   // 0 = 0 * 3 = 0
   // 1 = 1 * 3 = 3
   // 2 = 2 * 3 = 6
   for (unsigned int index = 0; index < MAX_OBJECT_COUNT * 3; index += 3)
   {
       // Compiler will probably work out that index, index + 1 and index + 2 are all the same values at
       // both position and velocity
       float& pX = properties->mPosition[index];
       float& pY = properties->mPosition[index + 1];
       float& PZ = properties->mPosition[index +  2];

       float& vX = properties->mVelocity[index];
       float& vY = properties->mVelocity[index + 1];
       float& vZ = properties->mvelocity[index + 2];

       // Do some calculations that involve positions and velocities
       // And this same loop could be used across all globally shared properties, just with inlined code
       // for each operation.
   }
  // All this data is guaranteed to be sequential in memory and therefore more cache friendly.
  // The issue with other paradigms by what Mike Acton is saying is that you have elements
  // placed randomly about the heap and you are accessing them in unpredictable fashions, so
  // the CPU is going to have a little bit of an issue dealing with code like that. You are also 
  // complicating the call structure by requiring use of vtables (virtual methods) which makes the CPU lookup
 // where to jump instead of the code simply being hardcoded to jump somewhere.

The above setup also means you'll have to work out some means of applying different sets
of logic to the same data without really randomly accessing the data. It's a pretty complex beast to try and use.

Though, the issue comes to mind whether or not DoD would be worth it: It's a paradigm oriented around the flow of data and it pretty much disregards how Humans tend to think about data because computers think much, much differently than we do. This being said, it would be a more difficult paradigm to implement and it may not be necessary unless you're going to be developing software with as such high-performance needs as their game engine. However, I would figure this would allow the code to run exceedingly well on mobile and other lower power devices.

[Phantom139]

It's definitely something I'll have to consider when I get through the EngineCore module (Cross Platform Code). I may actually end up trying an example of each and running some comparison tests to see exactly how much of a difference it would make on large scale cases (High object instances with each object needing certain actions).

[Ragora]

I would setup a test so that you're required to use vtables (a generic class of some sort of a handful of children classes) where the primary program loop just blows over the generic list and calls an update which performs some logic within the virtual method. Should make the logic fairly complicated, then implement the same sort of thing using strictly sequential arrays of raw data and direct (non-virtual) inlined method calls. Run both with 1000 or more instances, you'll probably notice a significant improvement with less cache misses, especially on mobile devices.