Branch/Cmove and Compiler Optimizations
kristerw.github.io
kristerw.github.io
Let's say you want to measure if code is faster with branch or cmove, so you make a microbenchmark. In that case the branch predictor has little other branches to keep track of, so it definitely has enough resources to predict that branch well.
In a real world program that function may only be called once in a while and the branch predictor may consider other branches more important.
I wonder if cmove has advantages even if your microbenchmark tells you it doesn't. One side effect would probably be that it takes pressure off of the branch predictor, which we have no good way of measuring in microbenchmarks.
There are also plenty of examples of microbenchmarks you can write for this type of code that don't suffer from the problem of artificially high branch prediction. An example used in this article is a function called downHeap which is presumably used as part of heap sort. Searching and sorting are good examples of algorithms that often don't do well with branch prediction. As a simple example, if you're doing a binary search for a random element in a sorted vector you'll expect half the branches to go one way (left of the pivot for the iteration) and half the branches to go the other way (right of the pivot for the iteration) without a predictable pattern, even in a microbenchmark.
The result of this should be that without PGO cmov is preferred, which is the right default (incorrectly picking a cmov is a bit worse than picking a branch, incorrectly picking a branch is catastrophically worse than picking a cmov).
If they're gonna make this behavior the default, I presume they have lots of benchmarks showing it's generally the correct choice..
In theory a sophisticated CPU could convert predictable CMOVs to branches (and some non-diverging unpredictable branches to CMOVs), but IIRC Intel has, since Spectre, guaranteed that CMOV itself never triggers speculation.
Reordering may allow executing independent instructions which follow the cmov, but anything depending on the cmov will have to wait.
It’s one of the reasons compilers avoid cmov relatively aggressively, they can cause pipeline stalls which don’t affect branches.
#pragma avoid_speculation
#pragma constant_time
#define VERY_LIKELY(x) __builtin_expect_with_probability(!!(x), 1, 0.999)
Without this, the result could be like 2, and this is not wanted here.
Still of course if your branch is very predictable, there is little need for cmov.
1. If the values the source registers aren't computed yet (due to prediction, renaming, etc.), then CMOV will need to stall until they're computed, right? And those could be pretty long prediction chains. So I don't follow as how you can regard this as just a 1-cycle thing on any architecture.
2. Didn't Ice Lake come out literally just 1 year ago? "Out of date" seems like quite an exaggeration... I don't have a single machine that new and I don't imagine most people purchase a new computer on an annual basis either.
Still, the advantage of conditional branches is that they do indeed break dependency chains and allow OoO execution, whether that's a win or not depend on the prediction rate of the specific branch and the length of the chain.
2. Well I only checked Agner for Ice (which BTW came out in 2019). But CMOV has had a 1 clock latency since Broadwell (2014). It had been 2 clock cycles for a few generation before. The number of generated uops has also significantly decreased.
Not sure what you're sorry about. The author doesn't seem to have made that mistake. It's not even a few paragraphs in before he says:
"One way that seems natural to get the compiler to generate branchless code is to use the ternary operator, but that does not work."
and later:
"Both GCC and Clang generate IR with branches for ternary operators (even with no side effects),"
Did you read any of the article? It doesn't really go into a lot of depth, but what's "shockingly common" is people who comment without reading.
It's like imagining that using negative integers instead of positive will make your CPU run cooler, or that using a for loop in your code instead of a while loop would get rid of the "hourglass" busy cursor in your program.
The C or C++ programmer is writing programs for an entirely imaginary machine (the "abstract machine") and even on that imaginary machine the compiler is allowed to perform "as if" transformations which change what happens so long as you can't observe the difference in certain ways.
You would need a language in which branchless was a specific category so that the language cares that you didn't write a branch and won't transform what you wrote into something with a branch in it. Neither C nor C++ are that language.
Yeah, but beginner programmers won't be told that. I can imagine even quite advanced programmers may be amazed because many do well in industry without digging deeply into their tools (for better or worse, there's often no need).
A few years ago I discovered that CPUs equally don't do what the code tells them - they do out-of-order to a shocking degree, have store forwarding and shadow registers (code writes a value x to register r1 doesn't mean x gets written to r1) etc. etc. and my jaw was hanging open. Nobody knows anything until they find out.
For example, humans behave as though "universal time" is a thing, even if they know intellectually that this isn't so. The CPU has no choice though, there is and can only be local time. Events definitely happen in order locally but with no larger coherency. So if you have two CPU cores, those aren't the same location and they necessarily don't experience the same time.
When writing a program with concurrency (e.g. threads), your C compiler emits machine code which, based on the author's understanding of the CPU documentation, will perform the necessary dance if you expressed that's what you wanted so that it seems there's a larger coherent sense of time. This is called Sequential Consistency. If you forgot to express that properly or you get it wrong, the C standard says your program has "Undefined Behaviour" because the machine code emitted does something which makes sense locally to each CPU core but may not make any sense to you at all. In general humans cannot reason successfully about what their program does in this situation anyway, it's just a complete head fuck, so the C decision to mark this "Undefined behaviour", anything could happen, is actually a reasonable one.
If it was practical people would do it because it makes it much easier to write programs. So, it's not practical today and yet your parent insists it's possible anyway and I wonder by how much.
But it's about scale in two distinct ways. Obviously these programs are smaller, meaning any clever trick has disproportionate impact on real performance, but also there's less need for abstraction because that's less global complexity to handle. A C64 has 65536 bytes of RAM, you can literally write down what each byte is used for, and your program is likewise smaller so you can write down what every instruction does exactly.
This sort of global view is something a compiler takes advantage of, but is normally not practical for humans. At the scale of a Commodore 64 it is practical.
People scale too. In Linux they can get into trouble if a function X() also happens to do Y 'cos that's not what the function said and nobody keeps all of this in their head. But if your entire software is the work of one guy, he remembers that the X routine also does Y so it's fine.
I guess precision in language is valuable, and I did make a typo by neglecting to type the word "to". I should've said, "Do you think they can't be used as part of an expression which may possibly be optimized into branchless code?".
Thank you for the metaphors about keeping the CPU cool, but I really just wanted to know what the other guy meant by what he said.
if (..) c = 1 else c = 2;
c = .. ? 1 : 2;
That's unusual, C syntax is complex and new users are often very focused on figuring out pointers, you can miss that `= a() && b() || c();` always calls b and c but that `= a() ? b() : c();` only calls one of them depending on whether a is zero.
&& are || are short-circuiting operators in C, so in that example b and c won't always be called either.
It wasn't on purpose, my brain took a shortcut from the eager logical operators I work with more frequently.
The rest of the article isn’t about this at all, so I don’t understand the critique.
Why does every top-level HN comment have to be a critique?