So I was trying to write a game from scratch. One of the first things I had to consider was whether I should bother doing an “Entity Component System” (ECS) or simply have a giant, “fat” struct with all the stuff packed into it. While a giant struct is easy to understand, the idea behind ECS is a little more sophisticated, but basically boils down to splitting a program’s data into separate arrays to achieve better CPU cache utilization.

If you’re not familiar with the topic I recommend you watch the talk by Mike Acton on Data Oriented Programming. The post is written with an expectation that the reader already knows the basics of virtual memory and CPU caches.

The choice is essentially between an Array of Structs (AoS) and a Struct of Arrays (SoA). Supposedly, the latter is faster, and some will tell you to always prefer it over AoS. Online, I commonly see weird examples of SoA where vectors are stored like this:

struct Positions
{
  float *x;
  float *y;
  float *z;
}

It isn’t particularly clear to me whether this is merely an example or serious advice. However, using SoA for maximum performance seems like the way to go. Or is it? Well, that’s what I wanted to find out.

In this post, I want to take a simple task that you would realistically encounter when making a game, then create a bunch of different struct layouts and compare their performance, taking access patterns into account.

The Setup

The task is as follows: you have a list of entities considered “dirty”, perhaps given to you by the physics engine, you want to recompute the transform matrix for each entity using respective position, rotation and scale. For the sake of simplicity, there will be no parents or children in the transform hierarchy. Here’s what I’m going to do:

1. Prepare a list of dirty entity IDs (sequential or random list of all entities).
2. Compute transform matrix using 4 different layouts:
   • Fat Struct - Contains transform, output transform matrix and junk padding.
   • Lean Struct - Contains transform and output transform matrix.
   • Lean Struct (+ Separate Output) - Entity contains only the transform data. The output matrix is stored in a separate array.
   • SoA - Each field is its own array.
3. Test it with 10'000, 100'000, 400'000 and 1'000'000 entities.

Here is the code for the 4 struct layouts:

// 376 bytes per entity. Chosen arbitrarily
struct Entity_Fat 
{
  float4   rotation;
  float3   position;
  float3   scale;
  float4x4 transform;
  // We simply pad the struct to pretend
  // that there is unrelated data in there
  char _junk_data_1[270];
};
Entity_Fat *entities_fat;

struct Entity_Lean
{
  float4   rotation;
  float3   position;
  float3   scale;
  float4x4 transform;
};
Entity_Lean *entities_lean;

struct Entity_Lean_Separate_Output
{
  float4 rotation;
  float3 position;
  float3 scale;
};
Entity_Lean_Separate_Output *entities_lean_input;
float4x4                    *entities_lean_output; // Note that we have a separate output array

struct Entity_SOA
{
  float4   *rotation;
  float3   *position;
  float3   *scale;
  float4x4 *transform;
};
Entity_SOA entities_soa;

And here is the loop we’re going to test:

void test_fat()
{
  for(uint64_t i = 0; i < ENTITY_COUNT; i++)
  {
    int entity_index = entity_access_indices[i];

    Entity_Fat *entity = &entities_fat[entity_index];
    entity->transform = make_transform(entity->position, entity->rotation, entity->scale);
  }
}

The test function looks about the same for each struct layout so I will leave the full versions in the source code for brevity. make_transform is a procedure that computes a transform matrix. I thought it would be nice to have something at least somewhat resembling a real workload for the test.

I ran these tests on AMD Ryzen 3700X. Each test function is executed 1'000 times. I graphed only the median, although the program itself also computes min, max and the average values as well, in case you want to run it for yourself. The numbers seem pretty stable between program restarts as well, but they do depend on the mood of my computer on a particular day a little.

Comparing fat structs

Before comparing different layouts I would like to point out something else I found interesting: the size of a struct greatly influences its performance characteristics, even for the linear access pattern.

Linear Access - Median Time

Wait but, I’m doing predictable memory access here, aren’t I? I’m reading 1-2 cache lines of data and then store the result, how come the prefetcher doesn’t help me here?

Well as it turns out, it is because hardware prefetchers operate with “streams”. When at least 2 cache misses occur within a page, the CPU allocates a “prefetch stream” for that particular page and tries to predict which cache lines are gonna be read next. Note, that this works on a cache line granularity. As far as I can tell, the hardware does not care if your array accesses are done with stride of 1 or 2 bytes, it only sees that you have accessed two adjacent cache lines so it will try to load the next adjacent cache line.

The important bit here is that each stream is limited to a single page of memory (4 KiB usually). Iterating with big strides causes a program to cross page boundaries more often - leading to performance degradation. Prefetching across page boundaries is also a thing, but it is pretty limited. From this article, it seems like CPU might preload first 2 cache lines of the next page. However, newer CPU designs such as Intel Redwood Cove have improved cross-page prefetchers, that “attempt to bring entire 4Kb page to the last level cache” (quote from Intel Optimization Reference Manual). Sadly, I do not have a CPU to test this with, but I wouldn’t count on this behavior when targeting the general audience.

Lastly I want to point out, that the 2048 byte struct is significantly slower than the other 2 versions even when doing only 10'000 operations, It’s hard to see, but the difference is 0.2 ms vs 0.06 ms

Comparing data layouts

Linear Access - Median Time

This is exactly what I expected to see. SoA is a little bit faster than any of the other ones. My understanding is that, even though we load 4 separate cache lines (index, position, rotation and scale), they can be used to compute ~16 matrices without going back into RAM, compared to “Lean Struct” where 40 bytes of a single cache line are used to compute just one transform matrix. I speculate that multiple prefetch streams could also be helping SoA.

Random Access - Median Time

Interesting. SoA is becoming about as slow as the Fat Struct when doing random access. I generally thought that SoA is supposed to just “be better” than everything else, but it very clearly isn’t the case here. So what gives?

Well, if we think about it, remember how SoA needs to load 4 separate cache lines to compute the transform matrix? Now, we only use 1 value from each cache line and discarding the rest of it immediately. Compared to that, the Lean Struct layout only needs to read ~2 cache lines to both compute and write the result.

Digging a little deeper, I’ve decided to try using AMD uPerf (VTune would be the equivalent for Intel) and found something else.

There is a sharp rise in L2 TLB misses! The Translation Lookaside Buffer (TLB) is used to cache mappings from virtual to physical addresses. When a miss occurs, the CPU has to invoke the Page Walker and search for the physical address by, well, walking the page table. Naturally, the Fat Struct layout experiences a lot of misses because there are only around 10 entries per page, making it difficult for the CPU to keep data in cache. With SoA specifically, we jump 5 times as many pages per iteration, compared to the Lean Struct version, so it naturally produces more TLB misses.

Conclusion

It seems pretty apparent to me that fat structs are indeed fine until they get too big or until you have too many things to process at once. Although, “a lot” here stands for “around 100'000”. All and all, using fat structs as a starting point is pretty reasonable. If you have to do a lot of random accesses then it might be a good idea to make your data as small as possible and avoid constantly jumping between pages.
Nowhere in this blog have I discussed what happens if you run this code using multiple threads, where you have to start caring about false sharing, among other issues. Perhaps I will explore that next time.

The source code for the benchmark can be found here.

I learned something new doing this, hopefully it was useful to you, the reader, as well. Thanks for following along, see you in the next one!

References

1. “What Every Programmer Should Know About Memory” by Ulrich Drepper
2. Battling the Prefetcher: Exploring Coffee Lake by Bertschi Andrin
3. Intel® 64 and IA-32 Architectures Optimization Reference Manual