“Pack it in, mathematicians, someone owes LLVM a million bucks”(twitter.com)

131 pointsby dejawu5 tahun yang lalu88 comments

“Pack it in, mathematicians, someone owes LLVM a million bucks”

https://twitter.com/jckarter/status/1428093469755527168

92 comments

ColinWright5 tahun yang lalu

(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?

stephencanon5 tahun yang lalu

(a) part of the joke

(b) the Millennium problems are not the only million-dollar prizes in mathematics

(c) part of the joke

(d) part of the joke (and part of the C++ standard)

ColinWright5 tahun yang lalu

(b) There are other prizes, but I'm not aware of any others worth a million dollars. Do you have any pointers? A quick interwebs search didn't turn up anything, but they might just be being swamped by the results with the Millennium Problems.

tpush5 tahun yang lalu

> A quick interwebs search didn't turn up anything [...]

Searching 'collatz conjecture prize' quite literally puts a prize of a bout 120MM Yen (~ $1MM) as the top result.

ColinWright5 tahun yang lalu

Hah! I didn't search specifically for that, I was searching for bounties in general.

Thanks.

ithinkso5 tahun yang lalu

There is also a Beal Conjecture[0] worth a million

[0] https://en.wikipedia.org/wiki/Beal_conjecture

ColinWright5 tahun yang lalu

My initial search for bounties didn't turn up that one, either. I wonder if my connection(s) with Erdos have polluted my search history, so it was showing me mostly those, and not showing me this.

<shrug>

Thanks for finding this and letting me know, I've learned something.

lostcolony5 tahun yang lalu

The joke.

cabaalis5 tahun yang lalu

I'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?

WJW5 tahun yang lalu

LLVM optimizes out the infinite loop, because the C++ standard defines that all programs must be able to make forward progress and so removing this loop does not alter the result of the program. Thus, collatz() as written in the tweet will always return true when optimized by LLVM. This says nothing about the conjecture being true or not, it is solely an artifact of the C++ standard being written a certain way.

But also a layer deeper, collatz() takes a uint128 as input and the Collatz conjecture has already been proven to be true for all numbers that would fit into a uint128. So LLVM arrives to the correct answer (`return true`) because of the wrong reason, mathematically speaking.

ludocode5 tahun yang lalu

This doesn't exactly follow the Collatz conjecture because multiplication by 3 will be truncated to a 128-bit unsigned int. It is possible that this truncation causes a loop. Even though the Collatz conjecture has been tested for all numbers in this range, it has probably not been tested with this overflow effect.

plasticchris5 tahun yang lalu

Edit: removing my comment, I misunderstood.

WJW5 tahun yang lalu

Not so, since the fact that it is in the range does not mean it will steadily go downwards. It might have numbers much bigger than the maximum value for a uint128 somewhere in its Collatz sequence and it is possible (though unlikely) that one of those numbers modulo the maximum value for a uint128 is the original number again. (That is, the modulo operation might introduce loops that are not present in the normal Collatz sequence because mathematical integers don't overflow)

Thiez5 tahun yang lalu

The 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.

Denvercoder95 tahun yang lalu

> 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.

HelloNurse5 tahun yang lalu

It optimizes "waste an unpredictable time doing arithmetic without side effects, then return 1" to "return 1 without looking at the input". The relation between that machine arithmetic and the Collatz conjecture is irrelevant.

Denvercoder95 tahun yang lalu

I don't think you're responding to the right comment?

junon5 tahun yang lalu

Yes.

cies5 tahun yang lalu

Savage. I dont often laugh loud reading HN. Today I did. Thanks.

ColinWright5 tahun yang lalu

(1)

tantalor5 tahun yang lalu

> The test is the wrong way round

Specifically, Collatz says "if x is even then x /= 2" but the code checks "x is odd".

rtkwe5 tahun yang lalu

> (b) The Collatz Conjecture isn't one of the Millennium problems;

It's not but there are more bounties out there than just the Millenium list. For the Collatz Conjecture specifically there's a 120M Japanese Yen prize which at this moment is a bit more than 1 million USD.

https://www.prnewswire.com/news-releases/bakuage-offers-priz...

ColinWright5 tahun yang lalu

(Also commented elsewhere) ... I didn't search specifically for that, I was searching for bounties in general.

Thanks.

yissp5 tahun yang lalu

> (c) It's using bounded numbers in the range where the Collatz Conjecture is known to be true;

The input is an unsigned __int128, and I believe Collatz has only been verified up to 2^68.

jens-c5 tahun yang lalu

Not to mention that the answer by itself is pretty much worthless, but Mathematicians are rather interested in a proof of the conjecture (or its negation).

I get that it is supposed to be a joke, but it kind of falls flat because it misses the point entirely.

gameswithgo5 tahun yang lalu

You have no sense of humor or curiosity about compiler optimization details that led to this, I guess.

For instance not all languages that target LLVM will get this result. That is interesting.

lou13065 tahun yang lalu

Somewhat 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/te...

[deleted]5 tahun yang lalu

cannabis_sam5 tahun yang lalu

If only c++ and llvm constituted a proof assistant..

nickcw5 tahun yang lalu

C++ doing infinite loops in zero time!

detaro5 tahun yang lalu

Would 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)

AnIdiotOnTheNet5 tahun yang lalu

That 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.

tsimionescu5 tahun yang lalu

This 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.

rrss5 tahun yang lalu

I 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.

foxfluff5 tahun yang lalu

N1570 "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.

AnIdiotOnTheNet5 tahun yang lalu

I 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.

Thiez5 tahun yang lalu

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 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.

AnIdiotOnTheNet5 tahun yang lalu

> 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.

Thiez5 tahun yang lalu

Note that the optimization discussed in the article does not actually involve 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.

Many types of UB are not easily detected at compile time, or cannot be detected in advance at all. For instance, prompting the user for an integer and incrementing it by 1 is UB when the user enters the maximum value of an integer. So should the compiler forbid adding two numbers unless you explicitly guard against overflow? Perhaps it should, but the resulting language definitely wouldn't look anything like C.

Besides, it's not that the compiler is going out of its way to screw you over with a 'gotcha' rule, it's just optimizing using the assumption that your program is free of UB. As a programmer it is your responsibility that there is no UB. If you feel there are too many pitfalls you could use a different programming language, lobby the standards organization for a standard that has less UB, or use compiler options to detect it (e.g. ubsan for clang).

Denvercoder95 tahun yang lalu

This 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.

AnIdiotOnTheNet5 tahun yang lalu

> 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.

Blaisorblade05 tahun yang lalu

Throwing away large chunks of code is what optimizers exist for! Sadly, most discussions of UB only show when it "goes wrong" (has surprising results), not when it goes right!

foxfluff5 tahun yang lalu

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?

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.

AnIdiotOnTheNet5 tahun yang lalu

> 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.

foxfluff5 tahun yang lalu

I 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.

AnIdiotOnTheNet5 tahun yang lalu

> 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.

Consider this hypothetical: the loop is only potentially infinite because it is written incorrectly. In testing, I would notice an infinite loop and debugging where that is happening is pretty trivial. When the compiler optimizes that away to just always return true, it has made the source of the bug much more difficult to pin down because the code I asked the compiler to make produces a completely different result than what the compiler compiled.

foxfluff5 tahun yang lalu

I know. I've used C for two decades, I write it professionally today.

Some bugs end up being extremely difficult to debug. I accept that as a fact of life; in exchange, we get pretty decent performance.

Guess what I do when there's a bug I have a hard time pinning down? Recompile with optimizations turned off.

By the way, I don't think I have ever witnessed a bug caused by an accidentally-infinite loop getting optimized out. So making that almost-never-happens situation easier to fix is not worth trading any optimizations for, imo. I'd rather just get a warning from compiler/static analyzer (if the code isn't the way it is due to macro expansion).

UncleMeat5 tahun yang lalu

The 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".

floxy5 tahun yang lalu

Sounds like you might be interested in Friendly C:

https://blog.regehr.org/archives/1180

tsimionescu5 tahun yang lalu

Well, 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?

AnIdiotOnTheNet5 tahun yang lalu

If the loop infinitely looping was a bug caused by not writing the function correctly, that bug is now a lot harder to find.

UncleMeat5 tahun yang lalu

I'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.

tsimionescu5 tahun yang lalu

While 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.

UncleMeat5 tahun yang lalu

Unsigned 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.

alisonkisk5 tahun yang lalu

It only breaks programs that do nothing forever, which is not useful

cjfd5 tahun yang lalu

Is 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....

detaro5 tahun yang lalu

Compilers 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#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.

gizmo6865 tahun yang lalu

An infinite loop without any side effects.

shusaku5 tahun yang lalu

Optimize our an infinite loop for infinite speed up!

folli5 tahun yang lalu

Okay, can somebody explain?

davikrr5 tahun yang lalu

"LLVM considers infinite recursion to be UB, so the only valid way for this function to execute is to return true"

jasode5 tahun yang lalu

>"LLVM considers infinite recursion to be UB,

Not sure why he used the word "recursion" since collatz() is not calling itself.

forgetfulness5 tahun yang lalu

It'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.

tpush5 tahun yang lalu

He means the general concept of recursion, of which looping is an implementation, so to speak.

tomhallett5 tahun yang lalu

How does LLVM decide this loop is unbounded? Is any `while(true)` loop considered UB and therefore replaced with `return true` or is there more advanced introspection of the ast (some limited set of the halting problem)?

detaro5 tahun yang lalu

It checks how the loop can be exited, assumes that the loop must exit and thus take the code path that exits it, and then applies optimizations to remove everything it doesn't need to find the result.

andrewaylett5 tahun yang lalu

Which isn't quite right: the C++ spec allows the compiler to assume that a loop without side-effects will terminate. And the only way the loop terminates will be by returning true.

Winsaucerer5 tahun yang lalu

What does 'UB' stand for?

loeg5 tahun yang lalu

Undefined Behavior.

the_only_law5 tahun yang lalu

Undefined Behavior

GuB-425 tahun yang lalu

The Collatz conjecture is saying that the programmed algorithm will eventually terminate and return true. Here the compiler optimized the code to always return true. Therefore the author jokingly assumed that the compiler must have proven the Collatz conjecture and the authors should be rewarded a million dollars.

In reality, the reason is that out of the two outcomes: true or infinite loop, the infinite loop violates the standard, and therefore, the result must be true. Another way to see it is that the only way for the code to be valid is if the programmer knows that the Collatz conjecture is true, and the compiler trusts the programmer, saying that the compiler knows the answer to the Collatz conjecture is a kind of circular reasoning.

There are other issues here: the numbers are bounded (a 128 bits integer), but the conjecture is not. And no million dollar prize have been assigned to this problem (it is not one of the millenium problems). Also, an infinite loop is not a result, it is actually the textbook example of an undecidable problem.

josephcsible5 tahun yang lalu

Here's the relevant part of the C++ standard:

> 6.9.2.2 Forward progress [intro.progress]

> The implementation may assume that any thread will eventually do one of the following:

> — terminate,

> — make a call to a library I/O function,

> — perform an access through a volatile glvalue, or

> — perform a synchronization operation or an atomic operation.

That loop doesn't ever do any of the second through fourth things, and if it didn't return true, then it would never terminate either, so Clang is allowed to assume that it will eventually return true. And since the loop doesn't have any other effects visible outside the function, it can be optimized away entirely.

[deleted]5 tahun yang lalu

muldvarp5 tahun yang lalu

Well, 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.

stephencanon5 tahun yang lalu

> 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.

vlovich1235 tahun yang lalu

The snippet on Twitter uses unsigned.

stephencanon5 tahun yang lalu

Yes, it does.

jasode5 tahun yang lalu

>, 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.

agent3275 tahun yang lalu

There is no side effect. The loop only interacts with variable 'x', which is discarded after the function ends. Since it is not observed, there is no side effect.

That leaves only the loop itself, which can run infinitely long (which would be UB, and the compiler is free to assume that won't happen), or it won't, in which case it will always return true. Thus, like them or not, the rules of C++ allow this particular outcome.

I can't say I like this kind of optimisation. Sure, you can construct neat circus tricks with it like this, but other than that it seems pretty pointless for real-world software, and something that could easily turn a simple mistake into a debugging disaster.

bidirectional5 tahun yang lalu

The only return statement returns a hardcoded true.

Denvercoder95 tahun yang lalu

For the purposes of the C++ standard, looping forever is not a side-effect. Only I/O calls, volatile accesses and atomic/synchronization operations are.

gpderetta5 tahun yang lalu

"Side-effect" is a Word of Power that includes IO, volatile, atomics, and little else.

hevalon5 tahun yang lalu

For 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

[deleted]5 tahun yang lalu

abetusk5 tahun yang lalu

   unsigned __int128