In performance-sensitive applications like games it is crucial to access data in a cache-friendly manner. Especially when dealing with a large number of objects of the same type, e.g. individual components in an entity-component-architecture, we should make sure to read as little data as possible. However, simple arrays-of-structures are often not suited for this, with structures-of-arrays yielding better performance. But the latter are not natively supported by the C++ language.

Array-of-structures (AOS) vs. Structure-of-arrays (SOA)

Before we discuss the inner workings of a possible solution, we need to explain the problem at hand, which can best be illustrated with an example.
Consider the following component:

struct Component
{
  // component data here
  AnyType member0;
  AnyType member1;
  // ...
  bool m_isVisible;
};

For illustration purposes, let us assume that the Component struct has additional members not shown here, so that sizeof(Component) yields 64 bytes. If we want to store an array of such components, we can either use plain arrays, or an std::vector. Both store the data in a so-called array-of-structures (AOS), which means that all instances of Component will be stored next to each other in memory, like so:

components[0] -> [ member0, member1, ..., m_isVisible]
components[1] -> [ member0, member1, ..., m_isVisible]

What does this mean for data accesses? Imagine that we want to render all of those components in one go, but in order to reduce the number of draw-calls submitted to the rendering API, we want to check whether the component is really visible:

for (size_t i=0; i < count; ++i)
{
  if (components[i].m_isVisible)
  {
    // render component here
  }
}

Even though it doesn’t look like it in the C++ code, we are reading a lot of unnecessary data whenever a component is invisible. Every time we access the member components[i].m_isVisible, we pull in the whole cache line that maps to the corresponding address in memory. So even though a component might not be visible, we still access all its data, reading 64 bytes instead of just 1 byte!
If we need to touch all the components’ data because they are all visible anyway, then it doesn’t really matter. But in the average case, we read a lot of unnecessary data.

A simple solution is to store the data using a structure-of-arrays (SOA) approach:

struct Component
{
  // component data here
  AnyType* member0;
  AnyType* member1;
  // ...
  bool* m_isVisible;
};

Note the pointers: instead of storing an array of Components, we store arrays of individual members next to each other. The memory layout of the data then becomes:

member0 -> [ component0, component1, ..., componentN]
member1 -> [ component0, component1, ..., componentN]
m_isVisible -> [ component0, component1, ..., componentN]

The code doesn’t have to change much, we only need to move the array access [i]:

for (size_t i=0; i < count; ++i)
{
  if (components.m_isVisible[i])
  {
    // render component here
  }
}

This simple change ensures that we only read the data we need. When we check components.m_isVisible[i], we also pull in all the boolean values for the other 63 components on that cache line, but none of the other members as long as we don’t touch them in code.

However, in practice it’s not just a simple change like in the code shown above. The surrounding code needs to be changed as well. Memory needs to be allocated differently, members need to be accessed differently, etc.
Which brings us to the topic of this post: what we would like to have is some sort of dynamic array that stores all its elements in SOA-fashion internally, but offers an interface similar to plain arrays or std::vector.

A non-generic first try

To keep things simple enough for this post, we only want to concern ourselves with POD data, and not deal with placement new and manual destructor invocation. You need this in production code as soon as you want to store non-PODs in such a container, but we want to concentrate on the more crucial parts of the code in this post.

For a non-generic, non-templated first stab at an implementation, let us store the following struct in an SOA manner:

struct Item
{
  int m_int;
  float m_float;
};

The most interesting methods we need in our implementation are Add() and Remove(), which are simple in this case because we know the data types we’re dealing with:

class ArraySOA
{
public:
  void Add(const Item& item);
  void RemoveAt(size_t index);

private:
  int* m_data0;
  float* m_data1;

  size_t m_size;
};

void ArraySOA::Add(const Item& item)
{
  m_data0[m_size] = item.m_int;
  m_data1[m_size] = item.m_float;

  ++m_size;
}

void ArraySOA::RemoveAt(size_t index)
{
  const bool isLast = (index+1u == m_size);
  if (!isLast)
  {
    m_data0[index] = m_data0[m_size-1u];
    m_data1[index] = m_data1[m_size-1u];
  }

  --m_size;
}

As I said – POD only, simple implementation.

Adding an item is done by storing the item’s data in the corresponding arrays, and removing an item is done by swapping all members with the last one in the array. This changes the order of items, but keeps the array contiguous (this is different to std::vector).
Let us now increase the difficulty by changing the implementation to deal with structs having an arbitrary number of members. Up until now, we knew that we needed an array of ints and an array of floats. But what if the struct Item has 3 members? Or 4?

It quickly becomes apparent that we cannot store any number of arrays in the way we did. We need a more generic version, and an array of pointers-to-void for storing the start of each individual array fits the bill:

class ArraySOA
{
private:
  void* m_array[MEMBER_COUNT];
  size_t m_size;
};

As long as we only store the pointers to the individual arrays and cast them back to their original type, everything’s fine. Assuming we could simply do that in C++, the code for adding an item would then look like this (pseudo-code-ish):

void ArraySOA::Add(const Item& item)
{
  for (size_t i=0; i < MEMBER_COUNT; ++i)
  {
    OriginalType* data = cast_to_original_type(m_array[i]);
    *data = item.access_member_i;
  }

  ++m_size;
}

There are two fundamental problems:

• How do we cast back to the original type of the array (e.g. int*, float*)?
• How do we access the i-th member of an item without knowing the member’s name?

We can tackle both problems by using templates and template specializations, introducing our own type traits.

Retrieving the original type

In order to be able to retrieve the original type of the array, we can provide a class template that defines an inner type that corresponds to the original type of a member in the struct. The base template can be left empty, and each struct needs to add a specialization for each of its members. In the case of our simple struct Item, this means that we could do the following:

// empty base template
template <typename T, size_t N>
struct GetType;

// template specialization for Item, 0
template <>
struct GetType<Item, 0> { typedef int Type; };

// template specialization for Item, 1
template <>
struct GetType<Item, 1> { typedef float Type; };

This means that the expression GetType<Item, 0>::Type would yield the type int, and GetType<Item, 1>::Type would yield the type float. Before we can put this to use, we need to find a way to access individual members of the Item struct without knowing their name in the for-loop.

Pointers-to-members in C++

In addition to pointers-to-functions and pointers-to-member-functions, in C++ there is also a thing known as pointers-to-members. In simple terms, a pointer-to-member allows you to store a pointer to a data member of a class, and read/write values of any instance of that class through that particular pointer. Regarding the effect it achieves it’s somewhat similar to using offsetof() in C, but a pointer-to-member does this in a type-safe manner. Therefore, always keep in mind that a pointer-to-member is not simply an offset from the start of the class – it could very well be, but in the case of multiple and/or virtual inheritance, such a pointer carries more information (which is defined by the implementation). Hence, it shall never be treated as a simple integer, but needs to be stored and accessed with the proper type.

Using our GetType template introduced above, we can now add a function template that yields the proper pointer-to-member of the Item struct, again specialized for individual members:

template <typename T, size_t N>
struct GetPointerToMemberType
{
  typedef typename GetType<T, N>::Type T::*Type;
};

template <typename T, size_t N>
static typename GetPointerToMemberType<T, N>::Type GetPointerToMember(void);

template <>
static typename GetPointerToMemberType<Item, 0>::Type GetPointerToMember<Item, 0>(void)
{
  return &Item::m_int;
}

template <>
static typename GetPointerToMemberType<Item, 1>::Type GetPointerToMember<Item, 1>(void)
{
  return &Item::m_float;
}

This may seem confusing at first, but bear with me.

The class template GetPointerToMemberType is a helper that makes dealing with the awkward pointer-to-member syntax easier. It simply takes the type defined by the GetType template, and defines an inner type that is a pointer-to-member of that type, in the given class. This means that when GetType<Item, 0>::Type yields type int, GetPointerToMemberType<Item, 0>::Type will yield a pointer-to-int-member for the class Item. Similarly, template arguments <Item, 1> will yield a pointer-to-float-member type.

This in turn allows us to define a function template named GetPointerToMember that returns the proper pointer to an Item‘s member. Again, the function template is specialized for template arguments <Item, 0> and <Item, 1>.

Implementing the loop

Armed with those templates, we can now try to rewrite the for-loop we had in a generic way:

void ArraySOA::Add(const Item& item)
{
  for (size_t i=0; i < MEMBER_COUNT; ++i)
  {
    typedef typename GetType<Item, i>::Type DataType;
    DataType* data = static_cast<DataType*>(m_array[i]);
    data[m_size] = item.*(GetPointerToMember<Item, i>());
  }

  ++m_size;
}

However, we have run into a fundamental problem: we cannot use a runtime variable i as compile-time template argument! We have to come up with some sort of compile-time for-loop which allows us to turn a compile-time expression into any number of function calls, like so:

ForEach<MyFunction, 3>();

should call

MyFunction<0>();
MyFunction<1>();
MyFunction<2>();

Note how a call of the function template ForEach is able to expand into several calls of a given function template, with the counter of the for-loop being passed as non-type template argument. But how do we implement such a ForEach function template? For that, we need a tiny bit of template meta-programming, but nothing too complicated.

A compile-time for-loop

The first thing we need is a function template that accepts an index as template argument, and calls another function template with that index, e.g.:

template <size_t INDEX>
void ForEach(void)
{
  MyFunction();
  ForEach<INDEX+1>();
}

Starting at ForEach<0>(), this would call MyFunction<0>(), MyFunction<1>(), and so on. However, there is nothing that stops the „loop“ right now. For that, we need to add a second template argument that denotes the maximum loop counter:

template <size_t INDEX, size_t COUNT>
void ForEach(void)
{
  MyFunction();
  ForEach<INDEX+1, COUNT>();
}

We could now use a template specialization in order to terminate the loop when INDEX == COUNT, but that doesn’t really work in our case because we want to have different ForEach calls with different loop counters.
Another option would be to add a third template argument that denotes whether the loop should terminate or not, and specialize the template for that argument. However, partial template specializations are not allowed on function templates, so that doesn’t work either.
There is a third option, however: type-based dispatching. By introducing two overloads of the ForEach function template, we can choose the correct one by supplying an unused temporary argument to the function call.

template <int N>
struct IntToType {};

typedef IntToType<true> ForEachDoNotTerminateLoop;
typedef IntToType<false> ForEachTerminateLoop;

template <size_t INDEX, size_t COUNT>
void ForEach(ForEachDoNotTerminateLoop)
{
  MyFunction();
  ForEach<INDEX+1, COUNT>(IntToType<(INDEX+1 < COUNT)>());
}

template <size_t INDEX, size_t COUNT>
void ForEach(ForEachTerminateLoop)
{
}

For an explanation of how the IntToType template works, see the original post. The important thing to note is that IntToType<false> and IntToType<true> yield two different types. Hence, IntToType<(INDEX+1 < COUNT)>() will yield a temporary of either type, which forces the compiler to undergo overload resolution, choosing one of our two overloads, depending on whether the expression INDEX+1 < COUNT was true or false. The two typedefs only exist to make the code more readable and clear.

And that is basically our compile-time for-loop. All we need now is another function template that kicks of the ForEach process:

template <size_t COUNT>
void ForEachFunction(void)
{
  ForEach<0, COUNT>(IntToType<(0 < COUNT)>());
}

So by calling ForEachFunction<3>, we get calls to MyFunction<0>(), MyFunction<1>(), and MyFunction<2>(). Just what we wanted!

Of course, in production code we need the ForEach function template to be much more generic, so that we can call both free functions and member functions with an arbitrary number of arguments. Additionally, we want to be able to specify which function should be called.
All of that adds quite a bit of boilerplate code and several more overloads, but is left as an exercise for the reader. The next version of the Molecule Core Library SDK will contain a full-blown implementation if you want to take a look.

Back to the start

Finally, we are able to correctly implement our Add() and Remove() methods for our SOA-style array:

void ArraySOA::Add(const Item& item)
{
  ForEachClassMethod<AddItem, ARRAY_COUNT>(this, item);
  ++m_size;
}

void ArraySOA::Remove(size_t i)
{
  const bool isLast = (i+1u == m_size);
  if (!isLast)
  {
    ForEachClassMethod<RemoveItem, ARRAY_COUNT>(this, i);
  }
  --m_size;
}

template <size_t N>
void AddItem(const Item& item)
{
  typedef typename GetType<Item, N>::Type DataType;
  DataType* data = static_cast<DataType*>(m_array[i]);
  data[m_size] = item.*(GetPointerToMember<Item, N>());
}

template <size_t N>
void RemoveItem(size_t index)
{
  typedef typename GetType<Item, N>::Type DataType;
  DataType* data = static_cast<DataType*>(m_array[i]);
  data[index] = data[m_size-1u];
}

Note how the code in the original loop has been moved into a function template, which is invoked by the ForEachClassMethod calls.

For a final implementation, there are a two more things left to do:

• The ArraySOA class should be able to handle any struct type T, not just Item.
• The ArraySOA class should offer methods for accessing elements both in AOS-fashion and SOA-fashion.

In Molecule, I dealt with the latter feature by using nested structs inside all types T. As an example, this is what a point light component looks like:

struct PointLightComponent
{
  struct Aos
  {
    math::vector4_t m_positionRadius;
    math::vector4_t m_diffuseColor;
    math::vector4_t m_specularColor;
    math::vector4_t m_shadowColor;
  };

  struct Soa
  {
    size_t m_count;

    math::vector4_t* m_positionRadius;
    math::vector4_t* m_diffuseColor;
    math::vector4_t* m_specularColor;
    math::vector4_t* m_shadowColor;
  };
};

The nested struct Aos is used for adding instances to the array, which offers the following interface:

template <class T>
void ArraySOA<T>::Add(typename const T::Aos& item);

For retrieving elements from the array, the class offers the following methods:

template <class T>
typename T::Aos ArraySOA<T>::GetAos(size_t index);

template <class T>
typename T::Soa ArraySOA<T>::GetSoa(size_t index);

template <class T>
typename T::Soa ArraySOA<T>::GetSoa(void);

GetAos() is useful if you only need read-access to the values stored in the array. Because all members are stored by-value, the data in the array cannot be changed.

GetSoa() returns the data of one particular entry in the array, which is useful for write-access because the struct’s members are stored by-pointer. Additionally, GetSoa() can return the whole data streams for all members, which is mostly used by individual component systems for bulk updates.

Last but not least, all the SOA-traits template specializations introduced in the beginning of the post have to be added for the struct as well, which is achieved using simple macros:

ME_DEFINE_SOA_CLASS(PointLightComponent, 4);
ME_DEFINE_SOA_TYPE(PointLightComponent, 0, math::vector4_t, m_positionRadius);
ME_DEFINE_SOA_TYPE(PointLightComponent, 1, math::vector4_t, m_diffuseColor);
ME_DEFINE_SOA_TYPE(PointLightComponent, 2, math::vector4_t, m_specularColor);
ME_DEFINE_SOA_TYPE(PointLightComponent, 3, math::vector4_t, m_shadowColor);

The macros do nothing more than declare the template specializations introduced earlier.

Wrapping up

To recap, our ArraySOA needs/uses the following things to get the job done:

• Our own type traits that identify types and pointers-to-members of all members in a struct T.
• Pointers-to-members for type-safe access to individual members of any struct T.
• A compile-time for-loop that is able to call function templates with a compile-time counter.
• Nested structs Aos and Soa to differentiate between the different kinds of access.

Performance-wise, the disassembly of the generated code boils down to the exact same code as if it was written by hand. This specifically means that e.g. ForEachClassMethod<AddItem, 3>(this, item) does exactly 3 assignments to the corresponding array streams, and nothing more. Neither the for-loop nor the pointers-to-members have any overhead when compiler optimizations are turned on.

And that concludes our implementation of the semi-automatic SOA-style array. Because storing elements in SOA-fashion is not natively supported by the language, we have to add quite a bit of extra declarations to each struct before it can be used, but that’s still better than having to write all that code by hand. I really would like to have a fully automatic implementation, but I don’t believe that’s possible without compiler support.