7 ms·
“Pack it in, mathematicians, someone owes LLVM a million bucks”
- detaro 5y agoWould be news to me that mathematicians consider maths to work like C++ language semantics. (endless loops that don't "make progress" are UB, so it can optimize them away)
- AnIdiotOnTheNet 5y agoThat sounds like a really great way to create bugs and hide the cause from the programmer. Why does anyone think this is a good idea? I'm not asking rhetorically, clearly people do think this is a good idea, I just can't fathom why.
- tsimionescu 5y agoThis allows compilers to optimize by reordering code before/after a loop. Without this, the compiler would only be allowed to move code around the loop if it could prove the loop terminates. By contrast, with this UB, the compiler is allowed to do this move if the loop is not doing IO or accessing volatile memory locations. I'd also note that this particular footgun only exists in C++, the C standard allows loops that never terminate and never do IO or volatile memory access.
- AnIdiotOnTheNet 5y agoI mean sure, if I let the compiler do whatever it wants to my code in order to make it faster it'll make it faster, but then it probably won't do what I want it to do. I don't understand why that's acceptable.
- foxfluff 5y agoA lot of people want programs to be optimized instead of naively executing everything as it appears in the source code. Do you think that's acceptable? I think it's easier to define in a standard what's conforming behavior than it is to exactly and precisely define all the possible optimizations a compiler may (or may not) perform. So "undefined behavior" is a decent starting point. Exceptions can be added later, but if you try to spec all allowed optimizations in advance, the spec is going to be massive and also a massive burden.
- AnIdiotOnTheNet 5y ago> A lot of people want programs to be optimized instead of naively executing everything as it appears in the source code. Do you think that's acceptable? Yeah, my problem isn't that optimization is changing the code per-se, it's that it is introducing a non-obvious bug by doing so. Ostensibly that loop either returns true or never returns. What if it were provided a number that would never return (assume this is possible given the algorithm provided), but because of the "optimization" now returns true? It literally gives us the wrong answer.
- foxfluff 5y agoI believe it to be the case that any optimization in conjunction with a non-conforming program can lead to a subtle or hard-to-understand bug, including giving literally the wrong answer. So what is the solution? Disallow optimization, or go to hellish lengths to write a hard-to-follow spec that only permits optimizations that do not surprise people? On the other hand, it is not hard for me to incorporate into my mental model of a language that a program should eventually "do something" and if it doesn't, it is literally a wrong program. In fact, that's exactly what I thought when I saw the code in question. Before even realizing what it is about: I read it like a normal program, I saw that it can only ever return true, therefore that code can do only one thing, and all that fluff in there does not impact the end result. So I don't think it's particularly non-obvious, but it does require something from the reader. I'm ok with that, there's a lot in C and C++ you can't just assume. I call this a "weird program." It's trying to brute-force an answer out of the computer, but it's the kind of an answer that may or may not ever come. Hardly unlike a program that tries to answer the halting problem. Not necessarily an illegitimate program (bruteforcing is a legitimate way to find answers), but not the kind of thing you'd put inside a normal application. So I'm not concerned about normal applications running into this issue much. If a normal application could go into an infinite do-nothing loop, that is almost definitely a bug -- a literally wrong program. The optimization here only changes how that wrongness manifests, which is expected for UB & optimizations. I do like that C gives you the escape hatch of using a constant controlling expression if you really want a true "potentially-infinite" loop.
- Thiez 5y agoOstensibly as a programmer you know the semantics of your programming language, so the compiler isn't doing anything unexpected here ;) So from its perspective it is not doing anything unexpected to your code. I think the real problem here is that people underestimate the complexity of C and C++. It often feels like it would be easy to guess what the assembly would look like for some snippet of C/C++ code (especially when it's not using any C++ features, such as the loop in the article) when we really should be thinking in terms of the abstract machine that the standard defines.
- AnIdiotOnTheNet 5y ago> Ostensibly as a programmer you know the semantics of your programming language, so the compiler isn't doing anything unexpected here ;) So from its perspective it is not doing anything unexpected to your code. I just don't think having 'gotcha' rules the compiler exploits to do whatever it wants regardless of programmer intent is a good idea, and that's how C/C++ treats UB. UB should be a compiler error and force the programmer to specify what they want the result to actually be so there are no assumptions on the programmer end and no surprises from the compiler.
- Denvercoder9 5y agoThis happens because (paraphrased) the standard dictates that loops without side-effects eventually terminate, and all other programs have undefined behaviour. You can't turn hitting that undefined behaviour into a compiler error, as distinguishing between the two requires solving the halting problem. You can remove the whole assumption, but that limits the optimization capabilities of the compiler. That gives a trade-off: do we want actual infinite loops, or do we want better optimizations? The second seems more useful to me, even though it might sometimes give surprising behaviour for the programmer.
- AnIdiotOnTheNet 5y ago> You can't turn hitting that undefined behaviour into a compiler error, as distinguishing between the two requires solving the halting problem. That's a fair point, but it still feels wrong to me that the compiler can throw away large chunks of code and change the outcome of the function silently.
- tsimionescu 5y agoWell, in this particular case, there are two possible options: the loop either terminates, or your program will forever more do nothing observable other than producing heat. In the first case the compiler is right, in the second case your program was not doing anything possibly useful anyway. So, what's the actual harm?
- AnIdiotOnTheNet 5y agoIf the loop infinitely looping was a bug caused by not writing the function correctly, that bug is now a lot harder to find.
- UncleMeat 5y agoI'm not certain that "the program should do roughly what the author expects in the face of arbitrary program incorrectness" is a thing that works in general. What should your program do if you overflow a 32 bit signed integer? What if you overflow a 64 bit signed integer? Should it do the "expected" thing and wrap according to two's complement? How do you intend to do that efficiently in a portable manner? This rabbit hole can be chased forever until you are left with every C++ implementation being a full blown interpreter.
- tsimionescu 5y agoWhile I agree with your statement in general, I think this is not a good example. Integer arithmetic is two's complement on all platforms of any interest from the last 30+ years, and unsigned integer overflow is already well defined in the standard. It's just an arcane decision to keep signed integer overflow UB as a performance hack. This is especially true given that (a) there is no standard compliant way of checking if you had overflow, and (b) the most pedantically correct way of looping over arrays and such uses an unsigned type (size_t), negating the usual claims about optimization opportunities.
- UncleMeat 5y agoUnsigned integer overflow is well defined. And because of this, you see worse performance when working with unsigned integers in many cases, because the compiler needs to stick instructions in there to catch overflow at the appropriate width. It cannot just use hardware flags because that 32 bit unsigned integer needs to wrap correctly on both 32 bit and 64 bit machines. Thus the word "efficiently" in my comment. By requiring weird and almost certainly buggy behavior to be defined, you require the program to behave more like an interpreted program, with associated performance costs.
- floxy 5y agoSounds like you might be interested in Friendly C: https://blog.regehr.org/archives/1180 https://blog.regehr.org/archives/1180
- UncleMeat 5y agoThe assumption is that programmers don't actually want to write infinite loops that do nothing but spin. UB, in most cases, is also well aligned with a typical programmer's definition of "is a bug".
- rrss 5y agoI think C11 and later have similar forward progress requirements as C++11 and later, C just has an additional exception for loops with constant conditions.
- foxfluff 5y agoN1570 "An iteration statement whose controlling expression is not a constant expression, that performs no input/output operations, does not access volatile objects, and performs no synchronization or atomic operations in its body, controlling expression, or (in the case of a for statement) its expression-3, may be assumed by the implementation to terminate." Doesn't seem like UB but optimizing effectless loops out is permitted.
- alisonkisk 5y agoIt only breaks programs that do nothing forever, which is not useful
- cjfd 5y agoIs it actually true that endless loops are undefined behavior? This statement does not make sense at face value. I am aware that sometimes UB is used to throw away code, but is an endless loop really UB? Anyway, compiling while(true); in g++ with -O4 just yields a program that runs forerver....
- detaro 5y agoCompilers choose to not remove it in this case, probably because there is no clean way of making assumptions that provide a way out, unlike in the example from the link, but the core point is as I mentioned "making progress", specificall< the Progress guarantee (https://en.cppreference.com/w/cpp/language/memory_model#Progress_guarantee https://en.cppreference.com/w/cpp/language/memory_model#Prog...) In a valid C++ program, every thread eventually does one of the following: * terminate * makes a call to an I/O library function * performs an access through a volatile glvalue * performs an atomic operation or a synchronization operation It's fairly obvious how a loop that has none of these side-effects is thus a target to get turned into one that's guaranteed to terminate.
- gizmo686 5y agoAn infinite loop without any side effects.
- shusaku 5y agoOptimize our an infinite loop for infinite speed up!
- folli 5y agoOkay, can somebody explain?
- davikrr 5y ago"LLVM considers infinite recursion to be UB, so the only valid way for this function to execute is to return true"
- Winsaucerer 5y agoWhat does 'UB' stand for?
- the_only_law 5y agoUndefined Behavior
- loeg 5y agoUndefined Behavior.
- jasode 5y ago>"LLVM considers infinite recursion to be UB, Not sure why he used the word "recursion" since collatz() is not calling itself.
- tpush 5y agoHe means the general concept of recursion, of which looping is an implementation, so to speak.
- forgetfulness 5y agoIt's in the computability theory sense, since compilers and language specifications are symbolic math-heavy, and in math you model all these things as recursive functions, the terminology is applied uniformly.
- tomhallett 5y ago
- deleted 5y ago[deleted]
- muldvarp 5y agoWell, first of all, Collatz isn't one of the millenium problems. Secondly, as others have already explained, endless loops are UB and optimized away, but, thirdly, even if they weren't, C++ integers are more like Z/nZ than Z and checking if Collatz holds in Z/nZ is rather trivial.
- stephencanon 5y ago> C++ integers are more like Z/nZ This is an widely-held misconception, but C++ signed integers are _nothing_ like Z/nZ. Unsigned integers are (except for division), and machine arithmetic often is, but in the C++ abstract machine, signed overflow is undefined behavior.
- vlovich123 5y agoThe snippet on Twitter uses unsigned.
- stephencanon 5y agoYes, it does.
- jasode 5y ago>, endless loops are UB and optimized away That soundbite also repeats/paraphrases what thread author Joe Groff said "LLVM considers infinite recursion to be UB," But... the key is infinite loops without side effects can be optimized away. Endless loops even without a provable termination (The Halting Problem) are not UB. But in this case, the value 'x' has a side effect of determining what bool of true/false value to return. That while() loop does not look like it's free of side effects.
- bidirectional 5y agoThe only return statement returns a hardcoded true.
- agent327 5y ago
- ColinWright 5y ago(a) The test is the wrong way round for the Collatz Conjecture; (b) The Collatz Conjecture isn't one of the Millennium problems; (c) It's using bounded numbers in the range where the Collatz Conjecture is known to be true; (d) It seems reasonable to say "If this routine exits then the value will be "true"; (e) None of what I say here is deep or new, so when people get excited about this sort of thing it makes me wonder what I've missed. So ... what have I missed?
- lostcolony 5y agoThe joke.
- cies 5y agoSavage. I dont often laugh loud reading HN. Today I did. Thanks.
- cabaalis 5y agoI've only seen Veretasium YouTube video on this a few days ago, and I'm not a mathematician. Is the joke that LLVM has solved the mystery by optimizing out what it decided is an infinite loop?
- junon 5y agoYes.
- Thiez 5y agoThe C++ standard allows compilers to assume that loops terminate. Since there is only one way to exit the loop (`return true;`) the compiler can assume that this line will eventually be reached. Since the rest of the loop has no side effects, the compiler can optimize it out. So the compiler doesn't actually need to figure out if the loop is infinite or not.
- Denvercoder9 5y ago> The C++ standard allows compilers to assume that loops terminate. Technically, it doesn't, but it requires programs to make forward progress, which is defined as either terminating, calling I/O functions, accessing a volatile variable or performing an atomic or synchronization operation. Infinite loops that'll eventually do one of these are perfectly valid C++ and don't have to terminate.
- hevalon 5y agoFor anyone that wants to have some background context on the problem statement (3x+1), Veritasium has made a great explanation [1]. [1] https://www.youtube.com/watch?v=094y1Z2wpJg https://www.youtube.com/watch?v=094y1Z2wpJg
- deleted 5y ago[deleted]
- abetusk 5y agounsigned __int128
- deleted 5y ago[deleted]
- nickcw 5y agoC++ doing infinite loops in zero time!
- cannabis_sam 5y agoIf only c++ and llvm constituted a proof assistant..
- lou1306 5y agoSomewhat related: a similar program [1] is part of the benchmarks used in the annual Software Verification Competition (SV-COMP). Specifically, in the termination analysis suite. Maybe they secretly hope that some tool, someday, will spit out a correct proof? :) [1] https://github.com/sosy-lab/sv-benchmarks/blob/svcomp17/c/termination-crafted/Collatz_unknown-termination_false-no-overflow.c https://github.com/sosy-lab/sv-benchmarks/blob/svcomp17/c/te...