‹ BackHN Continuity

Thread

C++26: Trivial infinite loops are no longer undefined behaviour

173 points · 290 comments · ibobev

  1. JoshTriplett · · focus · HN ↗
    > When both conditions are met, the loop body is replaced with a call to std::this_thread::yield().

    Insert screaming here.

    An infinite loop, with no library calls whatsoever, gets a system call inserted. That's a horrible surprise waiting to happen.

    The entire concept of the "forward progress guarantee" is broken. An infinite loop should compile to an infinite loop. Nothing more, nothing less.

    1. rcxdude · · focus · HN ↗
      Yeah, this is almost the worst way they could choose to 'fix' the problem.
    2. ameliaquining · · focus · HN ↗
      I'm curious, what exactly do you imagine going wrong here?
      1. rcxdude · · focus · HN ↗
        The biggest headache will probably be it getting emitted in inappropriate contexts: where there is no actual means to sched_yield for whatever reason (bare metal, kernel, whatever). The second is just that the behaviour of the infinite loop changes: suddenly you're getting a bunch of extra system calls from your spinning thread instead of just a high CPU usage, which could disguise the issue or perhaps cause problems for other parts of the system. I don't see a good reason for the transformation: pretty much any time you are writing a bare infinite loop like this you don't want anything else to happen (it's also silly that it only happens with a particular spelling of an infinite loop, keeping the others still undefined).
        1. JoshTriplett · · focus · HN ↗
          "Emitted in inappropriate contexts" is very much one of the shapes I would expect unpleasant surprises to take, yeah. If you're writing code in C, you often need a lot of control over exactly what's happening. You might, for instance, be writing a .so for use with LD_PRELOAD, where it's important that you know everything being called so you can't accidentally recurse. You might be writing code for a sandbox, where you have an allowlist of permitted syscalls.
          1. pjmlp · · focus · HN ↗
            Exact control is only available in Assembly, minus unavoidable hardware flaws, everything else even a minor compiler update might change the outcome of the code.
        2. criddell · · focus · HN ↗
          > suddenly you're getting a bunch of extra system calls from your spinning thread instead of just a high CPU usage

          Isn't the point that the loop was undefined behavior and so the spinning thread might not actually be spinning to begin with? It could be doing anything and sometimes did stuff like run the next block of code.

          If you really want an infinite loop that does nothing (not sure why), you can do that now on any standards conforming compiler with some of the methods Sandor described.

          1. rcxdude · · focus · HN ↗
            It being undefined behaviour before doesn't make all possible definitions of that behaviour equally reasonable. The strangest thing to me is that I don't know who this behaviour definition is for. Infinite loops like this are a pattern that's almost entirely mutually exclusive with situations where a scheduler is relevant.

            I'm not too concerned about it being possible to make a loop at all (there's a lot of ways to add a 'side-effect' that will probably result in the same assembly), I'm concerned with a) the strange unwillingness to just define a sensible behaviour in this case, especially when C already has one (and GCC already in practice implements a slightly different but also perfectly reasonable interpretation, both of which work for all the normal ways someone might write such a loop), and b) the huge amount of existing code which uses this construct because for the most part compilers did not actually cause problems with it.

        3. nicebyte · · focus · HN ↗
          arguably there are already several places in the language where things like this can happen. for example, initializing a static function variable has certain thread safety guarantees (two threads entering the function won't step on each other), and while it's nice to not worry about it, this can certainly be a problem if you're trying to stay close to the metal and not pull in any dependencies.

          > I don't see a good reason for the transformation: pretty much any time you are writing a bare infinite loop like this you don't want anything else to happen (it's also silly that it only happens with a particular spelling of an infinite loop, keeping the others still undefined).

          I'm not disagreeing with you, but two things worth considering are 1) you don't always write loops like that _intentionally_; 2) if a bug like that slips into production system, it would be good to make sure it doesn't starve other threads.

          1. rcxdude · · focus · HN ↗
            This is true. Static initialization will often generate calls to lock functions and that can be a faff to deal with. But I don't see what the point of the sched_yield() is. Using it at all is already a code smell and calling it repeatedly in a tight loop is the kind of thing kernel developers were trying to beat out of application developers decades ago because it just isn't really very helpful (and often actively harmful) with any but the dumbest of schedulers. It's certainly not very useful for avoiding thread starvation.
        4. mitxela · · focus · HN ↗
          Impl specific. If you're building bare metal, pass -ffreestanding so GCC knows it's not allowed to call OS functions.
      2. rfgplk · · focus · HN ↗
        The language is already littered with these "the compiler shall insert" and then a reference to the STANDARD LIBRARY FEATURE N.X. Which means if you're compiling in a freestanding environment half the time you'll get linker errors such as "couldn't find symbol whatever". And what's worse the compiler inserts a call to a function that is LITERALLY STD NAMESPACED. Meaning you have to provide that signature yourself. See how std vector is hardcoded into compare/meta and I can't remember what else.

        This then forces developers to create undefined behaviour because according to the standard you can't namespace std your own functions even though it's required to get it to work.

        1. ameliaquining · · focus · HN ↗
          Freestanding environments specifically don't have to do this, they get a carve-out. (I dunno if this applies elsewhere though.)
        2. mitxela · · focus · HN ↗
          Sounds like a compiler bug that a standard feature implementable in freestanding doesn't work in freestanding.
      3. yk · · focus · HN ↗
        I would expect an infinite loop

            while(true) std::this_thread::yield();
        to be designed to play nice with the scheduler, while I would assume a infinite loop

            while(true);
        to not play nice with the scheduler. Now, I can't really imagine where this matters except for horrible hacky attempts at faking a real time scheduler on windows, but breaking horrible hacky attempts at faking a real time scheduler sounds like the kind of bug you hear about in the evening news.
        1. nicebyte · · focus · HN ↗
          under what conditions would the infinite loop be scheduled over something else after it has run out of its time slice?
        2. rcxdude · · focus · HN ↗
          I would expect them to be the same or for the former to be worse. It's rarely useful to call sched_yield at all, but calling it repeatedly in a loop seems more likely to expose bad behavior in a scheduler than improve the interaction. Schedulers are already perfectly well designed to handle threads trying to take up 100% of the CPU: that's the default state for any CPU-bound task.
      4. 112233 · · focus · HN ↗
        I would expect quite a number of embedded use cases to suddenly break. Yay, free CVEs!
    3. ozgrakkurt · · focus · HN ↗
      But the compilers have to optimize the crap code in big tech codebases by 0.5%, it saves a lot of money.

      Also performance doesn't matter that much and developer time is more important btw, keep using react.

      1. muvlon · · focus · HN ↗
        It's not even about optimizing some big tech codebase by 0.5%. The progress guarantees in particular are in place s.t. Nvidia can choose a certain implementation strategy in Cuda C++ that has "surprising" consequences for users (one thread getting stuck in an infinite loop that never yields can livelock its entire warp) but still get to claim "full C++ standards compliance".
        1. JoshTriplett · · focus · HN ↗
          So let it livelock the entire warp when someone writes an infinite loop. Should we start replacing integer division by zero with INT_MAX so that people aren't "surprised" by their program crashing?
          1. muvlon · · focus · HN ↗
            I mean that's what they did, and that's why there's that UB. All I'm saying is that this is the "weird platform behaviors exist and must be legalized by the standard" kind of UB and not the "we want a 0.5% win for benchmaxxing" kind of UB (the standard has plenty of both).
            1. fc417fc802 · · focus · HN ↗
              No, they didn't. UB is a cop out and inserting yield is just plain bad. Locking up one or more threads in an implementation defined manner would be the outcome of least surprise (I already know it's going to lock up at least the one thread).
              1. mitxela · · focus · HN ↗
                The standards intended interpretation of UB was always intended to be something like "implementation defined, no documentation required" to allow for implementation weirdness, even unpredictable ones. It was compiler authors who decided do abuse this allowance to do really unintuitive things instead of weird platform weirdness.
                1. IcyWindows · · focus · HN ↗
                  100% There are implementations that have sane behavior for "UB" instead of making it an excuse to misbehave.

                  The ISO standard is not the same as a language from a single vendor.

                  1. mitxela · · focus · HN ↗
                    IIRC a lot of it was benchmark gaming between GCC and LLVM.
              2. cryptonector · · focus · HN ↗
                Because one can bleeping see that that's what would happen. Locking up a thread isn't a good thing, but it's a lot better than UB. There was never a need to make this UB.
        2. mitxela · · focus · HN ↗
          Isn't that the strategy for most of the stuff in C++? It's the common denominator of a wide variety of platforms. That's why numbers didn't have to be two's complement and characters didn't have to be ASCII for ages.
        3. mschuetz · · focus · HN ↗
          I don't see the issue. Just let wrong code do wrong things But let it do the expected wrong thing, rather than changing the code to something unexpected.
          1. cryptonector · · focus · HN ↗
            "No." <-- the C++ committee.
          2. Dylan16807 · · focus · HN ↗
            Good luck defining "expected" for most of the more complex cases.
            1. mschuetz · · focus · HN ↗
              Seems trivial to me for infinite loops. Nothing special to specify here, they're already specced by the definition of loops.
      2. vrighter · · focus · HN ↗
        performance doesn't matter.... so datacenters would be equally happy running software that runs half as fast but uses 10% more power?
    4. ibobev · · focus · HN ↗
      > An infinite loop should compile to an infinite loop.

      I think that a compiler option should control this. It can be a nice optimization, but the programmer should be able to opt out.

      1. Xirdus · · focus · HN ↗
        The programmer can opt out by terminating the loop.
      2. WalterBright · · focus · HN ↗
        Every flag that changes the semantics of the code bifurcates the language into two languages.
        1. ibobev · · focus · HN ↗
          If we accept this definition, C++ already seems to be many different languages. At my job, I'm currently fighting floating-point determinism issues across different build configurations, compilers, CPUs, operating systems, and standard library and libm implementations so that snapshot tests pass with the same hashes on all platforms. I can confirm that this is a complete nightmare.
          1. WalterBright · · focus · HN ↗
            Yup. I tried hard to not allow D's behaviors to be changed based on a compiler switch. Yes, we have switches to enable certain features, but not silent behavior changes.

            It's not perfect, but the forest of such switches in C compilers motivated D to not have them.

        2. cryptonector · · focus · HN ↗
          Alternatively every flag that changes the semantics of the code is a workaround for either legacy code no one will fix or language committee decisions that have unintended side effects.
          1. WalterBright · · focus · HN ↗
            Are C/C++ chars signed or unsigned? What a mess!
            1. nrr · · focus · HN ↗
              The state of affairs in C and C++ is abhorrently bad. Not only is there `char` but also `signed char` and `unsigned char`, and the standards seem to leave the signedness interpretation of bare `char` up to the implementation.

              Ada explicitly settled on `Character` being an enumeration type based on a specific character set encoding. When I learned Ada 95, the ARM specified the ISO 8859-1 character set for `Character`, likewise with `Wide_Character` and `Wide_Wide_Character` explicitly settling on 16- and 32-bit implementations of UCS. I wish more language specifications made decisions like this.

              D following suit with tying its `char`, `wchar`, and `dchar` to UTF-8, UTF-16, and UTF-32 is commendable.

    5. saghm · · focus · HN ↗
      I guess given that it was UB before, the compiler was already allowed to put a system call here if it wanted for some reason
      1. fc417fc802 · · focus · HN ↗
        Yes, it was a horrible situation that has been replaced by an only slightly less horrible situation.
        1. saghm · · focus · HN ↗
          I don't totally agree with this. To me, UB is an order of magnitude worse than pretty much anything else, so this is more than "slightly less" horrible. I don't necessarily disagree that this is still horrible, but I also don't write an C++, so I'm mostly just commenting as an outside observer.
      2. chowells · · focus · HN ↗
        Not only that, the code was wrong. The specification is quite clear that correct programs don't cause UB to be executed at run time. If your wrong code now produces wrong results, that's because it's wrong. That your compiler allowed you to get away with it for decades is a compiler bug, not a feature.

        Do I fully believe all of the above? Not exactly. But compiler authors do. Does it make a really good argument to never use C or C++? Yes. If only we had 50 years of optimization work in any language with better semantics.

        1. saghm · · focus · HN ↗
          Yeah, my slightly more verbose take is that a language that requires you to not ever make any mistakes in order to have a program behave in a predictable way is not a particularly good choice of language if you the ability to pick something else.
        2. JoshTriplett · · focus · HN ↗
          The mistake was declaring infinite loops to be UB in the first place.
        3. throwaway786678 · · focus · HN ↗
          > That your compiler allowed you to get away with it for decades is a compiler bug

          That UB was added in C++11.

          1. chowells · · focus · HN ↗
            That sounds like 1.5 decades to me...
        4. TuxSH · · focus · HN ↗
          FWIW while(true) / for(;;) (or any other loop condition that is a true constant-expression) is NOT UB in C, only C++.

          In any case stuff like __asm__ __volatile__("" ::: "memory") prevent such optimizations in the rare case you do need branch-to-self.

        5. classified · · focus · HN ↗
          > don't cause UB to be executed at run time.

          The insidious thing about UB is that it doesn't necessarily have to be executed to wreck your program. UB is not primarily about runtime behavior, it's about how the compiler interprets your code. The behavior that is undefined is your compiler's behavior.

          1. chowells · · focus · HN ↗
            You're right. I didn't enumerate every way UB can make a program go wrong. I'm sure I don't even know every way that can happen. But "UB doesn't happen at run time" is an assumption that lots of "optimizations" are based on.
      3. cryptonector · · focus · HN ↗
        Yes, but now it has to. I guess that's better? than UB, maybe.
        1. saghm · · focus · HN ↗
          Oh, definitely agreed. It's still not great, but it's a lot better than before.
    6. marcosdumay · · focus · HN ↗
      I don't understand your problem. Did you expect your C++ program to get uninterrupted access to the computer? What progression do you think isn't happening there?

      I think you are misinterpreting that. That phrase unambiguously says the loop is preserved on the final binary.

      1. JoshTriplett · · focus · HN ↗
        I expect an infinite loop to be compiled into, for instance, a jump instruction jumping to itself. The OS, if there is any, is welcome to interrupt and context switch. I don't expect code that has no function calls at all to have a system call inserted into it.
        1. marcosdumay · · focus · HN ↗
          Ok, I get this.

          The problem is that what you want is completely against the spirit of the entire language.

          If your point is that C++ should be more like C in general, I can agree with that. But if your point is that C++ should be literal on this specific case, performance be damned, and the rest of it is ok, then no, that's a bad one.

          1. JoshTriplett · · focus · HN ↗
            I was utterly unconvinced that the original infinite-loop UB gave the compiler any important performance optimization, and I'm unconvinced that this is providing useful value to compensate for its surprise. If I wanted a yield in my infinite loop, I'd add one.
            1. mitxela · · focus · HN ↗
              The original UB was to allow the compiler to merge two loops without proving termination.
              1. CamperBob2 · · focus · HN ↗
                What difference does it make? If the loop doesn't terminate, it doesn't terminate, which is almost always a bug, except when it's not. If it does terminate, then great, it terminates.

                Merging a buggy loop with another loop creates... a buggy loop.

                1. teo_zero · · focus · HN ↗
                  Take this example:

                    for (i=0;i<n;i++)
    A[i]=0;
  for (i=0;i<n;i++)
    B[i]=0;
                  It can be conveniently transformed into this:

                    for (i=0;i<n;i++)
    A[i]=B[i]=0;
                  They are exactly equivalent except if the first loop never terminates.

                  Now, the compiler could try to understand if the first loop does or doesn't terminate, and apply or not the optimization accordingly, but Turing tought us that is indeed a hard task!

                  Or it could decide to never apply it, for fear of those rare and usually pathological cases where the first loop doesn't terminate.

                  Or it could decide to apply it by default and accept that in those cases the program does something different than what the source code says. The latter is better known as UB.

                  The third option won, and that's why infinite loops are UB in the standard.

                  1. mitxela · · focus · HN ↗
                    You might ask why it's important that the first loop terminates since in this case the extra side effect would just be a dead store - but if the first loop doesn't terminate then it's possible B is an invalid pointer and then accessing it during the first loop is UB when it shouldn't be. Making a nonterminating loop UB is the patch for this.

                    The standard example is a linked list instead of an array because the compiler can't prove it never has a cycle.

                    1. CamperBob2 · · focus · HN ↗
                      The complaint I have is that for the sake of benchmark wars, UB has been retconned from "The code might not behave the way you want under certain conditions on certain platforms, hopefully you know what you're doing" to "The compiler can do anything it wants, including rickrolling the user."

                      That is no longer undefined behavior in my book. That is defined behavior that just has an unusually-shitty definition.

                      It's all moot anyway given other trends in progress, but... UB, bah humbug. Stop trying to fix problems that no one had. This is why people are clamoring to replace C/C++ with Rust and AI and whatever. The language needed to become more understandable and more predictable in everyday use, and instead it got worse.

                      1. mitxela · · focus · HN ↗
                        Yes.
                    2. imtringued · · focus · HN ↗
                      So you're saying the person you are responding completely failed to make their point clear?

                      Why use a for loop with a bound as an example instead of while loops with linked lists? He or she can prompt an LLM for a better example so laziness doesn't count as an excuse.

                      1. teo_zero · · focus · HN ↗
                        > Why use a for loop with a bound as an example instead of while loops with linked lists?

                        I'm the author of the example. I wanted to keep it as simple as possible, and this is the most common form of for loop. I was sure that HN readers would be clever enough to "map" it to whatever they have in their mind that satisfy the undecidability of the condition.

                        But since you're nitpicking, I haven't specified the types of i and n: i is uint8_t and n is uint32_t. Does it terminate? It depends on the value of n!

                  2. imtringued · · focus · HN ↗
                    Your explanation is completely insane.

                    > but Turing tought us that is indeed a hard task!

                    Analyzing whether a bounded loop terminates is impossible, got it.

                    >Or it could decide to apply it by default and accept that in those cases the program does something different than what the source code says. The latter is better known as UB.

                    But the reason why it lets the compiler fuse the loops has nothing to do with whether the loop terminates or not. The infinite loop UB is just a way of adding more UB and then invoking non infinite loop optimization.

                    We don't know if A[i] aliases with the pointer that stores the address of the B array and note I mean B itself not A and B overlapping. It could also alias with the loop bound. So the first loop must run until completion simply because it could accidentally overwrite a pointer or variable that is used in the second loop.

                    But now that we have infinite loop UB we can ignore all of that and it's not because infinite loops themselves produce optimization potential, it's because more stuff is UB now so the compiler is allowed to break aliasing rules, which is the actual thing that was preventing the optimization. The infinite loop UB is just the permission slip.

                    1. teo_zero · · focus · HN ↗
                      Whenever you write a succinct example or a metaphor to try to explain in a few words a complicated concept, someone will nitpick small details of your construction, thus focusing on the form and missing the spirit!

                      Forget if "i<n" is decidable or not: the sense is that there will always be some loops that the compiler can't determine if it's finite or not.

                      Forget if A and B can alias or not: the sense is having two independent actions that can be executed in the same loop or in two consecutive loops.

                      Let's see... what about the following example, that replaces all a's with @ and all e's with & in a zero-terminated string s?

                        for (char *p=s; *p; p++)
    if (*p=='a')
      *p='@';
  for (char *p=s; *p; p++)
    if (*p=='e')
      *p='&';
                      If a compiler is allowed to assume that the first loop terminates, then it may optimize it to:

                        for (char *p=s; *p; p++) {
    if (*p=='a')
      *p='@';
    if (*p=='e')
      *p='&';
  }
                      Is this explanation less insane?
        2. leni536 · · focus · HN ↗
          A call to a standard library function is still subject to the as if rule. It doesn't have to manifest into a call instruction to a standard library function. Much like memcpy in source code doesn't have to manifest to a call instruction.
          1. fc417fc802 · · focus · HN ↗
            Me: I don't expect to be stabbed.

            You: But you only might be stabbed. It isn't required to happen only permitted.

            1. leni536 · · focus · HN ↗
              A bad but conforming implementation of the standard can screw you over on every line of your program.
          2. ack_complete · · focus · HN ↗
            Yes, but the compiler does have to preserve any observable behavior produced by the call to the standard library function. Being able to omit this inserted yield() by the as if rule would mean that it isn't observable, which would also mean that the compiler could already add or not add it anywhere as needed without changing the behavior of the program. Which would seemingly make the inserted yield() pointless as it would have no effect.
            1. leni536 · · focus · HN ↗
              Arguably the only change to program behavior is to performance characteristics on hosted environments. It does not change any observable behavior otherwise.

              In environments where there are strong forward progress guarantees a busy infinite loop does the same as far as the abstract machine is concerned, as the OS will eventually put the thread to sleep anyway and other threads can make progress. How soon the thread yields is not "observable behavior" (as defined by the standard document).

      2. rcxdude · · focus · HN ↗
        Any program in an OS only gets as much resources allocated to it as the OS allows (OK, in any general-purpose OS written in the past few decades). sched_yield() doesn't actually reduce that allocation in most cases, anyhow: in fact it has a higher chance of increasing the resources that the thread uses spinning in a loop because it's gonna be thrashing the scheduler as well.
    7. usefulcat · · focus · HN ↗
      Yeah, I don't get it either. Like if I wanted to call std::thread::yield() inside an infinite loop, I could, you know, just do that myself?

      An obvious question (that TFA does not address) is, why is the forward-progress guarantee needed? Since that is the ostensible justification for this new invisible behavior.

      1. [deleted] · · focus · HN ↗

        [deleted]

    8. UncleMeat · · focus · HN ↗
      Forward progress guarantee is what allows for conversion between recursion and iteration for performance optimization. Otherwise these have different characteristics (recursion blows the stack, a loop hangs).
    9. amluto · · focus · HN ↗
      I grilled an LLM for a bit to see if it could justify the old forward progress rule. The only thing I got that passed the smell test was that it’s useful for the optimizer to be able to optimize:

          messy_pure_computation();
    some_atomic.store(1, relaxed);
      by moving the store before the computation. (Stronger stores would require additional analysis.)

      I admit I’m unconvinced that this is particularly useful.

      (I got many other ideas that did not pass my personal smell test.)

      1. raphlinus · · focus · HN ↗
        You will find the answer you seek not from an LLM, but from the talk Forward Progress Guarantees in C++ by Olivier Giroux at CppNow 2023. It's a long talk, with lots of details about forward progress, but I've set the timestamp[1] to the infinite loop bit.

        [1]: <a href="https:&#x2F;&#x2F;youtu.be&#x2F;g9Rgu6YEuqY?si=_l9JwKhjvIdFEDEX&amp;t=3819" rel="nofollow">https:&#x2F;&#x2F;youtu.be&#x2F;g9Rgu6YEuqY?si=_l9JwKhjvIdFEDEX&amp;t=3819

        1. amluto · · focus · HN ↗
          I don’t really buy that justification, for three reasons:

          1. Most implementations do not do this automatic cooperative multitasking trick and most users [0] don’t want it done to their code.

          2. The fact that a “step” is guaranteed to happen in finite time is far too weak for most use cases. I’ve done plenty of kernel programming, and a lot of kernels are partially or fully cooperative scheduled. Even somewhat long loops need manually inserted preemption points.

          3. “Finite” can be a very long time indeed. There are literally competitions to see who can make the largest busy beaver machine.

          Put another way, undefined behavior is a sharp line - if code has UB, it has UB and it if doesn’t, it doesn’t. But code being slow is not a sharp line - something can take 1 ns or 1 ms or 1 second or 1 hour or 1 year or 100 years or 1M years, etc.

          A scheduler that fails to schedule a runnable thread in finite time is wrong, but so is a scheduler that fails to schedule it for 100 years or for a week. If it merely takes a minute, then whether it’s right or wrong depends on the situation.

          So if you’re talking about schedulers (which that part of talk mostly is), then I don’t think the ability to say “infinite loop without side effects are UB, so my scheduler is correct if I assume that all side-effect-free loops are finite” is actually useful.

          There are real world examples. At one point, Go only preempted its cooperative threads at certain points, but this was a problem and newer versions of Go can even preempt tight loops. Python, which threads the worst-of-both-worlds middle ground between asynchronous and cooperative preemption, does not allow an infinite loop (in ordinary Python code) to starve other threads.

          [0] Most users of C- or Rust-like languages anyway. Quite a few more managed languages (e.g. Go) are the other way around.

      2. mitxela · · focus · HN ↗
        I thought it was generally so the compiler can merge two computation loops without proving if one of them runs forever .
        1. murderfs · · focus · HN ↗
          Correct. See N1528: &quot;Why undefined behavior for infinite loops?&quot; <a href="https:&#x2F;&#x2F;www.open-std.org&#x2F;jtc1&#x2F;sc22&#x2F;wg14&#x2F;www&#x2F;docs&#x2F;n1528.htm" rel="nofollow">https:&#x2F;&#x2F;www.open-std.org&#x2F;jtc1&#x2F;sc22&#x2F;wg14&#x2F;www&#x2F;docs&#x2F;n1528.htm
          1. amluto · · focus · HN ↗
            That’s actually a fairly good answer. I think I’d summarize the meat of it as: even a non-atomic, non volatile store can be observable in the sense that it can transform data-race-free code into racy code, and the compiler may not do this in a manner that changes observable behavior.

            I’m starting to wonder whether newly designed programming languages should explicitly distinguish probably terminating loops from potentially infinite loops. Lean does, for good reason.

            1. cryptonector · · focus · HN ↗
              Is it a good answer though? How often does this opportunity come up? And if you have two trivial infinite loops one after the other, do you really need to insert `yield()` in order to be able to merge them?
              1. amluto · · focus · HN ↗
                That&#x27;s not the issue.

                Suppose you have some state like this:

                    const node *head1;
    int sum1, sum2;
                And you have:

                    void func()
    {
        for ( int *p = head; p; p = p-&gt;next )
            sum1 += p-&gt;val1;
    
        for ( int *p = head; p; p = p-&gt;next )
            sum2 += p-&gt;val2;
    }
                The compiler really wants to merge the loops (this will be a nearly 2x speedup in this contrived case). In other words, the compiler would like to generate this instead:

                    void func()
    {
        for ( int *p = head; p; p = p-&gt;next ) {
            sum1 += p-&gt;val1;
            sum2 += p-&gt;val2;
        }
    }
                Naively, this optimization looks obviously correct: since there is no synchronization in func(), nothing could validly observe the changes in the order of the stores.

                Here&#x27;s the problem. While C and C++ consider data races to be UB (which is why the compiler is allowed to mess with the order in which potentially shared state is written here), the presence of a data race is still observable in a problematic sense. Suppose thread 2 is doing something like this:

                    while (true) {
        printf(&quot;%d\n&quot;, sum2);
    }
                If thread 1 calls func() while this loop is running, then the program has undefined behavior [0]. Except there&#x27;s a really nasty corner case. If the linked list has a cycle, then func() contains an infinite loop. (All it takes to cause this is head-&gt;next == head.) And, if func() has an infinite loop then, as originally written, sum2 is never modified and there is not a data race. So a sneaky programmer could set up the infinite loop, call func() in one thread, do the printf loop in another thread, and the compiler would need to run that code correctly because it&#x27;s not UB. If the compiler transforms func() as above, then it introduces a data race where none existed, and it&#x27;s a bug.

                But this optimization seems important, and C and C++ sidestep this issue by declaring that func() itself is UB if the linked list contains a cycle. So the transformation does not introduce UB in my example because, in the problematic case, the UB is already there in the original code. Problem solved. Yuck.

                (Realistically the compiler will also probably accumulate the sum in registers and add to sum1 and sum2 at the end. One could quibble that this subsequent transformation invalidates my point, but it&#x27;s easy enough to make a slightly more complex example that doesn&#x27;t have this problem.)

                None of this is to say that I like C and C++&#x27;s solution. It&#x27;s gross. The new C++ change to sort-of-solve it is extremely gross.

                FWIW (and I sort of alluded to this above), there is an IMO much more interesting reason that compilers should care about infinite loops that doesn&#x27;t apply to C&#x2F;C++. In languages like Lean (but borrowing C-like syntax), you can write something like:

                ProofType proof() { &#x2F;&#x2F; some body here }

                The entire basis of the proof model in Lean is that the existence of a &quot;term&quot; like proof() that returns the type ProofType implies that an object of ProofType can be constructed (I think this is usually described as saying that ProofType is &quot;inhabited&quot;). This is pretty concrete -- you could literally run proof() to obtain this object.

                But infinite loops completely break it: you could just write:

                    ProofType proof()
    {
        while (true)
            ;
    }
                (Sure, a clever compiler could reject this particular function. But a clever programmer can out-clever the compiler.)

                So, in Lean, you either need to prove to the compiler that all your loops terminate or you need to mark the function as &quot;partial&quot;, which tells the compiler that it cannot assume that the existence of the function means that the return type is inhabited. This would be a pretty radical change to C and C++, but it would fully solve forward-progress problem :)

                [0] This one is no joke. I can come up with examples that would jump to inappropriate addresses using a construct like this if there&#x27;s a data race -- just replace sum2 with a function pointer.

                1. cryptonector · · focus · HN ↗
                  &gt; But this optimization seems important

                  This is the only point I don&#x27;t fully agree with. I&#x27;d want to know that this optimization is worthwhile. Is it?

                  1. zbentley · · focus · HN ↗
                    Yes. Loops that manipulate data are extremely common. Combining memory accesses and increasing cache locality are extremely beneficial to performance. Transformations that rewrite loops to increase the chances of locality&#x2F;combining are therefore likely to be worthwhile.
          2. cryptonector · · focus · HN ↗
            That is not worth this nonsense.
    10. classified · · focus · HN ↗
      &gt; Insert screaming here.

      I have the suspicion that the members of the C++ standards committee are increasingly not from this planet.

Open on Hacker News to reply ↗

Unofficial Hacker News client; not affiliated with Y Combinator.