5 ms·

Almost certainly makes it worse to add additional conditional dependencies, meaning branches upon branches. Some examples: 1. Branches with dependencies. s

Almost certainly makes it worse to add additional conditional dependencies, meaning branches upon branches. 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.

jesse__ 4y ago
Loved this, thanks.
WithinReason 4y ago
Isn't the ternary operator a branch? Could you just write (u8)(x <= y)?
- dundarious 4y ago
  In x86_64, a branch is typically considered to be a comparison and then a jump to different code (otherwise fall through to following code). Test sets some control flags, and the specific jump type jumps based on the value of a specific control flag. You might have something like: 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 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".

jesse__ 4y ago

Loved this, thanks.

WithinReason 4y ago

Isn't the ternary operator a branch? Could you just write (u8)(x <= y)?

dundarious 4y ago
In x86_64, a branch is typically considered to be a comparison and then a jump to different code (otherwise fall through to following code). Test sets some control flags, and the specific jump type jumps based on the value of a specific control flag. You might have something like: 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 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".