27
\$\begingroup\$

Trying to figure out exactly what causes branching and what doesn't in GLSL.

I'm doing this a lot in my shader:

float(a==b)

I use it to simulate if statements, without conditional branching... but is it effective? I don't have if statements anywhere in my program now, nor do I have any loops.

EDIT: To clarify, I do stuff like this in my code:

float isTint = float((renderflags & GK_TINT) > uint(0)); // 1 if true, 0 if false
    float isNotTint = 1-isTint;//swaps with the other value
    float isDarken = float((renderflags & GK_DARKEN) > uint(0));
    float isNotDarken = 1-isDarken;
    float isAverage = float((renderflags & GK_AVERAGE) > uint(0));
    float isNotAverage = 1-isAverage;
    //it is none of those if:
    //* More than one of them is true
    //* All of them are false
    float isNoneofThose = isTint * isDarken * isAverage + isNotTint * isAverage * isDarken + isTint * isNotAverage * isDarken + isTint * isAverage * isNotDarken + isNotTint * isNotAverage * isNotDarken;
    float isNotNoneofThose = 1-isNoneofThose;

    //Calc finalcolor;
    finalcolor = (primary_color + secondary_color) * isTint * isNotNoneofThose + (primary_color - secondary_color) * isDarken * isNotNoneofThose + vec3((primary_color.x + secondary_color.x)/2.0,(primary_color.y + secondary_color.y)/2.0,(primary_color.z + secondary_color.z)/2.0) * isAverage * isNotNoneofThose + primary_color * isNoneofThose;

EDIT: I know why I don't want branching. I know what branching is. I'm glad you're teaching the children about branching but I would like to know myself about boolean operators (and bitwise ops but I'm pretty sure those are fine)

\$\endgroup\$
42
\$\begingroup\$

What causes branching in GLSL depends on the GPU model and OpenGL driver version.

Most GPUs seem to have a form of "select one of two values" operation that has no branching cost:

n = (a==b) ? x : y;

and sometimes even things like:

if(a==b) { 
   n = x;
   m = y;
} else {
   n = y;
   m = x;
}

will be reduced to a few select-value operation with no branching penalty.

Some GPU/Drivers have (had?) a bit of a penalty on the comparison operator between two values but a faster operation on comparison against zero.

Where it might be faster to do:

gl_FragColor.xyz = ((tmp1 - tmp2) != vec3(0.0)) ? E : tmp1;

rather than compare (tmp1 != tmp2) directly but this is very GPU and driver dependant so unless you are targeting a very specific GPU and no others I recommend using the compare operation and leave that optimising job to the OpenGL driver as another driver might have an issue with the longer form and be faster with the simpler, more readable way.

"Branches" aren't always a bad thing either. For example on the SGX530 GPU used in the OpenPandora, this scale2x shader (30ms) :

    lowp vec3 E = texture2D(s_texture0, v_texCoord[0]).xyz;
    lowp vec3 D = texture2D(s_texture0, v_texCoord[1]).xyz;
    lowp vec3 F = texture2D(s_texture0, v_texCoord[2]).xyz;
    lowp vec3 H = texture2D(s_texture0, v_texCoord[3]).xyz;
    lowp vec3 B = texture2D(s_texture0, v_texCoord[4]).xyz;
    if ((D - F) * (H - B) == vec3(0.0)) {
            gl_FragColor.xyz = E;
    } else {
            lowp vec2 p = fract(pos);
            lowp vec3 tmp1 = p.x < 0.5 ? D : F;
            lowp vec3 tmp2 = p.y < 0.5 ? H : B;
            gl_FragColor.xyz = ((tmp1 - tmp2) != vec3(0.0)) ? E : tmp1;
    }

Ended up dramatically faster than this equivalent shader (80ms) :

    lowp vec3 E = texture2D(s_texture0, v_texCoord[0]).xyz;
    lowp vec3 D = texture2D(s_texture0, v_texCoord[1]).xyz;
    lowp vec3 F = texture2D(s_texture0, v_texCoord[2]).xyz;
    lowp vec3 H = texture2D(s_texture0, v_texCoord[3]).xyz;
    lowp vec3 B = texture2D(s_texture0, v_texCoord[4]).xyz;
    lowp vec2 p = fract(pos);

    lowp vec3 tmp1 = p.x < 0.5 ? D : F;
    lowp vec3 tmp2 = p.y < 0.5 ? H : B;
    lowp vec3 tmp3 = D == F || H == B ? E : tmp1;
    gl_FragColor.xyz = tmp1 == tmp2 ? tmp3 : E;

You never know in advance how a specific GLSL compiler or a specific GPU will perform until you benchmark it.


To add the to point (even tho I don't have actual timing numbers and shader code to present you for this part) I currently use as my regular test hardware:

  • Intel HD Graphics 3000
  • Intel HD 405 Graphics
  • nVidia GTX 560M
  • nVidia GTX 960
  • AMD Radeon R7 260X
  • nVidia GTX 1050

As a wide range of different, common, GPU models to test with.

Testing each with Windows, Linux proprietary, and Linux open source OpenGL & OpenCL drivers.

And every time I try to micro-optimise GLSL shader (as in the SGX530 example above) or OpenCL operations for one particular GPU/Driver combo I end up equally hurting the performance on more than one of the other GPUs/Drivers.

So other than clearly reducing high-level mathematical complexity (eg: convert 5 identical divisions to a single reciprocal and 5 multiplications instead) and reducing texture lookups/bandwidth, it most likely will be a waste of your time.

Every GPU is too different from the others.

If you'd be working specifically on (a) gaming console(s) with a specific GPU this would be a different story.

The other (less significant for small game devs but still notable) aspect of this is that computer GPU drivers might one day silently replace your shaders (if your game becomes popular enough) with custom re-written ones optimised for that particular GPU. Doing that all work for you.

They will do this for popular games that are frequently used as benchmarks.

Or if you give your players access to the shaders so they can easily edit them themselves some of them might squeeze a few extra FPS for their own benefit.

For example there are fan-made shader & texture packs for Oblivion to dramatically increase frame rate on otherwise barely-playable hardware.

And lastly, once your shader get complex enough, your game almost completed, and you start testing on different hardware you'll be busy enough just fixing your shaders to work at all on a variety of GPUs as it is due to various bugs you wont have time to optimise them to that degree.

\$\endgroup\$
  • \$\begingroup\$ "Or if you give your players access to the shaders so they can easily edit them themselves..." Since you've mentioned this, what might be your approach to wallhack shaders and the like? Honor system, verified, reports...? I like the idea of lobbies restricted to the same shaders/assets, whatever they may be, since stances on max/min/scalable realism, exploits, and so on should bring players and modders together to encourage review, collaboration, etc. I seem to remember this being the way that Gary's Mod worked, but I'm well out of the loop. \$\endgroup\$ – John P May 3 '18 at 10:31
  • 1
    \$\begingroup\$ @JohnP Security wise anything that assumes the client isn't compromised doesn't work anyway. Of course if you don't want people editing their shaders there's no point exposing them, but it doesn't really help all that much with security. Your strategy for detecting things like wallhacks should treat client side messing with things as a low first barrier, and arguably there might be a larger benefit to allow light modding as in this answer if it doesn't lead to a detectable unfair advantage for the player. \$\endgroup\$ – Cubic May 3 '18 at 11:27
  • 8
    \$\begingroup\$ @JohnP If you do not want players too see through walls, don't let the server send them any information about what is behind the wall. \$\endgroup\$ – Polygnome May 3 '18 at 11:48
  • 1
    \$\begingroup\$ That's just it - I'm not against wall-hacking between players who like it for whatever reason. As a player, though, I've abandoned several AAA titles because - among other reasons - they made examples of aesthetic modders while money/XP/etc. hackers went unscathed (who made real money off of those frustrated enough to pay), understaffed and automated their report & appeal system, and made certain the games lived and died by the number of servers they cared to keep alive. I was hoping there might be a more decentralized approach as both a dev and a player. \$\endgroup\$ – John P May 3 '18 at 15:01
  • \$\begingroup\$ No I don't do inline if anywhere. I just do float(boolean statement) * (something) \$\endgroup\$ – Geklmintendon't of Awesome May 4 '18 at 1:49
7
\$\begingroup\$

@Stephane Hockenhull's answer pretty much gives you what you need to know, its going to be entirely hardware dependent.

But let me give you some examples of how it can be hardware dependent, and why branching is even an issue at all, what does the GPU do behind the scenes when branching does take place.

My focus is primarily with Nvidia, I have some experience with low level CUDA programming, and I see what PTX (IR for CUDA kernels, like SPIR-V but just for Nvidia) is generated and see the benchmarks of making certain changes.

Why is Branching in GPU Architectures such a big deal?

Why is it bad to branch in the first place? Why does do GPUs try to avoid to branch in the first place? Because GPUs typically use a scheme where threads share the same instruction pointer. GPUs follow a SIMD architecture typically, and while the granularity of that may change (ie 32 threads for Nvidia, 64 for AMD and others), at some level a group of threads share the same instruction pointer. This means that those threads need to be looking at the same line of code in order to work together on the same problem. You may ask how they are able to use the same lines of code and do different things? They use different values in registers, but those registers are still used in the same lines of code across the entire group. What happens when that stops being the case? (IE a branch?) If the program truly has no way around it, it splits up the group (Nvidia such bundles of 32 threads are called a Warp, for AMD and parallel computing academia, it is referred to as a wavefront) in to two or more different groups.

If there is only two different lines of code you would end up on, then the working threads are split up between two groups (from here one I'll call them warps). Lets assume Nvidia architecture, where the warp size is 32, if half of these threads diverge then you will have 2 warps occupied by 32 active threads, which makes things half as efficient from a computational through put end. On many architectures the GPU will try to remedy this by converging threads back into a single warp once they reach the same instruction post branch, or the compiler will explicitly put a synchronization point which tells the GPU to converge threads back, or attempt to.

for example:

if(a)
    x += z * w;
    q >>= p;
else if(c)
    y -= 3;
r += t;

The thread have a strong potential to diverge (dissimilar instruction paths) so in such a case you might have convergence happen in r += t; where the instruction pointers would be the same again. Divergence can also happen with more than two branches, resulting in even lower warp utilization, four branches means 32 threads get split up into 4 warps, 25% throughput utilization. Convergence however can hide some of these issues, as 25% does not stay the throughput through out the whole program.

On less sophisticated GPUs, other issues can occur. Instead of diverging they merely compute all branches then select the output at the end. This might appear the same as divergence (both have 1/n throughput utilization), but there are a few major issues with the duplication approach.

One is the power usage, you are using much more power when ever a branch happens, this would be bad for mobile gpus. Second is that divergence only happens on Nvidia gpus when threads of the same warp take different paths and thus have a different instruction pointer (which is shared as of pascal). So you can still have branching and not have the throughput issues on Nvidia GPUs if they occur in multiples of 32 or only happen in a single warp out of dozens. if a branch is likely to happen it is more likely fewer threads will diverge and you won't have a branching issue anyway.

Another smaller issue is when you compare GPUs up against CPUs, they often don't have prediction mechanisms and other robust branch mechanisms because of how much hardware those mechanism take up, you can often see no-op fill on modern GPUs because of this.

Practical GPU Architectural Difference Example

Now lets takes Stephanes example and see what the assembly would look like for branch-less solutions on two theoretical architectures.

n = (a==b) ? x : y;

Like Stephane said, when the device compiler encounters a branch it may decide to use an instruction to "choose" element which would end up having no branch penalty. This means on some devices this would be compiled to something like

cmpeq rega, regb
// implicit setting of comparison bit used in next part
choose regn, regx, regy

on others with out a choose instruction, it might be compiled to

n = ((a==b))* x + (!(a==b))* y

which might look like:

cmpeq rega regb
// implicit setting of comparison bit used in next part
mul regn regcmp regx
xor regcmp regcmp 1
mul regresult regcmp regy
mul regn regn regresult

which is branch-less and equivalent, but takes way more instructions. Because Stephanes example will likely be compiled to either on their respective systems, it doesn't make much sense to try to manually figure out the math to remove the branching ourselves, as the first architecture's compiler may decide to compile to the second form instead of the faster form.

\$\endgroup\$
5
\$\begingroup\$

I concur with everything said in @Stephane Hockenhull's answer. To expand on the last point:

You never know in advance how a specific GLSL compiler or a specific GPU will perform until you benchmark it.

Absolutely true. Furthermore, I see this sort of question come up quite frequently. But in practice I have rarely seen a fragment shader being the source of a performance issue. It's much more common that other factors are causing issues such as too many reads of state from the GPU, swapping too many buffers, too much work in a single draw call, etc.

In other words, before you go worrying about micro-optimizing a shader, profile your entire app and make sure that the shaders are what is causing your slowdown.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.