Adventures in data-oriented design - Part 1: Mesh data

Let’s face it, performance on modern processors (be it PCs, consoles or mobiles) is mostly governed by memory access patterns. Still, data-oriented design is considered something new and novel, and only slowly creeps into programmers’ brains, and this really needs to change. Having co-workers fix your code and improving its performance really is no excuse for writing crappy code (from a performance point-of-view) in the first place.

This post is the first in an ongoing series about how certain things in the Molecule Engine are done in a data-oriented fashion, while still making use of OOP concepts. A common misconception about data-oriented design is that it is “C-like”, and “not OOP”, and therefore less maintainable – but that need not be the case. The concrete example we are going to look at today is how to organize your mesh data, but let’s start with the pre-requisites first.

Data-oriented design

Much has been said and written about data-oriented design already, and there’s some nice resources on the web. Mike Acton (Technical Director at Insomniac Games) is a well-known advocate of data-oriented design, and has some interesting slides on the web as well.

I will not go into detail about data-oriented design in general, so let me quickly sum up what for me data-oriented design is all about:

1. Think about data first, and code second. Class hierarchies aren’t important, but data access patterns are.
2. Think about how data in your game is accessed, how it is transformed, and what you end up doing with it, e.g. particles, skinned characters, rigid bodies, and tons of other examples.
3. When there’s one, there’s many. Think in streams of data.
4. Be aware of the overhead of virtual functions, pointers to functions, and pointers to member functions.

Just to make everybody aware of the importance of point 1 and point 2, consider a very simple example:

char* data = pointerToSomeData;
unsigned int sum = 0;
for (unsigned int i=0; i<1000000; ++i, ++data)
{
  sum += *data;
}

In the above example, we take the sum of a million bytes, nothing more. No fancy tricks here, no hidden C++ costs. On my PC this loop takes about 0.7ms.

Let’s slightly alter the loop, and measure its performance again:

char* data = pointerToSomeData;
unsigned int sum = 0;
for (unsigned int i=0; i<1000000; ++i, data += 16)
{
  sum += *data;
}

The only thing that has changed is that we are summing every 16th element now, that is we have changed ++data to data += 16. Note that we still take the sum of exactly 1 million elements, only different elements this time!

The time this loop took? 5ms. Let me spell that out for you: This loop is more than 7 times slower than the original, eventhough we’re accessing the same amount of elements. Performance is all about memory access, and how to make good use of your processor’s caches.

Remember point 3, “When there’s one, there’s many. Think in streams of data.”? What does this mean? It’s simple: if you have one texture, mesh, sound sample, rigid body, etc. in your game, you’re going to have many of them. Write your code in a way that it can deal with many of them at once – think in terms of streams of objects. That doesn’t mean that you need to get rid of your Mesh and Texture classes, and turn them into a MeshList and TextureList, respectively. This will be dealt with in our later example.

Last but not least, point 4: “Be aware of the overhead of virtual functions, pointers to functions, and pointers to member functions.” is something that is very close to my heart. It is something often ignored (or forgotten about) by less experienced programmers, and I always make sure to teach my students the underlying costs of virtual function calls and the likes. Still, sooner or later they will end up being used in an inner loop, and will kill your performance.

To state it bluntly, you should never use a virtual function, a pointer-to-function, or a pointer-to-member-function on a per-object basis – not for each primitive group of a mesh, not for each particle in your particle system, not for each texel in a texture; you get the idea. They will likely cause both instruction and data cache misses, and kill your performance – be aware of it!

Dealing with static mesh data in a data-oriented way

Having said that, let’s start with today’s example of how to deal with static mesh data in a data-oriented way. There’s certainly many ways in which you can organize your data, so what we’re interested in is the difference in performance between a completely object-oriented design, and a design more concerned about data access patterns.

The scenario of our example is the following:

• We want to render 500 static meshes, and perform view-frustum culling on them.
• Each mesh has a vertex buffer, index buffer, and about 3 sub-meshes on average.
• Each sub-mesh stores a starting index and the number of indices used in the vertex buffer/index buffer of the mesh it belongs to. Additionally, each sub-mesh has a material and an axis-aligned bounding-box.
• A material contains a diffuse texture, and a light map.

Certainly nothing extremely complicated, which makes it easier to see the difference between the two approaches.

The by-the-book OOP approach

Let’s start with the class design of the object-oriented approach:

class ICullable
{
public:
  virtual bool Cull(Frustum* frustum) = 0;
};

class SubMesh : public ICullable
{
public:
  virtual bool Cull(Frustum* frustum)
  {
    m_isVisible = frustum->IsVisible(aabb);
  }

  void Render(void)
  {
    if (m_isVisible)
    {
      m_material->Bind();
      context->Draw(m_startIndex, m_numIndices);
    }
  }

private:
  unsigned int m_startIndex;
  unsigned int m_numIndices;
  Material* m_material;
  AABB m_boundingBox;
  bool m_isVisible;
};

class IRenderable
{
public:
  virtual void Render(void) = 0;
};

class Mesh : public IRenderable
{
public:
  virtual void Render(void)
  {
    context->Bind(m_vertexBuffer);
    context->Bind(m_indexBuffer);

    for (size_t i=0; i<m_subMeshes.size(); ++i)
    {
      m_subMeshes[i]->Render();
    }
  }

private:
  VertexBuffer* m_vertexBuffer;
  IndexBuffer* m_indexBuffer;
  std::vector<SubMesh*> m_subMeshes;
};

Hopefully, some of you will already cry at the sight of such a design. One might think that the above is an exaggeration of OOP design gone wild, but let me assure you that I’ve seen far worse in shipped games. The contender for the worst example was something along the lines of the following:

class GameObject : public IPositionable, public IRenderable, public IScriptable, ...

I cannot remember the exact details, but the actual implementation inherited from 6 or 7 classes, some of them having implementations, others just having pure virtual functions, others having virtual functions for the sole purpose of making dynamic_casts work on them… I don’t want to point fingers, but rather reinstate that such designs can be found in shipped, commercial games and are not made-up examples – but let’s not digress.

Back to the original example, what is so bad about it? Well, there’s several things:

1. The two interfaces IRenderable and ICullable cause a virtual function call hit on each call to Render() and Cull(), respectively. Furthermore, virtual functions almost never can be inlined, further deteriorating performance.
2. Bad memory access patterns when culling meshes. In order to read the AABB, a whole cache line (64 bytes on modern architectures) will be read into the processor’s cache, whether you need it or not. This boils down to accessing more data than necessary, which is bad for performance, as could be seen in our very first simple example (summing 1 million bytes).
3. Bad memory access patterns when rendering sub-meshes. Each sub-mesh checks its own m_isVisible flag, which again will pull more data into the cache than necessary. Same bad behaviour as in the example above.
4. Bad memory access patterns in general. Points 3 and 4 above assume that all the meshes’ and sub-meshes’ data is linearly laid out in memory. In practice, this is seldom the case, because programmers often just slam a new/delete in there, and be done with it.
5. Bad memory access patterns for future algorithms. As an example, in order to render geometry into a shadow-map, no materials need to be bound, only the start index and number of indices are needed. But each time we access them, we pull the other data into the cache as well.
6. Bad threadability. How would you perform the culling process of several sub-meshes on different CPUs? How would you perform the culling on SPUs?

So how can this situation be improved? How can we organize our data so that it offers good performance now and in the future?

The data-oriented design approach

The obvious things to get rid of are the two interfaces, and the virtual function calls associated with them. Believe me, you don’t need those interfaces.

The other thing we can change is to make sure that data that needs to be accessed together actually is allocated next to each other in memory. Furthermore, it would be nice if this was somehow done implicitly, without the programmer having to worry about memory allocations that much.

Going down the DOD route, such a design could look like this:

struct SubMesh
{
  unsigned int startVertex;
  unsigned int numIndices;
};

class Frustum
{
public:
  void Cull(const float* in_aabbs, unsigned bool* out_visible, unsigned int numAABBs)
  {
    // for each AABB in in_aabbs:
    // - determine visibility
    // - store visibility in out_visible
  }
};

class Mesh
{
public:
  void Cull(Frustum* frustum)
  {
    frustum->Cull(&m_boundingBoxes[0], &m_visibility[0], m_boundingBoxes.size());
  }

  void Render(void)
  {
    context->Bind(m_vertexBuffer);
    context->Bind(m_indexBuffer);

    for (size_t i=0; i<m_visibleSubMeshes.size(); ++i)
    {
      if (m_visibility[i])
      {
        m_materials[i]->Bind();
        const SubMesh& sm = m_subMeshes[i];
        context->Draw(sm.startIndex, sm.numIndices);
      }
    }
  }

private:
  VertexBuffer* m_vertexBuffer;
  IndexBuffer* m_indexBuffer;

  std::vector<float> m_boundingBoxes;
  std::vector<Material*> m_materials;
  std::vector<SubMesh> m_subMeshes;
  std::vector<bool> m_visibility;
};

Let’s examine this approach’s characteristics:

1. Good memory access patterns when culling sub-meshes. In order to cull N elements, exactly N*6 floats are accessed in memory. Visibility is written to a seperate destination in memory, so no overhead there either.
2. Good memory access patterns when rendering sub-meshes. All the data needed is stored contiguously in memory, and we only load data into the cache which is actually needed.
3. Good memory access patterns for future use. If we want to render sub-meshes into a shadow-map, we only need to access m_subMeshes, nothing more.
4. Good memory access patterns in general. Memory need not be allocated manually in order for the elements to be contiguous. A std::vector always is, and so is a simple array. You can go further and put all your Mesh instances into a seperate container as well, if you want.
5. Easier threadability. If culling (or any other operation, for that matter) needs to be split across multiple threads (or SPUs), we can divide the data into chunks, and feed each chunk of data to different threads. No synchronization, mutexes, or similar needed in those cases, and the solution scales almost perfectly, making it easy to take advantage of 4-core, 8-core or N-core processors, which will be the future of PCs and consoles.

I don’t claim that the presented solution is totally perfect – it certainly isn’t, it just served as an example. Points of improvement from the top of my head:

1. Instead of storing bools into the out_visible array, we could directly store the sub-meshes’ data, saving us both the branch and further indirections when rendering the visible meshes in Mesh::Render().
2. Taking it even further, we can directly store rendering commands into the GPU buffer if we want, e.g. by writing into a command-buffer on the PS3.
3. If your content pipeline supports it, bake all the static data into one single, big Mesh. All the static mesh data for a whole level is then guaranteed to be contiguous in memory, so you can reap the benefits of the above solution automatically.

What performance improvement can we expect to see from such a design change? In the experiments I conducted (500 meshes, 3 sub-meshes each, not counting Direct3D11 API call overhead), the difference between the two presented solutions was about 1.5ms.

If that doesn’t sound like much, consider that 1.5ms actually make up almost 10% of a 60Hz frame. Furthermore, we’re talking about 500 meshes here, and have only touched the design of static mesh data. If data-oriented design is applied throughout the whole engine, the performance benefits can be enormous.

And in case you wondered, of course the data-oriented design won. Let’s end this post by saying that you need to start caring about your data access patterns now, I mean it. So does Scott Meyers.

About these ads