6 ms·
Branch/Cmove and Compiler Optimizations
- puffoflogic 4y agoI'm sorry, but the shockingly common belief that C's ternary operator has anything at all to do with branchless code being emitted is completely unhinged from reality. Making this mistake requires that one fundamentally misunderstand what a [modern optimizing] compiler is and does. Inline assembly and intrinsics aside, the syntax that goes in and the code that comes out are related only by their independent relationship to an abstract machine model.
- xscott 4y ago> I'm sorry, but the shockingly common belief that C's ternary operator has anything at all to do with branchless code being emitted is completely unhinged from reality. 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.
- yxhuvud 4y agoWhat is not obvious is why anyone would think using ternaries would be a "natural" way of writing branchless code.
- xscott 4y agoYou've got "natural" in quotes there, but I honestly don't understand your intent. Do you think ternaries are unnatural? Do think they can't be used generate branchless code? Something else?
- tialaramex 4y agoThey can't be "used generate branchless code" because it's completely the wrong layer. 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.
- zasdffaa 4y ago> even on that imaginary machine the compiler is allowed to perform "as if" transformations which change what happens 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.
- tialaramex 4y agoIt's much worse than that, the CPU is stuck in the real world which is obliged to obey Mother Nature's laws despite the fact - especially at that scale - we find them unintuitive. The abstract machine can have intuitive behaviour because we choose how it works, a real machine not so much. 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.
- zasdffaa 4y agoBecause if (..) c = 1 else c = 2; will "obviously" map on to a branches whereas c = .. ? 1 : 2; "obviously" corresponds to a cmov. It's a natural mapping, if not necessarily correct mapping with more knowledge.
- IshKebab 4y agoWhy though? Ternary is always introduced as syntactic sugar for if/else.
- zasdffaa 4y agoMy K&R C book agrees with you, but there when you know about cmov, it seems to map cleanly to ?:. It's just my opinion and what I feel. I can't back it up any better.
- monocasa 4y agoBecause it's an single assignment expression dependent on a result that'll probably trivially be in a status flag.
- kzrdude 4y agoWhy not? It's expression oriented and as such seems to be a good way to write it.
- yxhuvud 4y agoUh, because it is just syntax sugar for an if-statement. And those are typically implemented using branches. There may be possible optimizations to make them branchfree in certain cases, but it is certainly not something I'd assume would be the default.
- samatman 4y agoBecause it's syntax which looks like an expression but isn't fully evaluated. 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.
- chaosite 4y agoAm I missing something? && are || are short-circuiting operators in C, so in that example b and c won't always be called either.
- samatman 4y agoNo you're correct of course. I could go back and edit it to be & and |, but I think leaving the easy-for-a-noob to make mistake in actually illustrates the point better. It wasn't on purpose, my brain took a shortcut from the eager logical operators I work with more frequently.
- puffoflogic 4y agoWhat is shockingly common is people who comment without thinking. Nowhere in my comment did I imply that I thought the author of the original article held the position that I was critiquing. And yet you have decided to assume that I did imply that in order to create an opportunity to insult me, to get your internet kicks for the day I suppose.
- deleted 4y ago[deleted]
- stingraycharles 4y agoI think it’s just an introductory example that inexperienced developers may think of, and explains why it’s wrong. The rest of the article isn’t about this at all, so I don’t understand the critique.
- puffoflogic 4y agoWhere's the critique? I understood perfectly well that it was just an introductory example and I chose to comment on the example, not critique the author. (Although it may still be a critique of the author if the example was meant to be plausible, but this isn't the most likely explanation.) Why does every top-level HN comment have to be a critique?
- kzrdude 4y agoWhat's the “corresponding thing” to branch prediction for conditional moves? Is it just speculative execution?
- nikic 4y agoAs far as I know there isn't anything like that for cmovs. The cmov depends on the condition, so it will only be executed once the condition is available. Of course, execution can still continue with instructions that don't need the cmov result. And because there is no branch, which instructions get executed does not depend on the cmov condition.
- gpderetta 4y agowell, the point of conditional moves is to avoid speculation. 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.
- masklinn 4y agoThere isn’t one. Branch prediction allows speculative execution, but cmov just blocks. 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.
- dataflow 4y agoObligatory explanation from Linus: https://yarchive.net/comp/linux/cmov.html https://yarchive.net/comp/linux/cmov.html
- gpderetta 4y agoNote that this specific rant is a bit out of date as these days register-register CMOS has a very short latency (1 clock on Ice Lake for example). Still of course if your branch is very predictable, there is little need for cmov.
- dataflow 4y agoA couple responses: 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.
- gpderetta 4y ago1. When quoting the latency of an instruction, it is customary to quote the latency that the instruction itself adds to a dependency chain. CMOV itself had indeed higher latency on P4 (Although Agner only claims 6 cycles, not 10 like Linus). 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.
- jabl 4y agoWrt #2, there is the additional argument that when selecting compiler optimizations for a -mtune=generic (or equivalent) target, it makes sense to be a bit "forward leaning", as it'll be a while before your work ends up in a released version, and even further time goes by until that compiler release ends up in the hands of users.
- nikic 4y agoLLVM recently introduced a SelectOptimize pass, which is used for select -> branch conversion in the presence of PGO information. This should replace the current non-PGO-aware X86 cmov conversion pass. 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).
- jabl 4y agoIs it the right default? If the vast majority of branches are predictable, then without PGO a branch would be the right choice, no? If they're gonna make this behavior the default, I presume they have lots of benchmarks showing it's generally the correct choice..
- pclmulqdq 4y agoThe vast majority of branches don't fit in the branch predictor, so it is taking no more than a naive guess about them. If you tell LLVM that the branch is likely or unlikely, they shouldn't use a CMOV, and should instead lay out the code so that the naive branch predictor is correct most of the time. Otherwise, the CMOV actually is likely to be beneficial.
- twic 4y ago#define VERY_LIKELY(x) __builtin_expect_with_probability(!!(x), 1, 0.999) What's the "!!" for? I've seen that in JavaScript, but wasn't expecting it in C.
- majke 4y agoIt's to make sure the result is either value 0 or value 1. Without this, the result could be like 2, and this is not wanted here.
- deleted 4y ago[deleted]
- deleted 4y ago[deleted]
- twic 4y agoWhy does it matter, though? This macro just tells the compiler how to compile the branch, right?
- dzaima 4y ago__builtin_expect_with_probability knows nothing about booleans or branches. It assigns a probability for the first and second argument being equal, but 2!=1 while 2 is truthy.
- IshKebab 4y agoPretty much the same thing really. Coerces the value to true or false (or 1/0 in C). E.g. !!2 is 1/true.
- tempodox 4y agoThe author of the macro cannot know what form the argument expression to the `x` parameter will have, and the double Boolean negation (`!!`) forces the result to be a Boolean. Ideally, this will be just the Zero bit in the condition register after `x` has been compared to zero.
- deleted 4y ago
- IshKebab 4y agoI wonder if compilers should have pragmas to control the exact code generation, e.g. #pragma avoid_speculation #pragma constant_time Feels like it might be more reliable that writing C and hoping the compiler does what you expect.
- Asooka 4y agoIt might be better to expose said instructions as special functions, like how SIMD instructions are exposed. Or write part of the code in assembly - choosing cmov over branch is already architecture dependent.
- mhh__ 4y agoI haven't seen any pragmas but GCC has builtins for injecting serialising instructions.
- fefe23 4y agoI'm not sure if the methodology is sound. 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.
- viraptor 4y agoI think that still makes sense. If you use that branch rarely enough that another one takes its place in the predictor, then it's likely not important enough to matter in the grand scheme of things. Cmov -vs- branch will be most important in stream processing / tight loop. When it's "once in a while" then who cares?
- terrelln 4y agoIt can still matter. You can have a common function that is inlined everywhere that takes a ton of CPU in aggregate, but each callsite is small. E.g Map::find().
- eklitzke 4y agoYour point about branch prediction working better in a microbenchmark than in real code is true in some scenarios. But it's also the case that if the code is called infrequently enough in the real program that it doesn't get good branch prediction it may not be worth optimizing, since that may mean it's not actually on a hot path. 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.
- chavvithakur 4y agospecific rant is a bit out of date
- hoseja 4y agoWho thinks ternary operator has anything to do with branchless and isn't only a sugar?