Why are comparisons so expensive on a GPU?
GPUs are SIMD architectures.  In SIMD architectures every instruction needs to be executed for every element that you process.  (There's an exception to this rule, but it rarely helps).

So in your MinMax routine not only does every call need to fetch all three branch instructions, (even if on average only 2.5 are evaluated), but every assignment statement takes up a cycle as well (even if it doesn't actually get "executed").

This problem is sometimes called thread divergence.  If your machine has something like 32 SIMD execution lanes, it will still have only a single fetch unit.  (Here the term "thread" basically means "SIMD execution lane".)  So internally each SIMD execution lane has a "I'm enabled/disabled" bit, and the branches actually just manipulate that bit.  (The exception is that at the point where every SIMD lane becomes disabled, the fetch unit will generally jump directly to the "else" clause.)

So in your code, every SIMD execution lane is doing:

compare (a &gt; b)
assign (max = a if a&gt;b)
assign (min = b if a&gt;b)
assign (max = b if not(a&gt;b))
assign (min = a if not(a&gt;b))
compare (c &gt; max)
assign (max = c if c&gt;max)
compare (c &lt; min if not(c&gt;max))
assign (min = c if not(c&gt;max) and c&lt;min)


It may be the case that on some GPUs this conversion of conditionals to predication is slower if the GPU is doing it itself.  As pointed out by @PaulA.Clayton, if your programming language and architecture has a predicated conditional move operation (especially one of the form if (c) x = y else x = z) you might be able to do better.  (But probably not much better).

Also, placing the c &lt; min conditional inside the else of c &gt; max is unnecessary.  It certainly isn't saving you anything, and (given that the GPU has to automatically convert it to predication) may actually be hurting to have it nested in two different conditionals.