Structure of Arrays

February 11, 2018

I discovered data oriented design a few years ago and kind of fell in love with the idea. Unfortunately at my day job I never really get much of a chance to flex my data oriented design muscles or to really play around with the concepts since it tends to fly in the face of typical OO design.1 On top of that one of the most frustrating things about trying to play around with DOD is that there are no modern languages I know of that provide data oriented containers out of the box, meaning just playing around with DOD requires quite a bit of work on the part of the learner.

This post is an attempt to rectify that, for C++ users at least. I hope the following SoA container helps you on your journey of learning about all things data oriented design. I think it might also be a decent introduction to variadic templates which I know can always be a little daunting, at least for me. Finally, full source is available on GitHub.

Why are you even talking about this?

There’s probably a very high chance you’re wondering what the hell it is I’m even talking about right now. Let me try to explain as briefly as I can why you might want a structure of arrays. First, lets consider the very commonly used alternative, an array of structures, a.k.a. a plain old object:

class Person {
    int id;
    const char* name;
    int age;
    int health;
    int food_amount;
    const char* weapon;
};

Now, in any old game you’re very likely not to have just one Person but many people (probably hundreds or even thousands), and so you create an array to store your people in:

std::vector<Person> people;
people.push_back({ 0, "Gandalf" , 2019, 999, 0, "staff" });
people.push_back({ 1, "Frodo"   , 31  , 30 , 1, "ring"  });
people.push_back({ 2 ,"Samewise", 61" , 40 , 2, "sword" });

Great. We did it. We’re the best! But no, that’s not quite true in this case.2 This way of storing data can actually be really inefficient in cases where we only care about certain parts of the data. For example, lets say our fellowship rests for the night and they all gain a little bit of health.

for (auto& person : people) {
    person.health += 10;
}

Well that was easy, but lets think a bit about what our program is actually doing here. In order to update our fellowship’s status we need to read all of the data of person 0, add 10 to their health, read in the next person’s data, add 10 to their health, and so on. Ok, that’s fine, but how much data is a Person?3 Well, if we’re on a 64 bit system then it would be four int at 8 bytes each and two const char* at 8 more bytes each. So 6 x 8 = 48 bytes. Does this matter? Well, when it comes to data oriented design it’s very important to remember a few things. Cache lines are small (on the order of 64 bytes), and reading from memory is slow, very very slow.

So what’s actually happening here is:

  1. Cache miss for Person 0 (~100ns)
  2. Update Person 0 health (~0.5ns)
  3. Cache miss for Person 1 (~100ns)
  4. Update Person 1 health (~0.5ns)
  5. Cache miss for Person 2 (~100ns)
  6. Update Person 2 health (~0.5ns)

Which brings us to a very scientific total of: 301.5ns

So what’s actually happening here is our program is just waiting around on memory reads. Very little useful work is happening which isn’t really what we intended at all! I hope you can see organizing your data this way can be very wasteful, especially if our Person class keeps growing. Why should we read in id, name, age, food_amount, and weapon every time we want to update health? We should just read and update health only.

Structure of Arrays

Of course there’s another way to lay out our data, unfortunately it just doesn’t come in the box that is the C++ Standard Library. Let’s build exactly what we have above but first we’ll turn our data 90 degrees.

struct People {
    std::vector<int> ids;
    std::vector<const char*> names;
    std::vector<int> ages;
    std::vector<int> healths;
    std::vector<int> food_amounts;
    std::vector<const char*> weapons;
};

People people;
people.ids.push_back(0);
people.names.push_back("Gandalf");
people.ages.push_back(2019);
people.health.push_back(999);
people.food_amount.push_back(0);
people.weapon.push_back("staff");

// Repeat for Frodo and Sam

Ok, that’s a lot of of typing and I didn’t even add our whole party yet! All this code does let us see that the individual properties of Person have been moved into their own arrays. In fact, the Person class itself it gone, and we no longer have a need for the concept of a single Person. All of our data manipulations will now happen in the context of everyone at once which is what we were doing anyways. Let’s look at what happens when our fellowship rests now.

for (auto& health : people.healths) {
    health += 10;
}

Mostly the same deal as above but this time we’re only accessing health data, exactly the 8 bytes we care about. And the memory accesses overall? Since all of our healths fit in one cache line (24 bytes), it should look something like this:

  1. Cache miss for Person 0 (~100ns)
  2. Update Person 0 health (~0.5ns)
  3. Update Person 1 health (~0.5ns)
  4. Update Person 2 health (~0.5ns)

“Total”: 101.5ns

Great! We theoretically sped up our code by a huge factor, and it only gets better the more people we have in our fellowship.

That code though >.>

Wouldn’t it be nice if C++ had a “Structure of Arrays” container like it had vector and unordered_map. Well, I wrote one, and it’s usage looks something like this:

enum Person {
    kId,
    kName,
    kAge,
    kHealth,
    kFoodAmount,
    kWeapon
};
using People = SoA<int, const char*, int, int, int, const char*>;

People people;
people.add(0, "Gandalf" , 2019, 999, 0, "staff");
people.add(1, "Frodo"   , 31  , 30 , 1, "ring");
people.add(2 ,"Samewise", 61" , 40 , 2, "sword");

for (auto i : people) {
    people.get<kHealth>(i) += 10;
}

I think that looks pretty good compared to the manual way of laying out a structure of arrays above. It gets even better when you realize we can be smarter than a bunch of unrelated vectors and instead of 6 mallocs we can allocate all the memory we need in one go. Internally it’s basically the same as our structure of arrays above. All healths live in one array and all names in their own array and so on.

Of course, you do lose some things with this method of structuring data. For one, it can be very difficult to find one specific “Person” when you need them. This can be solved a number of ways and my personal choice right now is to have a MappedSoA type that contains a map of Id to “Index” into the arrays themselves. This means that we have traded efficient access across all elements for a more inefficient lookup of single elements which would now be a table lookup followed by a random array access. But of course the whole point of having an SoA structure in your toolbox is just that, it’s another tool in your toolbox. I’m not mandating that all of your memory be laid out as structures of arrays but I also don’t think all of your data should be laid out into arrays of structures like OO design might lead you to believe.

The Code

This post ended up way longer than I thought it would and I didn’t even get to the code yet! Stay tuned for part 2 where I’ll dive into the code and hopefully explain what is going on in there.

  1. Of course, it doesn’t have to though. Which I hope to show here. ↩

  2. Don’t worry, I think you’re still pretty great. ↩

  3. What a weird thing to ask… and yet it also makes perfect sense. ↩

▲