1
\$\begingroup\$

I lately read an article about branchless programming and how it can effect performance. Since im developing a little archetype based ECS for learning purposes, i wanted to know if theres a way to make it also as branchless as possible.

Typical places for branches are most likely :

  • Adding entities ( Archetypes need to check whether its full to allocate new memory... )
  • Removing entities ( Archetypes need to check if its small enough to trim memory )
  • Query ( If statement to check whether each archetype contains the queried types )
  • Get Operations ( Dictionary lookups & possible if statements )

Is there any way to design an archetype ECS without any branches ? Or is this impossible since branches are pretty common for this task ?

\$\endgroup\$
1
  • 2
    \$\begingroup\$ I think you'd have a hard time 100% eliminating all branches. Checking when to allocate in particular is pretty necessary, unless you can 100% predict the collection size you need in advance and pre-allocate it all. But at least adding new entities is usually rarer than iterating them. Even then, the C# compiler will insert bounds checks every time you index into a collection, and looping over entities needs a branch to decide when to stop vs keep looping. Fortunately these all predict well. Have you profiled your code to identify which branches / mispredictions are having the most impact? \$\endgroup\$
    – DMGregory
    Commented Dec 2, 2022 at 13:32

1 Answer 1

3
\$\begingroup\$

As mentioned in the comment above, you can't practically eliminate all branches in an ECS written in C#. By the nature of an ECS, you're going to be looping over arrays of components. Every loop has a branch to decide whether to keep looping, and every array access in a managed language like C# has bounds checks to make sure you're not indexing beyond the bounds of the array.

Fortunately in correctly written code, these bounds checks always pass, so they should be predicted correctly by the branch predictor and have practically no cost. There's some evidence I saw recently from examples in Rust that backs that up. Similarly, the branch in a loop can be reliably predicted as "always loop", and it only gets it wrong on the last iteration. (You can reduce this overhead further using Span<T> instead of List<T>, or fetching a Span<T> version just in time)

So, not all branches are equally bad. What you want to avoid are random-looking branches that will frequently mis-predict and cause pipeline stalls.

One of the most common ways to get this is if your arrays of components can contain empty slots from destroyed entities, or entities temporarily disabled. Then every system update needs to have a branch that checks whether this component is valid to act on it before it acts. Since entities can be disabled/destroyed randomly (up to the whims of your game mechanics), those branches can be hard to predict. One good way to solve this, if you can, is to defer entity destruction to the end of a frame, and swap components of destroyed entities to the ends of their respective arrays, keeping living ones densely-packed at the head of the array (and updating ID lookups as necessary in this cleanup step). Then your liveness check just becomes your loop bounds check, and it predicts correctly until the last iteration. This also helps you get optimum cache utilization, since you don't waste precious cache line space on components that will be skipped over.

This is harder if just one component needs to be disabled out of a larger multi-component entity. In that case, you might need to just eat the branch cost (especially if it's a rare occurrence), or look at ways you can make its operation a no-op if you find the branch is a significant performance cost in your profiling. Or you could move the entity to another archetype which has the Disabled<ComponentType> component instead of the original ComponentType. This can have all the same fields to store the data/state for later re-enabling, but will be ignored by systems looking to update ComponentType.

Adding and removing entities should be much less common than iterating them, so this is unlikely to be a major performance sink. In cases where you are adding/removing many entities at once, and your profiling shows a significant cost from all the checks, it's likely you're adding/removing many of the same archetypes. In that case, you can look at batching up these operations. 300 new bullet entities have been requested this frame? I'll do my memory checks and allocations once to ensure there's room for 300 more, then bulk-fill that space with certainty that it's there, rather than repeatedly checking and incrementally expanding 300 times.

Queries are ripe for pre-computing. At the start of your game or at the start of a new scene, initialize each system that's going to be active in that scene, and have it register each of the queries it uses. Hand it back an object with a list of matching archetypes (initially empty). Now, each time you spawn a new archetype (not a new entity of an archetype - only do this the first time a new archetype is used), you run through that list of pre-registered queries and check which ones it matches, adding it to the response lists for those queries. Almost all of this work can be done at scene start-up, with zero matching cost per system update, because all the archetypes they need are already listed. Only occasionally will you introduce a new archetype mid-scene, and you only pay its matching cost once.

Your entity lookups could be a single array rather than a dictionary, mapping a sequential ID counter to its current archetype and index in that archetype (updating that book-keeping whenever you do a swap). You can use a free list to fill holes in that array as entities are created and destroyed. A generation number can help you detect when an ID you're holding refers to a now-destroyed entity that's been replaced.

Conditional logic within your component updates is a whole different ball game, but now you're outside of what's specific to an ECS, and into regular gamedev challenges.

Just remember: branches are not the greatest evil. You should expend only as much effort avoiding them as your measured profiling data confirms they're causing problems. A pipeline stall sucks, but as long as it's not happening constantly you can still get excellent performance.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks a lot ! :) This was an incredible usefull and detailed answer ! \$\endgroup\$
    – genaray
    Commented Dec 5, 2022 at 21:40

You must log in to answer this question.

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