28 ms·

Ralf Jung has a blog post looking at some of the claims in this paper [0]. Some hopefully representative quotes: > The paper makes many good points, but I thin

Ralf Jung has a blog post looking at some of the claims in this paper [0]. Some hopefully representative quotes: > The paper makes many good points, but I think the author is throwing out the baby with the bathwater by concluding that we should entirely get rid of this kind of Undefined Behavior. The point of this blog post is to argue that we do need UB by showing that even some of the most basic optimizations that all compilers perform require this far-reaching notion of Undefined Behavior. <snip> > I honestly think trying to write a highly optimizing compiler based on a different interpretation of UB would be a worthwhile experiment. We sorely lack data on how big the performance gain of exploiting UB actually is. However, I strongly doubt that the result would even come close to the most widely used compilers today—and programmers that can accept such a big performance hit would probably not use C to begin with. Certainly, any proposal for requiring compilers to curtail their exploitation of UB must come with evidence that this would even be possible while keeping C a viable language for performance-sensitive code. > To conclude, I fully agree with Yodaiken that C has a problem, and that reliably writing C has become incredibly hard since undefined behavior is so difficult to avoid. It is certainly worth reducing the amount of things that can cause UB in C, and developing practical tools to detect more advanced kinds of UB such as strict aliasing violations. <snip> > However, I do not think this problem can be solved with a platform-specific interpretation of UB. That would declare all but the most basic C compilers as non-compliant. We need to find some middle ground that actually permits compilers to meaningfully optimize the code, while also enabling programmers to actually write standards-compliant programs. [0]: https://www.ralfj.de/blog/2021/11/24/ub-necessary.html https://www.ralfj.de/blog/2021/11/24/ub-necessary.html

gavinhoward 5y ago
>> We sorely lack data on how big the performance gain of exploiting UB actually is. However, I strongly doubt that the result would even come close to the most widely used compilers today—and programmers that can accept such a big performance hit would probably not use C to begin with. Certainly, any proposal for requiring compilers to curtail their exploitation of UB must come with evidence that this would even be possible while keeping C a viable language for performance-sensitive code. There actually is data, [1] and it goes against intuition because it shows that UB makes code slower. It turns out that when programmers are faced with the possibility of UB, they (quite rightly) try to work around it. (In my case, I implemented signed two's-complement arithmetic entirely with unsigned types. I also implemented my own array types, including bounds checks when indexing the arrays.) These workarounds make their code slower, in general. When you think about it that way, it makes sense because programmers almost never want UB in their software, so on average, the software that people care about will work around UB and become slower. UB in C was defensible when platforms were not homogenous and when compiler writers did not abuse the spirit of it. But nowadays, most of it is indefensible because platforms are mostly homogenous, and compiler writers have been abusing UB for "performance." We saw the same thing happen with speculative execution in chips. For years, chip manufacturers got away with lots of tricks to increase performance. Then Spectre and Meltdown were discovered. As a result, a lot of software had to be changed, which resulted in the software slowing down. (Yes, there are now mitigations in chips, but I think those mitigations will be successfully attacked too. I think that it will continue that way until most or all speculative execution is removed.) Likewise, with compilers exploiting UB against the original spirit of UB, which was just to make C easy to port to any architecture, we are probably going to have a reckoning about it in the same way we did Spectre and Meltdown. In a way, we already do, but it's spread out like a thousand paper cuts. Maybe that means that it will stay invisible enough that programmers never wake up; I hope not. tl;dr: compilers exploiting UB actually slows down good code in much the same way that Spectre and Meltdown do. [1]: https://www.complang.tuwien.ac.at/kps2015/proceedings/KPS_2015_submission_29.pdf https://www.complang.tuwien.ac.at/kps2015/proceedings/KPS_20...
- sanxiyn 5y ago
  That data is bullshit. It measures -fno-strict-overflow -fno-strict-aliasing. I in fact agree flipping defaults on these UBs is reasonable, but that is very far from "portable assembler" or UB-free C. THE primary UB of C is out-of-bounds write. Any proposal for UB-free C should address how to compile out-of-bounds write. If you insist out-of-bounds write should compile in "portable assembler" way and reliably corrupt memory instead of allowing compilers to assume it doesn't happen, compilers can't allocate local variables in register. If it's on stack, out-of-bounds write may reliably corrupt stack, so how can it be on register? "Portable assembler" people invariably say "that's not what I meant!" when compiler people raise this issue, but the question is "then what do you mean?" And I am yet to see any good answer.
  - nkurz 5y ago
    Could you you explain your position here more fully? I'm a C programmer mostly in the "portable assembler" camp, and I don't see why insisting on out-of-bound writes to be performed prevents compilers from keeping local variables in registers. I think the difference might be your use of the word "reliably". I don't think anyone in my camp is insisting that the results be reliable in the sense you seem to take for granted. What we want is for the compiler to attempt to do what it's instructed to do, without eliding code based on counterfactual reasoning that assumes the absence of undefined behavior. In the absence of an explicit read that is being ignored, we're generally fine with cached values of local variables being out of date. Maybe you could give an example that makes your point more clearly, and we can see if we actually disagree?
    - sanxiyn 5y ago
      See https://news.ycombinator.com/item?id=30024534 https://news.ycombinator.com/item?id=30024534 (by jcranmer) and https://news.ycombinator.com/item?id=30026095 https://news.ycombinator.com/item?id=30026095 (by me). Does it help?
      - nkurz 5y ago
GoblinSlayer 5y ago
I'm afraid the author as usual confuses the cases when UB produces strange results and when the compiler actively and deliberately exacerbates the results. He also claims gcc interpretation of UB provides a lot of performance. Ironically gcc or clang already do experiments on different interpretation of UB like signed integer overflow and implicit initialization.
- Joky 5y ago
  Can you elaborate on the signed integer overflow and the implicit initialization differences you're referring to?
  - GoblinSlayer 5y ago
    https://reviews.llvm.org/D54604 https://reviews.llvm.org/D54604 https://clang.llvm.org/docs/ClangCommandLineReference.html#cmdoption-clang-fwrapv https://clang.llvm.org/docs/ClangCommandLineReference.html#c...
    - Joky 5y ago
      But these are options, it's not a big deal to me that compiler offers special options for special use cases. It's not clear to me if you are saying that the *default* for clang and GCC differs, aren't they both using `fno-wrapv` by default?
      - GoblinSlayer 5y ago
        These options provide a different interpretation of UB like signed integer overflow and implicit initialization. It's in reference to Ralf's blog post: >I honestly think trying to write a highly optimizing compiler based on a different interpretation of UB would be a worthwhile experiment. We sorely lack data on how big the performance gain of exploiting UB actually is. However, I strongly doubt that the result would even come close to the most widely used compilers today—and programmers that can accept such a big performance hit would probably not use C to begin with. Certainly, any proposal for requiring compilers to curtail their exploitation of UB must come with evidence that this would even be possible while keeping C a viable language for performance-sensitive code. He doesn't know such interpretations are implemented by widely used C compilers.
mzs 5y ago
I really wish we got cc: warning: UB line: 123 file: foo.c
- gpderetta 5y ago
  Compilers will routinely warn if they can detect UB at compile time. The problem is that except in a few trivial cases it is impossible to detect UB at compile time. Even whole program static analysis can only catch a small subset.
- foxfluff 5y ago
  Yeah, it'd be nice if we could solve the halting problem.
- tlb 5y ago
  You can't detect most UB at compile time. LLVM has a system to detect it a runtime. There is a significant performance penalty, but it can be useful during testing. See https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html
  - astrange 5y ago
    It’s not actually that significant compared to something like asan. You can ship software with ubsan enabled if you want to.
- jcranmer 5y ago
  How many warnings do you want for this small function? void oh_the_humanity(int *ptr, int val) { *ptr = val + 1; } Off the top of my head: * UB: ptr may be pointing a float variable. (It's not illegal to assign a float* to an int*, it's only UB when you actually dereference it with the wrong type.) * UB: val + 1 may overflow. * UB: potential data race on writing *ptr. * UB: ptr may be a one-past-the-end-of-the-array pointer, which can be validly constructed, but may not be dereferenced. * UB: ptr may be pointing to an object whose lifetime has expired. * UB: ptr may be uninitialized. * UB: val may be uninitialized. As you can see, UB is intensely specific to the actual data values; it's not really possible to catch even a large fraction of UB statically without severe false positive rates.
mpweiher 5y ago
He doesn't really address any of the claims made, and makes some startling claims himself. For example: > This example demonstrates that even ICC with -O1 already requires unrestricted UB. The example demonstrates nothing of the sort. It demonstrates that ICC uses unrestricted undefined behaviour, not that this is required in any way shape or form. (The only way the word "requires" is reasonable here is that the behavior seen "requires" use of this kind of UB to be present. But that's something very different, and doesn't match with the rest of his use). > writing C has become incredibly hard since undefined behavior is so difficult to avoid No, it has become difficult because compilers exploit UB in insane ways. The platform specific UB that he claims is "not an option" is, incidentally, exactly how UB is defined in the standard: Permissible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message). This was made non-binding in later versions of the standard, so optimiser engineers act as if these words don't exist. And of course there is no reason given for this interpretation being "not an option". Except for "but I wanna". Yes, it's not an option if you really want to exploit UB in the insane ways that compilers these days want to exploit it. But that's not necessary in any way shape or form. > That would declare all but the most basic C compilers as non-compliant. Yes, because by any sane interpretation of the standard they are non-compliant. On a more general note, I find this idea that things are necessary because I want to do them really bizarre.
- gpderetta 5y ago
  sorry, I don't understand, it seems to me that current optimizing compilers are fully compliant with the option of "ignoring the situation completely with unpredictable results". That's how UB exploiting optimizations work: the compiler ignores the possibility that the erroneous case can ever happen and takes into account only all valid states.
  - mpweiher 5y ago
    Apologies, but "ignoring the situation completely with undpredictable results" is the exact opposite of "assuming the situation cannot occur and acting on that assumption". If my program attempts to write outside the bounds of declared array, ignoring the situation (that this is UB) is letting that write happen, and letting the chips fall where they might. How is assuming it cannot/must not happen, and then optimising it away because it did happen "ignoring the situation"??
mlindner 5y ago
I pretty strongly disagree with these quotes you have here. You don't need UB to do optimization, in fact because of UB in C many forms of optimization are impossible in C because of aliasing uncertainty. If things are defined to not alias then even though things are fully defined there is a lot more optimization that can be performed by not reloading variables from memory and instead using local cached-in-register copies of variables. This is why naive Rust can in some cases be faster than naive C (without using of restrict keyword) and this will only improve with time as compilers better support this.
- puffoflogic 5y ago
  > If things are defined to not alias ... What do you call it then when you put aliasing pointers into pointer variables "defined not to alias"? Can you explain how this reduces UB?
  - foxfluff 5y ago
    I think they're trying to say that if your language prevents aliasing (i.e. pointers by definition do not alias and it is impossible to make them alias), then the compiler doesn't need to worry about it. C doesn't prevent aliasing, therefore the compiler has to worry about every case of aliasing that isn't undefined. But it's not the UB here that prevents optimization, it's precisely the fact that aliasing is (sometimes) defined. If it were always UB, the compiler wouldn't ever have to worry about it... but that'd require some interesting changes to the language to keep it usable. Definitely not backwards compatible changes.
    - puffoflogic 5y ago
    - andrewla 5y ago
      > pointers by definition do not alias and it is impossible to make them alias This is equivalent to saying that pointer arithmetic is disallowed. Pointers are by their nature in the C virtual machine offsets into a linear memory space, so for any two pointers, x and y, there exists a c such that (ptr_t)x+c == (ptr_t)y, and thus there can always be aliasing.
commandlinefan 5y ago
I had the same basic thought while reading this: the only alternative here is to interpret this sort of undefined behavior in a "different" way (such as the way the K&R originally interpreted it) and leave it up the programmer to intuit what other assumptions the compiler is making on their behalf. Like... I can assume that the compiler will interpret: if (i++ < i) as mov ax, i inc ax cmp ax, i jge else ... but that's still me making a (reasonable?) assumption. The C spec essentially just says "don't program that way".
- Shikadi 5y ago
  Odd intuition, since you never store i back after incrementing. Also, I believe i++ might increment after the comparison rather than before, vs. ++i incrementing first
  - commandlinefan 5y ago
    You know what I mean.
    - Shikadi 5y ago
      I actually don't, but maybe I just lack enough background knowledge on the discussion to understand your intent
      - saghm 5y ago
        I think they're saying that the assembly translation doesn't store back `i`, whereas the C version does, so it's a not straightforward to assume that the assembly compiled from the C won't do that.
      - commandlinefan 5y ago
        The article talks about a similar code snippet being optimized out by the compiler because i++ can never be less than i originally was (unless you take into account the actual behavior of computers).
scott_s 5y ago
HN thread: https://news.ycombinator.com/item?id=29435263 https://news.ycombinator.com/item?id=29435263

gavinhoward 5y ago

>> We sorely lack data on how big the performance gain of exploiting UB actually is. However, I strongly doubt that the result would even come close to the most widely used compilers today—and programmers that can accept such a big performance hit would probably not use C to begin with. Certainly, any proposal for requiring compilers to curtail their exploitation of UB must come with evidence that this would even be possible while keeping C a viable language for performance-sensitive code. There actually is data, [1] and it goes against intuition because it shows that UB makes code slower. It turns out that when programmers are faced with the possibility of UB, they (quite rightly) try to work around it. (In my case, I implemented signed two's-complement arithmetic entirely with unsigned types. I also implemented my own array types, including bounds checks when indexing the arrays.) These workarounds make their code slower, in general. When you think about it that way, it makes sense because programmers almost never want UB in their software, so on average, the software that people care about will work around UB and become slower. UB in C was defensible when platforms were not homogenous and when compiler writers did not abuse the spirit of it. But nowadays, most of it is indefensible because platforms are mostly homogenous, and compiler writers have been abusing UB for "performance." We saw the same thing happen with speculative execution in chips. For years, chip manufacturers got away with lots of tricks to increase performance. Then Spectre and Meltdown were discovered. As a result, a lot of software had to be changed, which resulted in the software slowing down. (Yes, there are now mitigations in chips, but I think those mitigations will be successfully attacked too. I think that it will continue that way until most or all speculative execution is removed.) Likewise, with compilers exploiting UB against the original spirit of UB, which was just to make C easy to port to any architecture, we are probably going to have a reckoning about it in the same way we did Spectre and Meltdown. In a way, we already do, but it's spread out like a thousand paper cuts. Maybe that means that it will stay invisible enough that programmers never wake up; I hope not. tl;dr: compilers exploiting UB actually slows down good code in much the same way that Spectre and Meltdown do. [1]: https://www.complang.tuwien.ac.at/kps2015/proceedings/KPS_2015_submission_29.pdf https://www.complang.tuwien.ac.at/kps2015/proceedings/KPS_20...

sanxiyn 5y ago
That data is bullshit. It measures -fno-strict-overflow -fno-strict-aliasing. I in fact agree flipping defaults on these UBs is reasonable, but that is very far from "portable assembler" or UB-free C. THE primary UB of C is out-of-bounds write. Any proposal for UB-free C should address how to compile out-of-bounds write. If you insist out-of-bounds write should compile in "portable assembler" way and reliably corrupt memory instead of allowing compilers to assume it doesn't happen, compilers can't allocate local variables in register. If it's on stack, out-of-bounds write may reliably corrupt stack, so how can it be on register? "Portable assembler" people invariably say "that's not what I meant!" when compiler people raise this issue, but the question is "then what do you mean?" And I am yet to see any good answer.
- nkurz 5y ago
  Could you you explain your position here more fully? I'm a C programmer mostly in the "portable assembler" camp, and I don't see why insisting on out-of-bound writes to be performed prevents compilers from keeping local variables in registers. I think the difference might be your use of the word "reliably". I don't think anyone in my camp is insisting that the results be reliable in the sense you seem to take for granted. What we want is for the compiler to attempt to do what it's instructed to do, without eliding code based on counterfactual reasoning that assumes the absence of undefined behavior. In the absence of an explicit read that is being ignored, we're generally fine with cached values of local variables being out of date. Maybe you could give an example that makes your point more clearly, and we can see if we actually disagree?
  - sanxiyn 5y ago
    See https://news.ycombinator.com/item?id=30024534 https://news.ycombinator.com/item?id=30024534 (by jcranmer) and https://news.ycombinator.com/item?id=30026095 https://news.ycombinator.com/item?id=30026095 (by me). Does it help?
    - nkurz 5y ago

GoblinSlayer 5y ago

I'm afraid the author as usual confuses the cases when UB produces strange results and when the compiler actively and deliberately exacerbates the results. He also claims gcc interpretation of UB provides a lot of performance. Ironically gcc or clang already do experiments on different interpretation of UB like signed integer overflow and implicit initialization.

Joky 5y ago
Can you elaborate on the signed integer overflow and the implicit initialization differences you're referring to?
- GoblinSlayer 5y ago
  https://reviews.llvm.org/D54604 https://reviews.llvm.org/D54604 https://clang.llvm.org/docs/ClangCommandLineReference.html#cmdoption-clang-fwrapv https://clang.llvm.org/docs/ClangCommandLineReference.html#c...
  - Joky 5y ago
    But these are options, it's not a big deal to me that compiler offers special options for special use cases. It's not clear to me if you are saying that the *default* for clang and GCC differs, aren't they both using `fno-wrapv` by default?
    - GoblinSlayer 5y ago
      These options provide a different interpretation of UB like signed integer overflow and implicit initialization. It's in reference to Ralf's blog post: >I honestly think trying to write a highly optimizing compiler based on a different interpretation of UB would be a worthwhile experiment. We sorely lack data on how big the performance gain of exploiting UB actually is. However, I strongly doubt that the result would even come close to the most widely used compilers today—and programmers that can accept such a big performance hit would probably not use C to begin with. Certainly, any proposal for requiring compilers to curtail their exploitation of UB must come with evidence that this would even be possible while keeping C a viable language for performance-sensitive code. He doesn't know such interpretations are implemented by widely used C compilers.

mzs 5y ago

I really wish we got cc: warning: UB line: 123 file: foo.c

gpderetta 5y ago
Compilers will routinely warn if they can detect UB at compile time. The problem is that except in a few trivial cases it is impossible to detect UB at compile time. Even whole program static analysis can only catch a small subset.
foxfluff 5y ago
Yeah, it'd be nice if we could solve the halting problem.
tlb 5y ago
You can't detect most UB at compile time. LLVM has a system to detect it a runtime. There is a significant performance penalty, but it can be useful during testing. See https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html
- astrange 5y ago
  It’s not actually that significant compared to something like asan. You can ship software with ubsan enabled if you want to.
jcranmer 5y ago
How many warnings do you want for this small function? void oh_the_humanity(int *ptr, int val) { *ptr = val + 1; } Off the top of my head: * UB: ptr may be pointing a float variable. (It's not illegal to assign a float* to an int*, it's only UB when you actually dereference it with the wrong type.) * UB: val + 1 may overflow. * UB: potential data race on writing *ptr. * UB: ptr may be a one-past-the-end-of-the-array pointer, which can be validly constructed, but may not be dereferenced. * UB: ptr may be pointing to an object whose lifetime has expired. * UB: ptr may be uninitialized. * UB: val may be uninitialized. As you can see, UB is intensely specific to the actual data values; it's not really possible to catch even a large fraction of UB statically without severe false positive rates.

mpweiher 5y ago

He doesn't really address any of the claims made, and makes some startling claims himself. For example: > This example demonstrates that even ICC with -O1 already requires unrestricted UB. The example demonstrates nothing of the sort. It demonstrates that ICC uses unrestricted undefined behaviour, not that this is required in any way shape or form. (The only way the word "requires" is reasonable here is that the behavior seen "requires" use of this kind of UB to be present. But that's something very different, and doesn't match with the rest of his use). > writing C has become incredibly hard since undefined behavior is so difficult to avoid No, it has become difficult because compilers exploit UB in insane ways. The platform specific UB that he claims is "not an option" is, incidentally, exactly how UB is defined in the standard: Permissible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message). This was made non-binding in later versions of the standard, so optimiser engineers act as if these words don't exist. And of course there is no reason given for this interpretation being "not an option". Except for "but I wanna". Yes, it's not an option if you really want to exploit UB in the insane ways that compilers these days want to exploit it. But that's not necessary in any way shape or form. > That would declare all but the most basic C compilers as non-compliant. Yes, because by any sane interpretation of the standard they are non-compliant. On a more general note, I find this idea that things are necessary because I want to do them really bizarre.

gpderetta 5y ago
sorry, I don't understand, it seems to me that current optimizing compilers are fully compliant with the option of "ignoring the situation completely with unpredictable results". That's how UB exploiting optimizations work: the compiler ignores the possibility that the erroneous case can ever happen and takes into account only all valid states.
- mpweiher 5y ago
  Apologies, but "ignoring the situation completely with undpredictable results" is the exact opposite of "assuming the situation cannot occur and acting on that assumption". If my program attempts to write outside the bounds of declared array, ignoring the situation (that this is UB) is letting that write happen, and letting the chips fall where they might. How is assuming it cannot/must not happen, and then optimising it away because it did happen "ignoring the situation"??

mlindner 5y ago

I pretty strongly disagree with these quotes you have here. You don't need UB to do optimization, in fact because of UB in C many forms of optimization are impossible in C because of aliasing uncertainty. If things are defined to not alias then even though things are fully defined there is a lot more optimization that can be performed by not reloading variables from memory and instead using local cached-in-register copies of variables. This is why naive Rust can in some cases be faster than naive C (without using of restrict keyword) and this will only improve with time as compilers better support this.

puffoflogic 5y ago
> If things are defined to not alias ... What do you call it then when you put aliasing pointers into pointer variables "defined not to alias"? Can you explain how this reduces UB?
- foxfluff 5y ago
  I think they're trying to say that if your language prevents aliasing (i.e. pointers by definition do not alias and it is impossible to make them alias), then the compiler doesn't need to worry about it. C doesn't prevent aliasing, therefore the compiler has to worry about every case of aliasing that isn't undefined. But it's not the UB here that prevents optimization, it's precisely the fact that aliasing is (sometimes) defined. If it were always UB, the compiler wouldn't ever have to worry about it... but that'd require some interesting changes to the language to keep it usable. Definitely not backwards compatible changes.
  - puffoflogic 5y ago
  - andrewla 5y ago
    > pointers by definition do not alias and it is impossible to make them alias This is equivalent to saying that pointer arithmetic is disallowed. Pointers are by their nature in the C virtual machine offsets into a linear memory space, so for any two pointers, x and y, there exists a c such that (ptr_t)x+c == (ptr_t)y, and thus there can always be aliasing.

commandlinefan 5y ago

I had the same basic thought while reading this: the only alternative here is to interpret this sort of undefined behavior in a "different" way (such as the way the K&R originally interpreted it) and leave it up the programmer to intuit what other assumptions the compiler is making on their behalf. Like... I can assume that the compiler will interpret: if (i++ < i) as mov ax, i inc ax cmp ax, i jge else ... but that's still me making a (reasonable?) assumption. The C spec essentially just says "don't program that way".

Shikadi 5y ago
Odd intuition, since you never store i back after incrementing. Also, I believe i++ might increment after the comparison rather than before, vs. ++i incrementing first
- commandlinefan 5y ago
  You know what I mean.
  - Shikadi 5y ago
    I actually don't, but maybe I just lack enough background knowledge on the discussion to understand your intent
    - saghm 5y ago
      I think they're saying that the assembly translation doesn't store back `i`, whereas the C version does, so it's a not straightforward to assume that the assembly compiled from the C won't do that.
    - commandlinefan 5y ago
      The article talks about a similar code snippet being optimized out by the compiler because i++ can never be less than i originally was (unless you take into account the actual behavior of computers).

scott_s 5y ago

HN thread: https://news.ycombinator.com/item?id=29435263 https://news.ycombinator.com/item?id=29435263