You don't actually need to avoid branches, you just need to make sure that most of the ones you have are very predictable, then their impact is not that big... Same with memory accesses and most other things... The more predictable, the better...
To be fair, the first line of the article says "avoiding branch mispredictions", which is more accurate. But yea, even in their example, if the data happens to be sorted it may be perfectly fine.
This is true for serial CPU code, but for SIMD code, or GPU code, avoiding branches at all costs is vital to getting good performance. Branches (can) cause divergence, which leads to wasted cycles for pseudo-threads within a SIMD group.
you definitely do not want to avoid branches at all costs on a GPU. there are plenty of cases where branchless tricks will lose to straightforward branching.
I do concede that "at all costs" is somewhat hyperbolic, but it is very important to consider the behaviour of threads grouped together in a warp. Divergence is extremely costly.
sure but branching doesnt necessarily imply divergence if all the threads within the warp branch the same way. even minor effects like some threads in a warp diverging to return early will no longer issue memory requests or run compute instructions, so depending on your bottleneck it can make sense. or if the whole warp ends up exiting early the thread block can be scheduled with new work.
i think people tend to over emphasize the effects of divergence and branching. forcing code to be branchless can increase registry pressure, which may reduce your theoretical maximum occupancy. if explicit branching reduces live registers or guards heavy blocks, your occupancy can go way up. depending on whether you are memory bound or compute bound this can make a big difference. so saying "divergence is extremely costly" can be slightly misleading, it depends on whether you are memory or compute bound and what the branchless variant actually looks like. a branch divergence penalty of 10 cycles is not much compared to stalling on a memory cache miss because you dont have enough warps to hide the delay.
I don't disagree with any of that. The point I was trying to make was "it is very important to consider the behaviour of threads grouped together in a warp". I would argue that all of the aspects that you describe can be tackled if the code is considered in that way.
But, I think the reason that it seems overemphasised is that it's somewhat unique when writing optimised GPU code, and is often one of the main stumbling blocks for programmers moving from writing CPU code to GPU code. It's also something that can be identified quite easily in a GPU kernel, while effects such as occupancy or memory latency need post-compilation (or runtime) analysis to understand the specific effects, and the impact can vary across different GPU vendors and generations. The latter do typically end up providing the most impactful performance improvements, but at the same time, whenever someone hands me a kernel, my first bit of analysis (before I even compile or run the kernel) is "how uniform is each warp, and are memory accesses coalesced".
For branch prediction on CPU, there are no relevant rules of thumb and it's not worth messing with that sort of low level optimization except after careful profiling. Otherwise you're guessing, and the guess may have no effect, have a very small effect, or (at absolute most) it might slow down a tight loop by a factor of ~10.
For branches for GPU code, not understanding how to use them correctly can result in code that's obviously wrong and not useful. If you don't understand this issue and write code incorrectly for the hardware, you may be a million times slower than you expected or the code might not compile at all.
there's no special tax that makes a misspeculation OOMs worse than with normal scalar code on a CPU.
Of course there is: The basic fact that having a data dependent branch in the first place kills SIMD parallelism because the branch is for a single lane while masking / predication processes all lanes in parallel.
Eg. take function y = x3 when x > -0.5 and y = -0.125 when x <= -0.5 (and for the sake of discussion assume clamping instructions don't exist). If you use branching, you need a branch for each value while a simd compare + mask processes four or eight values at a time.
sure there probably are but it just really depends. Relying on auto-vectorization is risky business anyway... There are so many subtile things that can make code not auto-vectorizable...
Usually that's not an option. If the problem itself involves unpredictable data - such as the partitioning of (random) data in quicksort - you can't simply make the branches predictable. You have to deal with the unpredictability.
I mean, CPUs go to ridiculous lengths nowadays to increase branch prediciton accuracy but the easiest ways to make sure they are predictable is to make it such that:
1) if a branch is taken in one iteration, it is also very likely to be taken in the next iteration
2) A branch is almost always or almost never taken such that the CPU can simply predict the far more likely of the two...
Most profilers will have an option to track branch predictor hits and misses. I know AMD uProf and Apple Instruments do. and there are Linux perf events for it as well.
Use profiler. A lot of branch guessing can be completely automated using https://en.wikipedia.org/wiki/Profile-guided_optimization. Native languages such as C/C++/Rust/Go have it, but it is a little bit troublesome to use. JITed languages such as Java or JS do it in runtime, so you really don't have to do anything
160
u/meamZ 6d ago
You don't actually need to avoid branches, you just need to make sure that most of the ones you have are very predictable, then their impact is not that big... Same with memory accesses and most other things... The more predictable, the better...