2
\$\begingroup\$

When I process a bunch of component data, I'd like that data to be sorted in such a way that I can iterate through the component buffers linearly. For instance when I want to update the physics system, in an ideal world the buffers for the TransformComponent, MovementComponent and PhysicsBodyComponent are structured in such a way that I would be able to iterate over the entities like this:

for(int i = 0; i < m_numEntitiesInSystem; i++)
{
    Transform& transform = g_transformBuffer[i];
    MovementComponent& movement = g_movementBuffer[i];
    PhysicsBodyComponent& body = g_physicsBodyBuffer[i];
    // ... update physics ...
}

The main advantage of this is that I would have next to no cache misses for this system. Because different systems require different (combinations of) components, this would imply that before every system update, I would either have to sort the respective component buffers so that they are aligned or I would have to use a cache that is local to the system only (this cache would need to be synced every time a component changes).

Of course both approaches come at a cost as well, sorting the component buffers could affect the ability to execute systems on separate threads. Not to mention that the sorting process itself might have its own performance drawbacks. Syncing the component data implies that some components might need to be copied over possibly several times per frame which again might come with its own performance drawbacks.

My question is: is the price of sorting or syncing worth being able to process data linearly? Or is it wiser to try organise the data in such a way that the most executed/expensive systems perform optimally and others potentially less so. If the former, would it be preferable to use the sorting method or the syncing method?

Also please don't tell me that "premature optimization is evil". Since this is more or less the foundation of my engine, I want it to be as well written and designed as I can. Or at least I want to understand the consequences of picking one method over the other.

Thank you so much!

\$\endgroup\$

2 Answers 2

1
\$\begingroup\$

It's difficult to say which way is best, since we don't know how prone your setup is to cache misses without this.

I think I remember Jonathan Blow describing doing this type of sort-before-update on one of his developer streams, as a way to improve performance late in a project, so there certainly could be cases where it's beneficial. Without profiling data though, it's not clear how much net savings you'd get, and whether it's worth the cost in complexity or threading flexibility as you mentioned.

One thing to consider is that just iterating in a sorted order, even with gaps, can still be a lot better than a random zig-zag backwards and forwards through memory!

So you might not need to re-sort for every system to get the lion's share of the cache miss savings. A single shared sort order that tends to keep clusters of entities close together for one or a few of your highest-throughput systems might be enough to keep your game running smoothly, even if most / all systems still encounter some gaps in their iteration.

But again, we can't really quantify this to test it without knowing the typical distributions of your data at runtime. There are use patterns under which this will perform at efficiency approaching the theoretical maximum, and other use patterns under which it will suffer as badly as pointer-chasing. So there's really no substitute for building tests and profiling, even if it means you go down the wrong road at first and need to refactor once you know in detail what your runtime data characteristics are like.

\$\endgroup\$
2
  • \$\begingroup\$ This gave me some new insights to consider, thanks! By any chance do you know where I can find Jonathan Blow's talk about this? And as a follow up question: do you have any recommendations for good profilers? I noticed visual studio's profiler won't let me analyze cache misses and I can't really afford a tool like VTuner. \$\endgroup\$
    – PhilipMR
    Nov 6, 2017 at 16:16
  • \$\begingroup\$ It'll be hard to find that reference. It was an offhand remark made during one of his programming language videos, of which there are now 48, and I couldn't say with confidence which one it was. The Q&A here is also not the best place to poll folks on tech preferences - try Game Development Chat for that kind of opinion-based discussion. \$\endgroup\$
    – DMGregory
    Nov 6, 2017 at 17:16
1
\$\begingroup\$

It's great that you have taken the time to think about a couple of ways to accomplish this.

Unfortunately, there is no way to tell what's the best approach before you try it with actual data in an actual game.

Guessing where the bottlenecks are and trying to optimize that in advance may lead to work done in vain.

I spent two weeks rehashing the structure of some data over which were were doing a lot of process. All the data was created in random memory location, using pointers. There was a lot on cache misses.

My assumption was that by regrouping the data in arrays, and having it accessed sequentially would reduce the cache misses and thus the time it takes to perform the calculation.

The results of all of this? It reduced the cache misses a lot, there was a 10% gain in performance for the processing itself, but the simple work to reorganize the data simply killed the performance gained.

So my suggestion is this: Build both approaches in your engine. Give tools to your user to measure how long a process takes with their real-world situation and allow them to use the one they feel is the best for them in their situation.

\$\endgroup\$
2
  • \$\begingroup\$ Thank you! A problem I often encounter when I want to analyze code performance is that (well first of all, I can't really seem to find a decent profiler, but also) it seems like some systems can't really be tested properly until the final stages of development. I could create two implementations A and B and find that A is faster than B. But later on when it turns out this system is actually used a lot more (or less) than expected, B actually performs better. What is your take on this? Throw in abstractions everywhere so that the implementation can changed at any time? \$\endgroup\$
    – PhilipMR
    Nov 6, 2017 at 16:22
  • \$\begingroup\$ IMHO it's better to try to come up with an engine with defined characteristics and optimize against them, embracing some cons that inevitably come along the way, than trying to abstract the hell out of everything to the point where you might not end up with a system that great at anything. As for profilers, CodeXL is a nice free one. I actually use that in spite of having used VTune for years at a former company. When my license expired, I switched to CodeXL's CPU sampling and haven't really missed VTune that much. \$\endgroup\$
    – user77245
    Dec 11, 2017 at 0:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .