5 ms·

> Only from the user's point of view? No, I'd say it's bad in some absolute sense as well. I didn't say _only_, but I'm not sure about "bad" an an "absolute" s

> Only from the user's point of view? No, I'd say it's bad in some absolute sense as well. I didn't say _only_, but I'm not sure about "bad" an an "absolute" sense. I think it would take a lot of defining the exact question to debate that. For me if it is a bad outcome from the user's point of view, it is already worth discussing. > Can we at least agree that it would be better for the compiler to do what the programmer clearly intended? I guess? It would be pretty neat to work in a language that did what I intended rather than what I wrote, but it will quickly become unsustainable when two people write the same code but intended different things. That problem doesn't apply exactly here since the code is just UB, so the intent doesn't exactly conflict with the actual semantics since there are no semantics. However, the compiler writers have decided to chose the behavior which produces the fastest code. > Maybe this one can be solved with an extra block, or with a better #pragma, or just really good heuristics. IMO, it is largely already solved. If you want signed overflow to behave as, well, signed overflow, use -fwrapv. You pay the small price in reduced optimization opportunities, but you get well-defined behavior on wrapping always (note: wrapping is still almost always a bug!). I think you can make a good argument that this flag should be the default behavior. Certainly, if you were designing a new language you might want to make it the default and maybe C and/or C++ will get there some day. > But the current approach of silent deletion of explicit code for undefined behavior is a terrible pattern! This sentence embodies my main complaint with the endless discussions on this topic. There is no optimization that just removes signed overflows checks, inserted there by a malicious compiler writer. There is a big family of interlocking optimizations, which as a whole are responsible for some spectacular gains in compiled code efficiency. For example there is dead code elimination, which is really important. There is treating code that does something impossible or UB as dead, which is also important (it extends way beyond this signedness stuff). All this conspires to eliminate the _explicit_ overflow check which is the poster-child for compiler misbehavior - but the same optimizations do all sorts of other stuff that you wouldn't have a problem with. Everyone points there finger at this case that looks bad and says "obviously don't do that", but very few explain how. Deep within the guts of the optimizer, you just have IR which probably looks nothing like the code you wrote, there is no distinction between explicit and other code, and no "annotation of intent" to tell anyone what the programmer _really meant_. You have most or all of the major compilers implementing this optimization, yet none of them have apparently solved this simple case of not messing up what the programmer wrote? Probably because it is not at all simple. The solution I'm aware of is to just always treat overflow as defined. I.e., the -fwrapv solution. I'd be fine if compiler makes made it the default - but I guess the competitive pressures mean that compilers generally leave all legal optimizations on at the highest levels, to not be slower than the other guy. I'm OK with that also - at least it's a consistent rule. The compiler-writers position is if you write broken code that invokes UB, you don't get the complain. I think that's often a reasonable approach. In other languages it's just the obvious default: it's just a bit annoying in C/C++ because there are so many things that people think should work, and did work, but are actually UB.

nkurz 8y ago
There is a big family of interlocking optimizations, which as a whole are responsible for some spectacular gains in compiled code efficiency. I agree with you on the "interlocking" part, and the lack of conspiracy, but is there a canonical example of these "spectacular gains"? Particularly, from an optimization that depends on the assumption that the program exhibits no undefined behavior, where the opportunity for optimization disappears if the undefined behavior were instead to be implementation defined. You have most or all of the major compilers implementing this optimization, yet none of them have apparently solved this simple case of not messing up what the programmer wrote? I do not assume that it is simple, only that it is important and desirable. I'm not sure if compiler writers believe it to be impossible to do things better than they do, or just not sufficiently desirable to make it worth the effort. My guess would be that it's impossible to obey programmer intent perfectly in these cases, but possible to do much better than is done currently. The solution I'm aware of is to just always treat overflow as defined. First, I'm using signed integer overflow as the example not because it's a particular focus for me, but because it was central to the examples of linked article. Rather than -fwrapv, my personal preferred practice is to avoid unnecessary use of signed integers. My actual focus is the larger group of optimizations thought to be possible only because one can assume that a program does not invoke undefined behavior. I'd like to see C (and probably C++, although I've thought about it less) reduce the scope of undefined behavior, either at the level of the standard or of individual compilers. I think there is room to allow more cases to be architecturally defined without significant adverse effect. I think the counter-argument is that if this were done, performance would necessarily drop. I haven't yet seen proof of this. It appears that many people seem to assume (as you seem to) that there is no room between "implementation defined" (-fwrapv) and "undefined behavior" (nasal daemons). What I (and I think vyodaiken) are arguing is that there is a level of compiler agnosticism and architecturally defined that can be a useful middle ground. I think this approach (at least for C) offers 95% of the optimization potential while going 95% of the way of honoring the "obvious" intent of the programmer.
- BeeOnRope 8y ago
  > I agree with you on the "interlocking" part, and the lack of conspiracy, but is there a canonical example of these "spectacular gains"? To be clear, when I spoke of spectacular gains, I meant the overall result of all optimizations that modern compilers make, not just the "controversial subset". To see that with pretty much any program, just compare compiling with and without optimizations, or perhaps compare against a 20 or 30 year old C compiler if you can find one. The actual impact of this specific controversial signedness optimization is likely to be small overall, at best low single digit %s but likely even less over a complex piece of software. That's true of many of individual optimizations today. In this case, you can easily A/B test this by compiling with and without -fwrapv. I have seen plenty of cases where the difference is zero within measurement accuracy! In unusual cases, the optimization might speed up some loops by 2x or 3x (an example at [1]), but unless that loop makes up the majority of your application, those speedups will be averaged out by a lot of code that doesn't change. So this signedness thing is not at all an example of spectacular gains, and I didn't mean to imply that it was. Outside of signedness, if you want examples of some significant gains by "exploiting" UB rather than making all behavior [implementation] defined, don't worry: there is no shortage. Just go through a list like [2] and then follow the discussions in many places (including proposals in the standards committees) about what optimizations each UB allows. Certainly not all of the reasons for UB lead to interesting optimizations, but many do. Consider a simple example: deallocating (e.g., free() in C, delete in C++) the same memory twice is UB, as is deallocating memory that was never allocated. You could certainly make this well-defined or implementation-defined instead: just define it to return some kind of error indication or do be a no-op. If you've ever tried to write a high performance memory allocator, you already know that this requirement will kill you. You'll have to be able to distinguish a valid pointer from an invalid one, and you'll probably have to implement your whole allocation scheme in a different way. Despite invalid deallocation and the consequent heap corruption being a major issue pretty much across the spectrum of C/C++ software (way more than a few signedness quirks), you don't hear almost any wailing or gnashing of teeth about how crazy it is when these programs malfunction - it's never going to make the front page of HN. Now, you are probably thinking that obviously they malfunction because they have a bug! They are violating the specification! Well, the same is true of the signedness stuff - it's just a lot more surprising and less expected because (a) it's a relatively new phenomenon (b) like many more people people are aware of the UBness of invalid frees than are aware of the UB of signed overflow (c) if the compiler compiled it in the "obvious" way on "my hardware" it would have worked! To be clear, I think this allocation thing is a completely defensible example of UB. OTOH, I think given modern hardware, and the limited gains, the signedness thing specifically is less defensible: but the solution is there no matter which side you fall on given -fwrapv. > Rather than -fwrapv, my personal preferred practice is to avoid unnecessary use of signed integers. Interesting. I use the opposite approach: I try to use signed for all _numeric_ values (leaving unsigned for "bit strings"), because I'm quite sure that the number of bugs caused by the discontinuity at zero (for unsigned values) is much larger than the number caused by the discontinuity or UB at INT_MIN/INT_MAX. Avoiding bugs is my goal and when you "wrap" a value it's almost always a bug whether the compiler exploited it to do something weird or whether your program carries on with a semantically invalid value. So I while I have heard this "used unsigned since at least it has defined behavior" thing many times, I think it is usually misplaced. Examine a bunch of integers in any program and decide whether the program is correct if they wrap: the answer is almost always no. Weird cases like this were something was specifically trying to detect a wrap and do something are lost in the noise. > My actual focus is the larger group of optimizations thought to be possible only because one can assume that a program does not invoke undefined behavior. I think it is a bit harder than you imagine to define the scope of that. Nearly any optimization relies on the absence of some types of undefined behavior such as wild writes: if you make wild writes defined behavior, you probably won't even be able to keep any variable in a register. You can get there, and still have good performance, but you pretty much need a new language (see Rust or Java, for example). > I think the counter-argument is that if this were done, performance would necessarily drop. I haven't yet seen proof of this. You only need one example, right? See [1]. That's just the last one I ran across and it's actually a new example, the other ones I saw were places where different assumptions could be made about the induction variable. The impact here is 3x the number of instructions in the loop body (ignoring overhead). That said, I totally agree on reducing the scope of UB in the standard. A lot of the UB is here to stay, like wild reads and writes, double deletes, even (I suspect) strict aliasing. A lot of the other UB, however, is just a relic of the hardware around the time C was being standardized. There is little reason not to settle on 8-bit bytes, 2's complement arithmetic for signed and unsigned with the "expected" wrapping, arithmetic left shifts for signed values, etc. The standard may eventually get there, but in the meantime people are already somewhat "opting in" to that world, simply by writing code that assumes a non-deathstation machine, i.e., not using CHAR_BIT, assuming intptr_t has the expected representation, etc. Adjacent standards like POSIX even define a lot of this: if you using POSIX a lot of the weirder possibilities go away because POSIX defines a bunch of things that are left open in the C standard. > It appears that many people seem to assume (as you seem to) that there is no room between "implementation defined" (-fwrapv) and "undefined behavior" (nasal daemons). Yeah, that's pretty close to my position on this issue. A more nuanced version would be that I am not personally aware of some middle ground that is better than the current behavior or -fwrapv. More to the point, I never see anything like that presented by the opponents of the current behavior (you have taken the step of suggesting that you think it exists - which already puts you in a small group trying, if barely, to explain how it should work). Most just the claim that the current behavior is really insane with the implication that there is some better way. Some just use and promote -fwrapv as that better way, but many reject it. So what is this better way? You can go back and read various discussion on the compiler dev lists, as I did at one point, and you won't find this better way. These people are smart enough to get us into this situation, so one would imagine they'd be smart enough to least discuss this better way if it exists. You can take a survey of other languages, most more modern and so with the advantage of hindsight, and see what they do. I don't see the solution there either. Of course, some use arguably _better_ behavior like 2's complement wrapping, like Java and probably a lot of others, but that's just -fwrapv. A lot use something heavier-weight like infinite precision integer, which probably wouldn't be appropriate for C/C++. Rust uses a kind of weird mix of wrapping in release builds or trapping in debug builds - I'm not yet sure how I feel about that one. So yeah, you can put me down in the camp of not finding the position of the compiler writers all that unreasonable: they are following the standard, the programs that exhibit this surprising behavior are ill-formed (even if that is surprising), and critically they _offer a flag_ to reverse all of that so that signed wrapping is well-defined and then everything works. I think the primary criticism one could reasonably level is that flag should be opt-out, not opt-in (i.e., wrapping by default). A vague suggestion that there must be a better way, without details, I don't find all that convincing and I think it's reasonable for compiler people to more or less put the topic on the shelf until details are forthcoming. --- [1] https://gist.github.com/rygorous/e0f055bfb74e3d5f0af20690759de5a7 https://gist.github.com/rygorous/e0f055bfb74e3d5f0af20690759... [2] https://blog.regehr.org/archives/1520 https://blog.regehr.org/archives/1520

nkurz 8y ago

There is a big family of interlocking optimizations, which as a whole are responsible for some spectacular gains in compiled code efficiency. I agree with you on the "interlocking" part, and the lack of conspiracy, but is there a canonical example of these "spectacular gains"? Particularly, from an optimization that depends on the assumption that the program exhibits no undefined behavior, where the opportunity for optimization disappears if the undefined behavior were instead to be implementation defined. You have most or all of the major compilers implementing this optimization, yet none of them have apparently solved this simple case of not messing up what the programmer wrote? I do not assume that it is simple, only that it is important and desirable. I'm not sure if compiler writers believe it to be impossible to do things better than they do, or just not sufficiently desirable to make it worth the effort. My guess would be that it's impossible to obey programmer intent perfectly in these cases, but possible to do much better than is done currently. The solution I'm aware of is to just always treat overflow as defined. First, I'm using signed integer overflow as the example not because it's a particular focus for me, but because it was central to the examples of linked article. Rather than -fwrapv, my personal preferred practice is to avoid unnecessary use of signed integers. My actual focus is the larger group of optimizations thought to be possible only because one can assume that a program does not invoke undefined behavior. I'd like to see C (and probably C++, although I've thought about it less) reduce the scope of undefined behavior, either at the level of the standard or of individual compilers. I think there is room to allow more cases to be architecturally defined without significant adverse effect. I think the counter-argument is that if this were done, performance would necessarily drop. I haven't yet seen proof of this. It appears that many people seem to assume (as you seem to) that there is no room between "implementation defined" (-fwrapv) and "undefined behavior" (nasal daemons). What I (and I think vyodaiken) are arguing is that there is a level of compiler agnosticism and architecturally defined that can be a useful middle ground. I think this approach (at least for C) offers 95% of the optimization potential while going 95% of the way of honoring the "obvious" intent of the programmer.

BeeOnRope 8y ago
> I agree with you on the "interlocking" part, and the lack of conspiracy, but is there a canonical example of these "spectacular gains"? To be clear, when I spoke of spectacular gains, I meant the overall result of all optimizations that modern compilers make, not just the "controversial subset". To see that with pretty much any program, just compare compiling with and without optimizations, or perhaps compare against a 20 or 30 year old C compiler if you can find one. The actual impact of this specific controversial signedness optimization is likely to be small overall, at best low single digit %s but likely even less over a complex piece of software. That's true of many of individual optimizations today. In this case, you can easily A/B test this by compiling with and without -fwrapv. I have seen plenty of cases where the difference is zero within measurement accuracy! In unusual cases, the optimization might speed up some loops by 2x or 3x (an example at [1]), but unless that loop makes up the majority of your application, those speedups will be averaged out by a lot of code that doesn't change. So this signedness thing is not at all an example of spectacular gains, and I didn't mean to imply that it was. Outside of signedness, if you want examples of some significant gains by "exploiting" UB rather than making all behavior [implementation] defined, don't worry: there is no shortage. Just go through a list like [2] and then follow the discussions in many places (including proposals in the standards committees) about what optimizations each UB allows. Certainly not all of the reasons for UB lead to interesting optimizations, but many do. Consider a simple example: deallocating (e.g., free() in C, delete in C++) the same memory twice is UB, as is deallocating memory that was never allocated. You could certainly make this well-defined or implementation-defined instead: just define it to return some kind of error indication or do be a no-op. If you've ever tried to write a high performance memory allocator, you already know that this requirement will kill you. You'll have to be able to distinguish a valid pointer from an invalid one, and you'll probably have to implement your whole allocation scheme in a different way. Despite invalid deallocation and the consequent heap corruption being a major issue pretty much across the spectrum of C/C++ software (way more than a few signedness quirks), you don't hear almost any wailing or gnashing of teeth about how crazy it is when these programs malfunction - it's never going to make the front page of HN. Now, you are probably thinking that obviously they malfunction because they have a bug! They are violating the specification! Well, the same is true of the signedness stuff - it's just a lot more surprising and less expected because (a) it's a relatively new phenomenon (b) like many more people people are aware of the UBness of invalid frees than are aware of the UB of signed overflow (c) if the compiler compiled it in the "obvious" way on "my hardware" it would have worked! To be clear, I think this allocation thing is a completely defensible example of UB. OTOH, I think given modern hardware, and the limited gains, the signedness thing specifically is less defensible: but the solution is there no matter which side you fall on given -fwrapv. > Rather than -fwrapv, my personal preferred practice is to avoid unnecessary use of signed integers. Interesting. I use the opposite approach: I try to use signed for all _numeric_ values (leaving unsigned for "bit strings"), because I'm quite sure that the number of bugs caused by the discontinuity at zero (for unsigned values) is much larger than the number caused by the discontinuity or UB at INT_MIN/INT_MAX. Avoiding bugs is my goal and when you "wrap" a value it's almost always a bug whether the compiler exploited it to do something weird or whether your program carries on with a semantically invalid value. So I while I have heard this "used unsigned since at least it has defined behavior" thing many times, I think it is usually misplaced. Examine a bunch of integers in any program and decide whether the program is correct if they wrap: the answer is almost always no. Weird cases like this were something was specifically trying to detect a wrap and do something are lost in the noise. > My actual focus is the larger group of optimizations thought to be possible only because one can assume that a program does not invoke undefined behavior. I think it is a bit harder than you imagine to define the scope of that. Nearly any optimization relies on the absence of some types of undefined behavior such as wild writes: if you make wild writes defined behavior, you probably won't even be able to keep any variable in a register. You can get there, and still have good performance, but you pretty much need a new language (see Rust or Java, for example). > I think the counter-argument is that if this were done, performance would necessarily drop. I haven't yet seen proof of this. You only need one example, right? See [1]. That's just the last one I ran across and it's actually a new example, the other ones I saw were places where different assumptions could be made about the induction variable. The impact here is 3x the number of instructions in the loop body (ignoring overhead). That said, I totally agree on reducing the scope of UB in the standard. A lot of the UB is here to stay, like wild reads and writes, double deletes, even (I suspect) strict aliasing. A lot of the other UB, however, is just a relic of the hardware around the time C was being standardized. There is little reason not to settle on 8-bit bytes, 2's complement arithmetic for signed and unsigned with the "expected" wrapping, arithmetic left shifts for signed values, etc. The standard may eventually get there, but in the meantime people are already somewhat "opting in" to that world, simply by writing code that assumes a non-deathstation machine, i.e., not using CHAR_BIT, assuming intptr_t has the expected representation, etc. Adjacent standards like POSIX even define a lot of this: if you using POSIX a lot of the weirder possibilities go away because POSIX defines a bunch of things that are left open in the C standard. > It appears that many people seem to assume (as you seem to) that there is no room between "implementation defined" (-fwrapv) and "undefined behavior" (nasal daemons). Yeah, that's pretty close to my position on this issue. A more nuanced version would be that I am not personally aware of some middle ground that is better than the current behavior or -fwrapv. More to the point, I never see anything like that presented by the opponents of the current behavior (you have taken the step of suggesting that you think it exists - which already puts you in a small group trying, if barely, to explain how it should work). Most just the claim that the current behavior is really insane with the implication that there is some better way. Some just use and promote -fwrapv as that better way, but many reject it. So what is this better way? You can go back and read various discussion on the compiler dev lists, as I did at one point, and you won't find this better way. These people are smart enough to get us into this situation, so one would imagine they'd be smart enough to least discuss this better way if it exists. You can take a survey of other languages, most more modern and so with the advantage of hindsight, and see what they do. I don't see the solution there either. Of course, some use arguably _better_ behavior like 2's complement wrapping, like Java and probably a lot of others, but that's just -fwrapv. A lot use something heavier-weight like infinite precision integer, which probably wouldn't be appropriate for C/C++. Rust uses a kind of weird mix of wrapping in release builds or trapping in debug builds - I'm not yet sure how I feel about that one. So yeah, you can put me down in the camp of not finding the position of the compiler writers all that unreasonable: they are following the standard, the programs that exhibit this surprising behavior are ill-formed (even if that is surprising), and critically they _offer a flag_ to reverse all of that so that signed wrapping is well-defined and then everything works. I think the primary criticism one could reasonably level is that flag should be opt-out, not opt-in (i.e., wrapping by default). A vague suggestion that there must be a better way, without details, I don't find all that convincing and I think it's reasonable for compiler people to more or less put the topic on the shelf until details are forthcoming. --- [1] https://gist.github.com/rygorous/e0f055bfb74e3d5f0af20690759de5a7 https://gist.github.com/rygorous/e0f055bfb74e3d5f0af20690759... [2] https://blog.regehr.org/archives/1520 https://blog.regehr.org/archives/1520