How can I boost cache performance when storing objects in a scene with managed languages?

Question

So, for reasons that I won't go into (has to do with my team more so than a good objective reason, unfortunately), I'm building a soft game engine in C# on top of SharpDX. C++ wasn't an option. I can't store objects contiguously in C# when it comes to reference types like classes, so I'm thinking about taking a data-oriented-design approach to storing objects in my scene. Thus, my scene looks a bit like this right now (all of the fields are structs because I can store them by value type, and thus contiguously):

public delegate void UpdateMethod (ref ModelData md, ref Transform t, ...)

class Scene
{
    ModelData[] models;
    Transform[] transforms;
    //...some other fields here
    UpdateMethod[] updateMethods; //delegate array

    void UpdateAll()
    {
         for (int i = 0; i < NUM_GAME_OBJECTS; i++)
        {
            if (updateMethods[i]!= null)
            {
                updateMethods[i](ref models[i], ref transforms[i], ...);
            }
        }
    }
}

The idea being that I can now store the objects contiguously as opposed to just an array of contiguous references to the data if I made each component a class.

Is this even a viable technique, or am I abusing the DOD paradigm? I'm storing all of my objects like this, not just my dynamic ones. Perhaps I could split it up into two sets of arrays for dynamic and non-dynamic, so I'm not tempting branch-predictor slow-downs on the if statement for UpdateAll()?

Will an approach like this create more issues than it attempts to solve? I will note that, while updating occurs here, I outsource the actual carrying out of the component functionality to other systems. For example, an input subsystem determines keys pressed, so an object could check in its unique update method denoted by the delegate; the update doesn't do everything, just behavior specific to that bundle of game object data.

This seems analogous to operating over columns in a row-major language, in that I'm killing performance gain of data locality; am I correct in concluding it would it be beneficial to wrap all of these fields into some GameObjectData wrapper struct, and just store those in an array?

Answer 1

This is a viable technique in general, but as with any decision it comes with downsides. Most of them are related to ease of use: consider that your example updateMethods call is (probably) wrong, since you're copying models[i] and so on. Updating the instance of ModelData you get inside updateMethods won't change the one in models[]. You'll end up passing around a lot of ref parameters, or passing arrays-and-indexes to refer to individual objects.

It looks to me like you are worrying too much about the theoretical performance implications instead of the practical ones. That is, engage your profiler and determine where and when (or even if) you need to resort to this kind of approach.

It's very possible to make a game that performs well in C# without resorting to making everything a struct in a giant contiguous array so long as you also understand the implications of reference types on the garbage collector and the behavior of the garbage collector. Understanding how-and-when to avoid the garbage collector just as important as understanding how-and-when it's a good optimization to stuff a bunch of structs into a contiguous array (or understanding how-and-when to avoid, or not, allocation of memory in C++).

Also:

Secondly, this seems a lot like operating over columns...

That's true. Since your apparent "update method" takes one instance from each array, you don't actually gain a ton from the contiguous nature of each array, since you're reading from many very distant locations every iteration of the loop.

You don't necessarily need to wrap up everything in one big structure and store an array of those, though; you need to consider which data will benefit the most from being contiguously iterated over and pack that together. It's impractical to make everything perfectly cache coherent in any complex project, so it's a matter of picking and choosing when you get the most bang for your buck and dealing with other cases differently. This is another place where a profiler can help you.

Answer 2

Ordering the data is going to depend on existing data access patterns for your application. Profile first, and see what areas of execution are taking the longest as a result of cache misses.

Once you've done that, interleaved data (array of structs) will almost certainly be better than splitting into massive arrays of a single element type. How you interleave the data is going to depend on your profiling research, and experimentation.

It is possible that in some cases you may want repeat data across different interleaved arrays. For example, while AI processing may fit transform, physics, inventory and character stats data into a cache line, the rendering pipeline may want transform, lighting state, and colour information. That means you may be better off having the transform interleaved into two different arrays, each element of which contains the appropriate goodies as just mentioned. Otherwise memory access is scattered, and cache performance suffers.

As for where your logic sits... it's mostly an illusion. I've worked in pure C for long enough now to see just how irrelevant it is. It is just an organisational tool. You can write a single monolithic class to perform all logic, you can split into subsystems, you can have entities with methods or leave that method logic to a super-controller... what matters is only that you get your flow of control right. I tend to favour an approach of "the next controller up, creates, controls and destroys that which sits below it."