Using "else if" is a valid optimization in general, but not necessarily when your target is a branchless program. Using "else if" may help in some cases, but you must have in mind exactly which CMOV instructions will be generated by the compiler, to be sure that there is any improvement, i.e. any reduction in the total number of CMOV instructions, and that you are not increasing the length of some chains of dependent instructions (leading to a greater latency).
Some examples:
1. Branches with dependencies.
static void minMax(u8* pxmin, u8* pxmax, const u8* xs, size_t n)
{
const u8 init = n > 0u ? xs[0] : (u8)0u;
u8 xmin = init
u8 xmax = init;
for (size_t i = 1u; i < n; ++i)
{
const u8 x = xs[i];
if (x < xmin) { xmin = x; }
else if (x > xmax) { xmax = x; }
}
*pxmin = xmin;
*pxmax = xmax;
}
2. Branches w/o dependencies static void minMax(u8* pxmin, u8* pxmax, const u8* xs, size_t n)
{
const u8 init = n > 0u ? xs[0] : (u8)0u;
u8 xmin = init
u8 xmax = init;
for (size_t i = 1u; i < n; ++i)
{
const u8 x = xs[i];
if (x < xmin) { xmin = x; }
if (x > xmax) { xmax = x; } /*not doing else if*/
}
*pxmin = xmin;
*pxmax = xmax;
}
Compiling with auto-vectorization enabled (-O3 for most versions of GCC, and I was using -march=native on a Zen1 AMD CPU, so AVX2 capable), version 2 is 0.05x the runtime of the version 1 (so a lot faster). Version 2 disassembly will show lots of “packed” vector instructions.3. Branchless
inline u8 minBranchless(u8 x, u8 y)
{
return x * (u8)(x <= y ? 1u : 0u)
+ y * (u8)(x > y ? 1u : 0u);
}
inline u8 maxBranchless(u8 x, u8 y)
{
return x * (u8)(x >= y ? 1u : 0u)
+ y * (u8)(x < y ? 1u : 0u);
}
static void minMax(u8* pxmin, u8* pxmax, const u8* xs, size_t n)
{
const u8 init = n > 0u ? xs[0] : (u8)0u;
u8 xmin = init
u8 xmax = init;
for (size_t i = 1u; i < n; ++i)
{
const u8 x = xs[i];
xmin = minBranchless(xmin, x);
xmax = maxBranchless(xmax, x);
}
*pxmin = xmin;
*pxmax = xmax;
}
Version 3 is probably a better comparison for the code from the article — there are only 1 or 2 joystick direction vectors that need normalization, so perhaps not enough to show major vectorization benefit, or to even prompt compiler auto-vectorization. Version 3 will most likely be compiled into cmov instructions on x86_64, which are branchless, but branches can still be better, if they can be predicted well. The test data I used was random, so cmov should be expected to be beneficial.Last time I ran comparisons, Version 2 was 0.07x the runtime of Version 3, so Version 3 was not that much faster than Version 1, but still a good improvement.
As a final note, I should say I’m not a fan of relying on compiler auto-vectorization. If you depend on the performance of vectorized code (and vectorizing code is one of the best optimizations out there), then I’m a fan of explicitly vectorizing. SSE2 is in nearly 100% of relevant x86_64 systems (first coming out in 2003). If you’re targeting consumers, AVX is almost certainly worth it. If you’re writing server code, you should be taking full advantage of AVX2 and maybe 512. For arm, NEON is the current vector extension of relevance, and you can polyfill with DLTcollab/sse2neon or something like that, until you go native. Writing vectorized code using SIMD intrinsics (#include <immintrin.h>) is preferable. Especially since compilers just cannot know how to auto-vectorize a lot of floating point code, because of strict assumptions about requirements around non-commutativity, so they almost never generate packed FMADDs.
As for the article code, I wouldn’t make any assumptions about whether the compiler is generating branches or cmov-s. I’d guess cmov-s would be faster, but I haven’t really thought about it. All I’ll say is that turning a lot of `if`s into `else if`s would make it impossible to generate cmov-s, and chaining branches just to avoid assigning to a local that’s almost certainly in a register is only going to make branching slower.
Not nearly, exactly 100%. The 64-bit ABI specifically requires SSE2 support.
It's 100% of what matters, so in practice I'm in full agreement with you.
mov rax,rbx
test rcx,rcx
jnz L1
mov rax,rdx
L1: ret
A cmov instruction is a conditional move. It says, based on specific control flags, do a mov, otherwise do nothing. mov rax,rbx
test rcx,rcx
cmovz rax,rdx
ret
The conditional move is not really branching in the classic meaning of the word, because there is no jump (the instruction pointer unconditionally moves forward to the next instruction).Branches, even well-predicted ones, can hurt performance, especially if the jumped to code is not in cache (needs to be fetched). More detail can be found in this nice top-to-bottom video from Casey Muratori, which goes over modern CPU architecture (it's nothing too fancy, I think every person doing optimization should know this stuff): https://www.youtube.com/watch?v=8VakkEFOiJc
You can imagine the compiler generating either assembly from if style code or from ternary style code. Writing the arithmetic ternary style just happens to nudge the compiler into using cmov-s more often than other ways. For simple cases, a smart enough compiler could generate cmov-s from the if-else case as well, but it's not smart enough for even toy examples. Never mind that cmov-s are not unconditionally better -- a well-trained branch predictor is faster. The question is if your data is conducive to that or not -- something the compiler may never infer. So we're left to encode such information very indirectly via the code patterns, or via all sorts of __builtin_expect style intrinsics.
This all goes to show that C is no longer portable assembler, and there are all sorts of crucial resources on the CPU (cmov, SIMD, etc.) that may go unused based on slight differences in the C code (e.g., even little things that might seem correct, like using unsigned for an accumulator, can ruin its ability to generate cmov-s).
Compilers are really good at turning code that multiplies by a constant into a weird mov and lea that's cheaper than a mul, but they're still very spotty on everything else, and "everything else" covers a huge amount of the stuff that has made CPUs faster in the last 15+ years. Understanding your specific platform target(s) is still crucial if you want to do better than just "get lucky with the compiler sometimes".
- Use else if to avoid uncessary condition checking.
- Only check for xneg / yneg if outx / outy are non-zero.