5 ms·

As a game developer, should I be thinking about reducing branches in performance critical loops?

dminik 3y ago
As a game developer, you should consider reducing branches in shaders. Though if you're CPU bound, then sure, it's something to think about.
r1ch 3y ago
Ideally try to design your loops so you're accessing memory sequentially (better cache locality) and predictably (i.e. don't branch on a condition that changes in every iteration). Using a branchless algorithm is only really beneficial if the branch is constantly being mispredicted. As always, profile first so you don't fall into the premature optimization hole.
iforgotpassword 3y ago
This isn't necessarily game-specific. I'm not up to speed with current gen, but in the past the simple answer was "it depends", as usual. :-) There are times where doing some bit-twiddling hacks outperform branching, or where (partial) loop-unrolling is faster than the higher code density of a firm loop, but in the end for trivial cases, the compiler often, but not always, would do these things behind the scenes if you tell it what CPU you want to target. And if you really want the best performance in a particularly hot section, you just have to benchmark every possible implementation and pick on a case-by-case basis, or even provide two or three different implementations and pick the best one at runtime.
- clamchowder 3y ago
  (author here) I think it's not useful to eliminate branches in hot loops. These games have giant instruction footprints and a high branch rate. A loop will probably fit within the L1 BTB and uop cache, and probably won't benefit from eliminating branches. Exception would be a branch that's near impossible to predict, like one that depends on a randomly generated value or otherwise doesn't correlate well with global history.
doctorpangloss 3y ago
Yes, here's an example of a case where eliminating a branch will save you as a game developer: while (money > 0) { if (iOS) { // ios revenue money += 5; // ios costs money -= 2; } else if (android) { // android revenue money += 1; // android costs money -= 5; } } Anyway, to your real question, an entity component system-based middleware, hopefully in a language that isn't C++, forces you to author your code in a way where branches can be "moved" to remove the problematic memory access and execution pattern. So maybe it's not about specific C++ method branches, which may be beneficial to your employer but never beneficial to you or your career, but it's about the architecture of the thing that still has innovation opportunities that could really matter. You probably aren't interested in the even bigger picture conversation, which is that some games are so ill specified that it is impracticable to use an ECS middleware. Games that are really well specified (i.e. clones & sequels) might thrive on ECS, but the ones we end up playing are authored by companies with real budgets and take years to develop, so the compute platform will get faster than your micro-optimization.
vlovich123 3y ago
TLDR: worry about branches in your hot loop kinda last and only if the profiler indicates you have a random walk through your branches AND you’ve verified the compiler emitted branches. There are more impactful optimization techniques to worry about first and often with PGO and LTO the compiler is going to be a lot better about making relevant code branchless on your behalf without you having to think about it. I’d say that’s something you should only do once you understand your architectural bottlenecks. These are bottlenecks that appear because of how you’re doing computation and moving data around. They won’t show up on any profiler because the profiler is telling you “this is where an implementation is slowest” and not “there’s a better implementation altogether” - the latter is art as it requires a good working understanding of computer architecture and playing around with algorithms that aren’t taught in text books (or adapting them more optimally for your problem domain). If you’ve done all other major architectural optimizations and you’ve identified a hot loop where the compiler is inserting branch code which is mispredicted, an explicitly branchless version will help. But remember - compilers are very good often at recognizing the opportunity for a branchless version and changing your code to that, so if you’re in AOT land with a major compiler (clang/llvm, gcc, msvc, Intel) there’s a good chance your algorithm might already be branchless. In fact, if you use something like PGO on a realistic workload, the compiler is even more likely to emit the correct machine code in way more places without you having to manually alter code by hand. More impactful low level optimizations often are: Optimizing for cache locality through something like entity component systems (ECS). Basically using a struct of arrays and no polymorphism instead of an array of polymorphic structs. This is a popular one for games and works really well. Similarly, make sure that data being accessed in a hot path is all linearly laid out in processing order if possible. Applying SIMD to your hot loop processing. The compiler does have autovectorization that can work well with ECS but requires you to write your scalar code carefully to trigger it (ie your scalar code has to look similar to the vector version in important ways). Check the assembly to see if the compiler is doing it and rewrite using compiler intrinsics when it’s not. Similarly try to minimize data dependencies between your loops. Eg instead of sum=0 foreach x in arr sun += x Try sum0 = 0, sum1 =0, … sum7 = 0 foreach (x0, x1, …, x7) in arr sum0 += x0 … sum = sum0 + sum1 +… That’s very very similar to what a SIMD loop would look like and a compiler is likely to recognize it. Even if it doesn’t autovectorize, you’re now doing 8 summations “concurrently” because there’s no data dependency for those 8 additions on every loop iteration, so the CPU will execute them without waiting for the result of any other summation. Make it unrolled enough to exhaust the execution units and you’ve guaranteed that the beginning of the loop will start after the previous data dependency has been resolved (ie the CPU will be executing that loop at maximum speed). Again, this kind of stuff is silly to worry about until you figure out where your hot loop is for a given implementation. Knute writes “premature optimization is the root of all evil”. Implementation optimizations can get you very small improvements once you’ve exhausted low hanging fruit (basically implementation mistakes). Switching implementations can often net you order of magnitude improvements. Looking into branchless is probably often premature. Organizing your data efficiently and using good algorithms is not. Data dependencies in loops is probably in the middle there - they optimize your current implementation but the improvement for that hot loop can be drastically more significant than a branchless design (fixing data dependencies can easily 10x your performance, making branchless for a mispredicted loop can net you maybe 20% or so for that hot loop).
nwallin 3y ago
You should run your critical loops through perf or a similar tool and get statistics for branch misprediction. If you have a lot of misprediction, you should think about doing branchless stuff. If you don't have a lot of misprediction, the branchy code will be faster. Sometimes you can guess whether the data the loop will hit will be predictable or not. The same applies; if you expect it to be predictable, then don't try to remove branches. If you expect it to be unpredictable, try to remove branches. Note that you will need to teach yourself your expectations; the branch predictor might be better or worse than you expect it to be. Modern branch predictors are extremely complex, often taking more die space than everything except cache. Don't assume that just because you can't see a pattern in the data, the branch predictor won't be able to.
kevingadd 3y ago
Branches are still valuable in many cases but it can be valuable, situationally, to replace them with things like cmovs instead. You'll need to benchmark it to be sure - it's not like the old days where branches were always worse. Branch hoisting, on the other hand, is a win like 90% or more of the time (I can imagine it being a loss if it causes stuff to fall out of icache), which is why most compilers will try to do it automatically. Worse than branches (generally) are indirect calls (i.e. virtual methods, function pointers) that don't predict well, so you especially want to avoid those in tight loops and if you can't avoid them you want to sort your data so that the call target doesn't change frequently.
fear91 3y ago
Only if they are poorly predicted.

As a game developer, you should consider reducing branches in shaders. Though if you're CPU bound, then sure, it's something to think about.

r1ch 3y ago

Ideally try to design your loops so you're accessing memory sequentially (better cache locality) and predictably (i.e. don't branch on a condition that changes in every iteration). Using a branchless algorithm is only really beneficial if the branch is constantly being mispredicted. As always, profile first so you don't fall into the premature optimization hole.

iforgotpassword 3y ago

This isn't necessarily game-specific. I'm not up to speed with current gen, but in the past the simple answer was "it depends", as usual. :-) There are times where doing some bit-twiddling hacks outperform branching, or where (partial) loop-unrolling is faster than the higher code density of a firm loop, but in the end for trivial cases, the compiler often, but not always, would do these things behind the scenes if you tell it what CPU you want to target. And if you really want the best performance in a particularly hot section, you just have to benchmark every possible implementation and pick on a case-by-case basis, or even provide two or three different implementations and pick the best one at runtime.

clamchowder 3y ago
(author here) I think it's not useful to eliminate branches in hot loops. These games have giant instruction footprints and a high branch rate. A loop will probably fit within the L1 BTB and uop cache, and probably won't benefit from eliminating branches. Exception would be a branch that's near impossible to predict, like one that depends on a randomly generated value or otherwise doesn't correlate well with global history.

doctorpangloss 3y ago

Yes, here's an example of a case where eliminating a branch will save you as a game developer: while (money > 0) { if (iOS) { // ios revenue money += 5; // ios costs money -= 2; } else if (android) { // android revenue money += 1; // android costs money -= 5; } } Anyway, to your real question, an entity component system-based middleware, hopefully in a language that isn't C++, forces you to author your code in a way where branches can be "moved" to remove the problematic memory access and execution pattern. So maybe it's not about specific C++ method branches, which may be beneficial to your employer but never beneficial to you or your career, but it's about the architecture of the thing that still has innovation opportunities that could really matter. You probably aren't interested in the even bigger picture conversation, which is that some games are so ill specified that it is impracticable to use an ECS middleware. Games that are really well specified (i.e. clones & sequels) might thrive on ECS, but the ones we end up playing are authored by companies with real budgets and take years to develop, so the compute platform will get faster than your micro-optimization.

vlovich123 3y ago

TLDR: worry about branches in your hot loop kinda last and only if the profiler indicates you have a random walk through your branches AND you’ve verified the compiler emitted branches. There are more impactful optimization techniques to worry about first and often with PGO and LTO the compiler is going to be a lot better about making relevant code branchless on your behalf without you having to think about it. I’d say that’s something you should only do once you understand your architectural bottlenecks. These are bottlenecks that appear because of how you’re doing computation and moving data around. They won’t show up on any profiler because the profiler is telling you “this is where an implementation is slowest” and not “there’s a better implementation altogether” - the latter is art as it requires a good working understanding of computer architecture and playing around with algorithms that aren’t taught in text books (or adapting them more optimally for your problem domain). If you’ve done all other major architectural optimizations and you’ve identified a hot loop where the compiler is inserting branch code which is mispredicted, an explicitly branchless version will help. But remember - compilers are very good often at recognizing the opportunity for a branchless version and changing your code to that, so if you’re in AOT land with a major compiler (clang/llvm, gcc, msvc, Intel) there’s a good chance your algorithm might already be branchless. In fact, if you use something like PGO on a realistic workload, the compiler is even more likely to emit the correct machine code in way more places without you having to manually alter code by hand. More impactful low level optimizations often are: Optimizing for cache locality through something like entity component systems (ECS). Basically using a struct of arrays and no polymorphism instead of an array of polymorphic structs. This is a popular one for games and works really well. Similarly, make sure that data being accessed in a hot path is all linearly laid out in processing order if possible. Applying SIMD to your hot loop processing. The compiler does have autovectorization that can work well with ECS but requires you to write your scalar code carefully to trigger it (ie your scalar code has to look similar to the vector version in important ways). Check the assembly to see if the compiler is doing it and rewrite using compiler intrinsics when it’s not. Similarly try to minimize data dependencies between your loops. Eg instead of sum=0 foreach x in arr sun += x Try sum0 = 0, sum1 =0, … sum7 = 0 foreach (x0, x1, …, x7) in arr sum0 += x0 … sum = sum0 + sum1 +… That’s very very similar to what a SIMD loop would look like and a compiler is likely to recognize it. Even if it doesn’t autovectorize, you’re now doing 8 summations “concurrently” because there’s no data dependency for those 8 additions on every loop iteration, so the CPU will execute them without waiting for the result of any other summation. Make it unrolled enough to exhaust the execution units and you’ve guaranteed that the beginning of the loop will start after the previous data dependency has been resolved (ie the CPU will be executing that loop at maximum speed). Again, this kind of stuff is silly to worry about until you figure out where your hot loop is for a given implementation. Knute writes “premature optimization is the root of all evil”. Implementation optimizations can get you very small improvements once you’ve exhausted low hanging fruit (basically implementation mistakes). Switching implementations can often net you order of magnitude improvements. Looking into branchless is probably often premature. Organizing your data efficiently and using good algorithms is not. Data dependencies in loops is probably in the middle there - they optimize your current implementation but the improvement for that hot loop can be drastically more significant than a branchless design (fixing data dependencies can easily 10x your performance, making branchless for a mispredicted loop can net you maybe 20% or so for that hot loop).

nwallin 3y ago

You should run your critical loops through perf or a similar tool and get statistics for branch misprediction. If you have a lot of misprediction, you should think about doing branchless stuff. If you don't have a lot of misprediction, the branchy code will be faster. Sometimes you can guess whether the data the loop will hit will be predictable or not. The same applies; if you expect it to be predictable, then don't try to remove branches. If you expect it to be unpredictable, try to remove branches. Note that you will need to teach yourself your expectations; the branch predictor might be better or worse than you expect it to be. Modern branch predictors are extremely complex, often taking more die space than everything except cache. Don't assume that just because you can't see a pattern in the data, the branch predictor won't be able to.

kevingadd 3y ago

Branches are still valuable in many cases but it can be valuable, situationally, to replace them with things like cmovs instead. You'll need to benchmark it to be sure - it's not like the old days where branches were always worse. Branch hoisting, on the other hand, is a win like 90% or more of the time (I can imagine it being a loss if it causes stuff to fall out of icache), which is why most compilers will try to do it automatically. Worse than branches (generally) are indirect calls (i.e. virtual methods, function pointers) that don't predict well, so you especially want to avoid those in tight loops and if you can't avoid them you want to sort your data so that the call target doesn't change frequently.

fear91 3y ago

Only if they are poorly predicted.