8 ms·

Impact of Undefined Behavior on Performance

47 points by SerCe 5y ago

tirrex 5y ago
> And how much impact does it have on runtime performance? Well even computing a sum for a relative small number 1000, according to cppbench, the signed version is 430X faster. Although you can find these kind of examples for a few lines of code snippet, the question is what is the impact on overall program? Nowadays, I guess it has no impact for almost all programs. Because memory access patterns, system call overhead, operating system interaction etc. have much more impact on overall performance compared to optimizations enabled by undefined behaviors.
- fooker 5y ago
  You are wrong. Optimizations directly enabled by Undefined behavior are only a very negligible part of the performance benefits of the existence of UB. For example, consider the fact that array access out of bounds is UB. Because of this a compiler can assume (without proof) that all accesses are actually going to be in range. This enables a boatload of loop optimizations. All non trivial optimizations done by a compiler usually assume such facts.
  - AlotOfReading 5y ago
    The problem has always been that in practice any nontrivial codebase had UB somewhere (invalidating the entire program!) and diagnosing any particular instance was generally painful until recently. Compilers didn't point most things out, sanitizers didn't exist, and prior to 2011, I don't think there was even a list of UB in C besides the entire standard. C++ is still largely in that position AFAIK. It's a complete disaster on all sides.
    - fooker 5y ago
      Invalidating the entire program is theoretically correct, but not really a useful statement. In practice, weird miscompilations due to UB are just slightly more difficult to debug than your usual segfault. You can generally keep reducing your problem to localize the issue in the code. Also, such issues are not very common because the value obtained from an UB operation is usually nonsense (shifting past bitwidth, out of bounds array element, etc) so a compiler switching things around is just garbage-in-garbage-out. It is of course a serious issue if a program is actually depending on such a value for a crucial operation. That's how you get exploits, with or without the compiler doing something clever.
      - anonymoushn 5y ago
        One of my least favorite bugs came from a loop that iterated from *p to *(p+n) (exclusive). For n=0 and values of p other than null, the loop body never executes. For n=0 and p=null, the loop body is allowed to execute, because null+0 is allowed to be any value.
        fooker 5y ago
        Nice example! Seems solvable by printf debugging though..
        taneq 5y ago
        The fact that it’s fixable doesn’t mean it’s fun…
      - barrkel 5y ago
        Miscompilations due to UB are normally silent and can remove checks written into the code for security purposes; e.g. checks for overflowing signed integers, or for null pointers. They're not harder to debug. Debugging them isn't the issue. The problem is knowing that the code in the editor doesn't correspond to the code under execution.
      - vlovich123 5y ago
        All I can do is point out that very big names in CS (including Linus) disagree with you: http://www.yodaiken.com/wp-content/uploads/2018/05/ub-1.pdf http://www.yodaiken.com/wp-content/uploads/2018/05/ub-1.pdf This is probably because they’ve seen the effects of the foot gun first hand. They also recall what C/C++ looked like before the standards bodies made exploiting UB in compilers open season. There’s also a reason why Rust doesn’t have any UB in its safe dialect even though it sits on infrastructure capable of most/all the same possible optimizations via LLVM. There was in fact a direct kernel security issue UB exploitation caused in the Linux kernel whereas without that optimization there is no security issue. if I recall correctly the code looked something like: Some_value = ptr->value If (!ptr) { return; } This worked correctly in all cases before the compiler added the optimization. It worked less well after because the !ptr check was UB since it followed a dereference. It also wasn’t immediately obvious this code was broken because there was no diagnostic nor any indication that upgrading a compiler would suddenly elide the check. The value-add of such optimizations at scale vs the correctness issues exploiting it causes is questionable. The problem wasn’t that it’s not fixable. It’s that it takes time to find and you may not even find it until after it’s being exploited.
- foota 5y ago
  I'm not so sure, while these certainly have a large impact on performance, I know that compiler optimizations have a huge impact as well, now what part of that is enabled by assuming the lack of undefined behavior I don't know.
- jcelerier 5y ago
  > Because memory access patterns, system call overhead, operating system interaction etc. have much more impact on overall performance In most media apps, the actually processing intensive part definitely does not do syscalls or OS interaction. It's pure computations for as long as possible (and often non-parallelizable, e.g. x[i] *= x[i-1] sort of things). Disabling those optimisations is a killer.
lordnacho 5y ago
Doesn't UB also mean whatever it does might change? This summation thing seems clever but in a large code base you probably don't want to have a bunch of clever UBs.
- pornel 5y ago
  Quality/performance of optimizations may change, but that's separate from UB. Behavior of the code is not supposed to ever change, unless you let the program to cause UB (e.g. give it numbers that do overflow). But you're not allowed to let the program cause UB under any circumstances, ever. So as far as "correct" programs go, it's guaranteed not to change. UB is about giving freedom to the compiler to assume that certain cases never ever happen, so it doesn't need to worry about them. In C, C++, and unsafe Rust the programmer has responsibility to ensure that UB situations can't happen, so the effect of the assumption can't be observed.
superjan 5y ago
Interesting point, but a better post about compilers exploiting this type of ub is ryg’s: https://gist.github.com/rygorous/e0f055bfb74e3d5f0af20690759de5a7 https://gist.github.com/rygorous/e0f055bfb74e3d5f0af20690759...
eptcyka 5y ago
Cool, one version of a compiler will do the cool optimization that makes it go fast. But since this is undefined behavior, it's also unspecified behavior, and one can't expect it to be reliable. Maybe in practice this doesn't matter, but theoretically there's nothing (besides perf regression testing) stopping the next version of the same compiler from not doing this. Furthermore, you'll be bound to a specific compiler if you care about performance enough to rely on specific behavior for UB, one can't reasonably expect all compilers to do the same thing when they are allowed to do UB.
vkazanov 5y ago
So, in a narrow, simplistic case signed integer overflow undef behaviour made it possible to replace a loop with a constant. Hooooray! Pretending that integer overflows don't happen because of undef behaviour is... Funny. Integer overflow do happen a lot, both with signed and unsigned ints. Compilers should only apply radical optimisations in this situation if they can prove an overflow will never happen. Otherwise, they should not touch the loop. EDIT: typos, rephrasing for clarity
- cobbal 5y ago
  The problem is that “radical” is in the eye of the beholder. If a language is so poorly specified that developers and the specification don’t agree on the meaning of a program, that leaves optimizers in an unwinnable situation.
  - vkazanov 5y ago
    In this particular case the problem can relatively painfully defined away by Wg14.
imoverclocked 5y ago
> or _when_ undefined behavior is our friend. (emphasis mine) I think this is the key point a lot of responses are missing. It's not that undefined behavior is innately good or bad. It's that it leaves wiggle room that can potentially be exploited for good while being too rigid may not always be the best long-term strategy. I used to think of code as something that should live forever and compile/run for all time without change. Over time, I've come to realize that just as spoken languages evolve, so do our programming languages. To run/understand code written 2 decades ago, we often have to use compilers/interpreters from that era. I doubt that will change even with extremely rigid language specifications.
CJefferson 5y ago
The compiler could still sub in the equation for unsigned integers, the equation is (mostly) the same. Not discussed (that I can see), the real problem is the loop variable -- because the loop ends with ' <= n', which means if n is the largest unsigned integer, this is an infinite loop. One easy thing UB is useful for is proving these types of loop terminate (as overflowing would be UB).
- tpolzer 5y ago
  And indeed, clang is able to do it for unsigned, too: https://godbolt.org/z/36r1Maq7b https://godbolt.org/z/36r1Maq7b gcc doesn't seem to implement this optimization at all. Technically it should be possible for the <=n case, too: An infinite loop is undefined behavior, so the compiler is allowed to assume it doesn't happen. But I guess (for good reasons) compiler writers are reluctant to exploit that too heavily (or it's just about ordering of optimization passes).
  - CJefferson 5y ago
    Didn't know clang can do it for unsigned, so it seems there really isn't anything here you can only do with UB. EDIT: I had a quick look to see why the obvious equation ( n (n+1))/2 ) didn't just work. The only problem for large n is you need to do the 'n (n+1)' in a bigger type (it doesn't technically matter if the n*(n+1) overflows, you just need a bigger type), so when you divide by 2 you get the right value in the top-most byte of 'unsigned int'.
    - hairtuq 5y ago
      You don't necessarily need a wider type (which might be slower to work with), you can just calculate (n|1) * ((n+1)/2). Clang does something much more complicated, probably because for it is just a special case of some much more general optimization.
      - CJefferson 5y ago
        That's a neat trick! -- I was trying to figure out how to handle the fact I didn't know which of n and n+1 was even.
fay59 5y ago
That's not a good take. Compilers love UB because it signals unreachable code, and unreachable code can be removed and/or its surroundings can be simplified. If UB was instead defined to trap, most optimizations that are made possible by UB would still be possible, but without the footgun part. Specifically with this example, if the rust community cared, it could implement pattern detection for this operation and reduce it to a constant-time operation too; the reality is just that nobody cares and this optimization was probably only added to make Clang look better on a specific benchmark. The other problem with UB is how capricious the specification is. There is no contemporary reason for why signed integer arithmetic is UB and unsigned integer arithmetic isn't. It's just a wrinkle from the past that somehow, some people prefer to praise than to fix.
- mike_hock 5y ago
  > If UB was instead defined to trap, most optimizations that are made possible by UB would still be possible, but without the footgun part. ... on hardware where the native instruction happens to trap. Otherwise it needs to generate a conditional branch and explicit trap instruction, which is as unoptimal as any other imposed behavior.
  - fay59 5y ago
    No, you’ve missed the point. It’s still much better to have a trap than “any other imposed behaviour” because the compiler can reason that this condition is impossible on the happy path and remove code accordingly. Removing code is both among the most sensitive and the most effective optimizations that compilers do, and they use UB as another signal for “unreachable”. The current model of “assume things never happen and don’t plan anything in particular if it does happen” does no one a service.
    - mike_hock 5y ago
      If you impose that the unhappy path must trap, the compiler has to guarantee that. Conversely, if the compiler can reason that the condition is impossible, it can remove code regardless of what behavior is imposed for the condition that it knows can't happen.
tomp 5y ago
Hm… so Rust compiles code as is, whereas C “overly smart” compiler mangles correct code into faster, less correct version. If Rust is too slow (as measured by the profiler… premature optimisation etc.), you can always take another look at the algorithm and optimise it manually, and correctly. On the other hand, if C is wrong… let’s hope you manage to isolate the fault to this function (a big if!)… start up the debugger… the assembly will likely look correct, because the compiler won’t optimise so aggressively in a debug build! Good luck debugging <3
- secondcoming 5y ago
  If your code has UB then it was never correct. The issue is that instead of telling you about your UB, compiler writers use it to generate very quick but broken programs
  - MichaelBurge 5y ago
    Suppose there are 3 translation units compiled from: a.c int foo(int* ptr); int main() { return foo(0); } b.c int foo(int* ptr) { return *ptr; } c.c int foo(int* ptr) { return 5; } All three translation units do not have undefined behavior, so no compiler should report it. At the time of compilation of a.c, foo does not have a definition. If it is linked with b.c's object file, the program would have undefined behavior. But if it is linked with c.c's object file, there is no undefined behavior. Object files can't tell who they're going to be linked with. And when b.c is compiled, foo only exhibits undefined behavior if somebody else calls it with an invalid pointer. It's not b.c's problem. Further, a.c and b.c might be compiled with different C compilers(very common), so you can't rely on any kind of caching of type information or state-tracking across translation units. When the linker is run, the undefined behavior is instantiated to create an incorrect binary, but linkers aren't regulated by the C standard so it wouldn't be appropriate to include a UB checker in one. To do what you're saying, you'd need a language designed for whole-program analysis. Rust and Haskell do this, and they both require you to have source code for all your dependencies so they can recompile them each time. It'd be quite the design change for C, and not something compiler writers can "fix" by themselves.
steerablesafe 5y ago
One nice thing about undefined behavior is that it allows any behavior to be implemented, including diagnostics. So if your compiler has an option to do that (-fsanitize=undefined) then you can make use of that to catch bugs. If you have defined wrapping/saturating semantics then you don't get this option, even if overflow is a bug in your program. AFAIK rust also panics on overflow in debug builds, so it's already decided that overflow is semantically a bug by default. So in release mode as it is already a bug then you potentially can't reason about the further behavior of the program. The compiler to assume that overflow doesn't happen and using that to optimize your program does not worsen the situation too much.
- ithkuil 5y ago
  fwiw, rust behaves differently between debug and release but in both cases the behaviour is defined. In release mode signed overflow is two-complement wraparound. You can use this fact to insert assertions that check if that happened and you won't be surprised that the compiler removes the check code you just wrote to check whether something happened! > The compiler to assume that overflow doesn't happen and using that to optimize your program does not worsen the situation too much. quite the contrary, the situation is much much worse! The C compiler silently removes code you may have written with the explicit intention of checking the effects of something. Yes sure you have bug; now with underfined behaviour you have an even harder time figuring out you have a bug in the first place! I'd be slightly less mad at C (copmilers) if it provided me a way of annotation a statement with "please don't optimize this out". But seriously, just don't exploit undefined behaviour. Programs have bugs; yes when a program hits a bug and continues you can say that the behaviour of the program is no longer defined according the the original intentions of the author. But wouldn't it be much much better if at least you can reason about what the program does according to how the (buggy) program is actually written? How mad would you be at a debugger that when asked to inspect the state of a variable that has been subjected to a signed overflow, would just lie to you and tell you it has a value it had some time in the past (or worse)?
- temac 5y ago
  Exploit UB to do optims can degenerate to the invocation of nasal deamons. I'm not sure to what extent it would theoritically be possible to avoid daemons while still providing some optimization, nor if any people even studied that question, but pragmatically: - complete violation and exploitation of the VM is a situation that Rust is trying to address as a main goal; - the main implementation using LLVM would make it hard to avoid unbounded consequences given the internal handling of UBs by llvm are rarely exploited with such constraints in mind.
renox 5y ago
I think that Zig has undefined behaviour for + overflow both both signed and unsigned values. It also has an 'add_modulo' operator.
the8472 5y ago
Safe rust can eliminate the loop just fine if you use fold() or an exclusive range instead of an inclusive one. This is because in release mode it has wrapping semantics for unsigned integers. In debug mode you would get a panic instead for too large inputs. So the behavior is defined, albeit still a bit of a pitfall. But you can enable overflow checks in release mode too if desired. https://rust.godbolt.org/z/1sK7GEr9E https://rust.godbolt.org/z/1sK7GEr9E
bxparks 5y ago
The problem with undefined behavior is that there are about 200 of them in the C language spec, and I can remember only 3 or 4 at any given time (signed integer overflow, dereferencing NULL, out-of-bounds array access). And I can't remember which ones are "undefined behavior", and which ones are "implementation defined". Sometimes I remember more when I use it a lot, then I forget most of them when I shift to projects using other languages. This means my ability to write correct, non-trivial C code is basically zero.
xorvoid 5y ago
Is this really an optimization that we want/need a compiler to do? I kind of get it for really high-level languages like Haskell, but for low-level languages like C/C++ it feels like a silly toy example. The abstract machine is so low-level that many big optimizations can’t be done. Instead the compiler can only do little O(1) optimizations. And you know what, I’m perfectly fine with that. C/C++ trades it all in order to give the programmer significant control over how the code works. If I want to use the summation formula, I can just write that myself. Honestly the thing I hate about the standards bodies is that they try to have it both ways so their compiler developer buds can implement their favorite (imho dubious) optimizations. But as a programmer, what I really want is well-defined, predictable constructs. Worrying about UB while also trying to design an algorithm, while also designing good data structures, while also designing for cache hierarchy , while also optimizing, while also thinking about cache coherency, while also thinking about paging and tlb behaviors, while also.. .. .. It’s all already too complicated before having to worry about what UB the compiler may try to exploit next week. I have a very strong suspicion that almost any non-trivial C/C++ program has UB somewhere. If so, then something is seriously wrong with this whole concept when useful and practical programs written in C are not technically defined/valid C programs!

47 points by SerCe 5y ago

> And how much impact does it have on runtime performance? Well even computing a sum for a relative small number 1000, according to cppbench, the signed version is 430X faster. Although you can find these kind of examples for a few lines of code snippet, the question is what is the impact on overall program? Nowadays, I guess it has no impact for almost all programs. Because memory access patterns, system call overhead, operating system interaction etc. have much more impact on overall performance compared to optimizations enabled by undefined behaviors.

fooker 5y ago
You are wrong. Optimizations directly enabled by Undefined behavior are only a very negligible part of the performance benefits of the existence of UB. For example, consider the fact that array access out of bounds is UB. Because of this a compiler can assume (without proof) that all accesses are actually going to be in range. This enables a boatload of loop optimizations. All non trivial optimizations done by a compiler usually assume such facts.
- AlotOfReading 5y ago
  The problem has always been that in practice any nontrivial codebase had UB somewhere (invalidating the entire program!) and diagnosing any particular instance was generally painful until recently. Compilers didn't point most things out, sanitizers didn't exist, and prior to 2011, I don't think there was even a list of UB in C besides the entire standard. C++ is still largely in that position AFAIK. It's a complete disaster on all sides.
  - fooker 5y ago
    Invalidating the entire program is theoretically correct, but not really a useful statement. In practice, weird miscompilations due to UB are just slightly more difficult to debug than your usual segfault. You can generally keep reducing your problem to localize the issue in the code. Also, such issues are not very common because the value obtained from an UB operation is usually nonsense (shifting past bitwidth, out of bounds array element, etc) so a compiler switching things around is just garbage-in-garbage-out. It is of course a serious issue if a program is actually depending on such a value for a crucial operation. That's how you get exploits, with or without the compiler doing something clever.
    - anonymoushn 5y ago
      One of my least favorite bugs came from a loop that iterated from *p to *(p+n) (exclusive). For n=0 and values of p other than null, the loop body never executes. For n=0 and p=null, the loop body is allowed to execute, because null+0 is allowed to be any value.
      - fooker 5y ago
        Nice example! Seems solvable by printf debugging though..
        taneq 5y ago
        The fact that it’s fixable doesn’t mean it’s fun…
    - barrkel 5y ago
      Miscompilations due to UB are normally silent and can remove checks written into the code for security purposes; e.g. checks for overflowing signed integers, or for null pointers. They're not harder to debug. Debugging them isn't the issue. The problem is knowing that the code in the editor doesn't correspond to the code under execution.
    - vlovich123 5y ago
      All I can do is point out that very big names in CS (including Linus) disagree with you: http://www.yodaiken.com/wp-content/uploads/2018/05/ub-1.pdf http://www.yodaiken.com/wp-content/uploads/2018/05/ub-1.pdf This is probably because they’ve seen the effects of the foot gun first hand. They also recall what C/C++ looked like before the standards bodies made exploiting UB in compilers open season. There’s also a reason why Rust doesn’t have any UB in its safe dialect even though it sits on infrastructure capable of most/all the same possible optimizations via LLVM. There was in fact a direct kernel security issue UB exploitation caused in the Linux kernel whereas without that optimization there is no security issue. if I recall correctly the code looked something like: Some_value = ptr->value If (!ptr) { return; } This worked correctly in all cases before the compiler added the optimization. It worked less well after because the !ptr check was UB since it followed a dereference. It also wasn’t immediately obvious this code was broken because there was no diagnostic nor any indication that upgrading a compiler would suddenly elide the check. The value-add of such optimizations at scale vs the correctness issues exploiting it causes is questionable. The problem wasn’t that it’s not fixable. It’s that it takes time to find and you may not even find it until after it’s being exploited.
foota 5y ago
I'm not so sure, while these certainly have a large impact on performance, I know that compiler optimizations have a huge impact as well, now what part of that is enabled by assuming the lack of undefined behavior I don't know.
jcelerier 5y ago
> Because memory access patterns, system call overhead, operating system interaction etc. have much more impact on overall performance In most media apps, the actually processing intensive part definitely does not do syscalls or OS interaction. It's pure computations for as long as possible (and often non-parallelizable, e.g. x[i] *= x[i-1] sort of things). Disabling those optimisations is a killer.

lordnacho 5y ago

Doesn't UB also mean whatever it does might change? This summation thing seems clever but in a large code base you probably don't want to have a bunch of clever UBs.

pornel 5y ago
Quality/performance of optimizations may change, but that's separate from UB. Behavior of the code is not supposed to ever change, unless you let the program to cause UB (e.g. give it numbers that do overflow). But you're not allowed to let the program cause UB under any circumstances, ever. So as far as "correct" programs go, it's guaranteed not to change. UB is about giving freedom to the compiler to assume that certain cases never ever happen, so it doesn't need to worry about them. In C, C++, and unsafe Rust the programmer has responsibility to ensure that UB situations can't happen, so the effect of the assumption can't be observed.

superjan 5y ago

Interesting point, but a better post about compilers exploiting this type of ub is ryg’s: https://gist.github.com/rygorous/e0f055bfb74e3d5f0af20690759de5a7 https://gist.github.com/rygorous/e0f055bfb74e3d5f0af20690759...

eptcyka 5y ago

Cool, one version of a compiler will do the cool optimization that makes it go fast. But since this is undefined behavior, it's also unspecified behavior, and one can't expect it to be reliable. Maybe in practice this doesn't matter, but theoretically there's nothing (besides perf regression testing) stopping the next version of the same compiler from not doing this. Furthermore, you'll be bound to a specific compiler if you care about performance enough to rely on specific behavior for UB, one can't reasonably expect all compilers to do the same thing when they are allowed to do UB.

vkazanov 5y ago

So, in a narrow, simplistic case signed integer overflow undef behaviour made it possible to replace a loop with a constant. Hooooray! Pretending that integer overflows don't happen because of undef behaviour is... Funny. Integer overflow do happen a lot, both with signed and unsigned ints. Compilers should only apply radical optimisations in this situation if they can prove an overflow will never happen. Otherwise, they should not touch the loop. EDIT: typos, rephrasing for clarity

cobbal 5y ago
The problem is that “radical” is in the eye of the beholder. If a language is so poorly specified that developers and the specification don’t agree on the meaning of a program, that leaves optimizers in an unwinnable situation.
- vkazanov 5y ago
  In this particular case the problem can relatively painfully defined away by Wg14.

imoverclocked 5y ago

> or _when_ undefined behavior is our friend. (emphasis mine) I think this is the key point a lot of responses are missing. It's not that undefined behavior is innately good or bad. It's that it leaves wiggle room that can potentially be exploited for good while being too rigid may not always be the best long-term strategy. I used to think of code as something that should live forever and compile/run for all time without change. Over time, I've come to realize that just as spoken languages evolve, so do our programming languages. To run/understand code written 2 decades ago, we often have to use compilers/interpreters from that era. I doubt that will change even with extremely rigid language specifications.

CJefferson 5y ago

The compiler could still sub in the equation for unsigned integers, the equation is (mostly) the same. Not discussed (that I can see), the real problem is the loop variable -- because the loop ends with ' <= n', which means if n is the largest unsigned integer, this is an infinite loop. One easy thing UB is useful for is proving these types of loop terminate (as overflowing would be UB).

tpolzer 5y ago
And indeed, clang is able to do it for unsigned, too: https://godbolt.org/z/36r1Maq7b https://godbolt.org/z/36r1Maq7b gcc doesn't seem to implement this optimization at all. Technically it should be possible for the <=n case, too: An infinite loop is undefined behavior, so the compiler is allowed to assume it doesn't happen. But I guess (for good reasons) compiler writers are reluctant to exploit that too heavily (or it's just about ordering of optimization passes).
- CJefferson 5y ago
  Didn't know clang can do it for unsigned, so it seems there really isn't anything here you can only do with UB. EDIT: I had a quick look to see why the obvious equation ( n (n+1))/2 ) didn't just work. The only problem for large n is you need to do the 'n (n+1)' in a bigger type (it doesn't technically matter if the n*(n+1) overflows, you just need a bigger type), so when you divide by 2 you get the right value in the top-most byte of 'unsigned int'.
  - hairtuq 5y ago
    You don't necessarily need a wider type (which might be slower to work with), you can just calculate (n|1) * ((n+1)/2). Clang does something much more complicated, probably because for it is just a special case of some much more general optimization.
    - CJefferson 5y ago
      That's a neat trick! -- I was trying to figure out how to handle the fact I didn't know which of n and n+1 was even.

fay59 5y ago

That's not a good take. Compilers love UB because it signals unreachable code, and unreachable code can be removed and/or its surroundings can be simplified. If UB was instead defined to trap, most optimizations that are made possible by UB would still be possible, but without the footgun part. Specifically with this example, if the rust community cared, it could implement pattern detection for this operation and reduce it to a constant-time operation too; the reality is just that nobody cares and this optimization was probably only added to make Clang look better on a specific benchmark. The other problem with UB is how capricious the specification is. There is no contemporary reason for why signed integer arithmetic is UB and unsigned integer arithmetic isn't. It's just a wrinkle from the past that somehow, some people prefer to praise than to fix.

mike_hock 5y ago
> If UB was instead defined to trap, most optimizations that are made possible by UB would still be possible, but without the footgun part. ... on hardware where the native instruction happens to trap. Otherwise it needs to generate a conditional branch and explicit trap instruction, which is as unoptimal as any other imposed behavior.
- fay59 5y ago
  No, you’ve missed the point. It’s still much better to have a trap than “any other imposed behaviour” because the compiler can reason that this condition is impossible on the happy path and remove code accordingly. Removing code is both among the most sensitive and the most effective optimizations that compilers do, and they use UB as another signal for “unreachable”. The current model of “assume things never happen and don’t plan anything in particular if it does happen” does no one a service.
  - mike_hock 5y ago
    If you impose that the unhappy path must trap, the compiler has to guarantee that. Conversely, if the compiler can reason that the condition is impossible, it can remove code regardless of what behavior is imposed for the condition that it knows can't happen.

tomp 5y ago

Hm… so Rust compiles code as is, whereas C “overly smart” compiler mangles correct code into faster, less correct version. If Rust is too slow (as measured by the profiler… premature optimisation etc.), you can always take another look at the algorithm and optimise it manually, and correctly. On the other hand, if C is wrong… let’s hope you manage to isolate the fault to this function (a big if!)… start up the debugger… the assembly will likely look correct, because the compiler won’t optimise so aggressively in a debug build! Good luck debugging <3

secondcoming 5y ago
If your code has UB then it was never correct. The issue is that instead of telling you about your UB, compiler writers use it to generate very quick but broken programs
- MichaelBurge 5y ago
  Suppose there are 3 translation units compiled from: a.c int foo(int* ptr); int main() { return foo(0); } b.c int foo(int* ptr) { return *ptr; } c.c int foo(int* ptr) { return 5; } All three translation units do not have undefined behavior, so no compiler should report it. At the time of compilation of a.c, foo does not have a definition. If it is linked with b.c's object file, the program would have undefined behavior. But if it is linked with c.c's object file, there is no undefined behavior. Object files can't tell who they're going to be linked with. And when b.c is compiled, foo only exhibits undefined behavior if somebody else calls it with an invalid pointer. It's not b.c's problem. Further, a.c and b.c might be compiled with different C compilers(very common), so you can't rely on any kind of caching of type information or state-tracking across translation units. When the linker is run, the undefined behavior is instantiated to create an incorrect binary, but linkers aren't regulated by the C standard so it wouldn't be appropriate to include a UB checker in one. To do what you're saying, you'd need a language designed for whole-program analysis. Rust and Haskell do this, and they both require you to have source code for all your dependencies so they can recompile them each time. It'd be quite the design change for C, and not something compiler writers can "fix" by themselves.

steerablesafe 5y ago

One nice thing about undefined behavior is that it allows any behavior to be implemented, including diagnostics. So if your compiler has an option to do that (-fsanitize=undefined) then you can make use of that to catch bugs. If you have defined wrapping/saturating semantics then you don't get this option, even if overflow is a bug in your program. AFAIK rust also panics on overflow in debug builds, so it's already decided that overflow is semantically a bug by default. So in release mode as it is already a bug then you potentially can't reason about the further behavior of the program. The compiler to assume that overflow doesn't happen and using that to optimize your program does not worsen the situation too much.

ithkuil 5y ago
fwiw, rust behaves differently between debug and release but in both cases the behaviour is defined. In release mode signed overflow is two-complement wraparound. You can use this fact to insert assertions that check if that happened and you won't be surprised that the compiler removes the check code you just wrote to check whether something happened! > The compiler to assume that overflow doesn't happen and using that to optimize your program does not worsen the situation too much. quite the contrary, the situation is much much worse! The C compiler silently removes code you may have written with the explicit intention of checking the effects of something. Yes sure you have bug; now with underfined behaviour you have an even harder time figuring out you have a bug in the first place! I'd be slightly less mad at C (copmilers) if it provided me a way of annotation a statement with "please don't optimize this out". But seriously, just don't exploit undefined behaviour. Programs have bugs; yes when a program hits a bug and continues you can say that the behaviour of the program is no longer defined according the the original intentions of the author. But wouldn't it be much much better if at least you can reason about what the program does according to how the (buggy) program is actually written? How mad would you be at a debugger that when asked to inspect the state of a variable that has been subjected to a signed overflow, would just lie to you and tell you it has a value it had some time in the past (or worse)?
temac 5y ago
Exploit UB to do optims can degenerate to the invocation of nasal deamons. I'm not sure to what extent it would theoritically be possible to avoid daemons while still providing some optimization, nor if any people even studied that question, but pragmatically: - complete violation and exploitation of the VM is a situation that Rust is trying to address as a main goal; - the main implementation using LLVM would make it hard to avoid unbounded consequences given the internal handling of UBs by llvm are rarely exploited with such constraints in mind.

renox 5y ago

I think that Zig has undefined behaviour for + overflow both both signed and unsigned values. It also has an 'add_modulo' operator.

the8472 5y ago

Safe rust can eliminate the loop just fine if you use fold() or an exclusive range instead of an inclusive one. This is because in release mode it has wrapping semantics for unsigned integers. In debug mode you would get a panic instead for too large inputs. So the behavior is defined, albeit still a bit of a pitfall. But you can enable overflow checks in release mode too if desired. https://rust.godbolt.org/z/1sK7GEr9E https://rust.godbolt.org/z/1sK7GEr9E

bxparks 5y ago

The problem with undefined behavior is that there are about 200 of them in the C language spec, and I can remember only 3 or 4 at any given time (signed integer overflow, dereferencing NULL, out-of-bounds array access). And I can't remember which ones are "undefined behavior", and which ones are "implementation defined". Sometimes I remember more when I use it a lot, then I forget most of them when I shift to projects using other languages. This means my ability to write correct, non-trivial C code is basically zero.

xorvoid 5y ago

Is this really an optimization that we want/need a compiler to do? I kind of get it for really high-level languages like Haskell, but for low-level languages like C/C++ it feels like a silly toy example. The abstract machine is so low-level that many big optimizations can’t be done. Instead the compiler can only do little O(1) optimizations. And you know what, I’m perfectly fine with that. C/C++ trades it all in order to give the programmer significant control over how the code works. If I want to use the summation formula, I can just write that myself. Honestly the thing I hate about the standards bodies is that they try to have it both ways so their compiler developer buds can implement their favorite (imho dubious) optimizations. But as a programmer, what I really want is well-defined, predictable constructs. Worrying about UB while also trying to design an algorithm, while also designing good data structures, while also designing for cache hierarchy , while also optimizing, while also thinking about cache coherency, while also thinking about paging and tlb behaviors, while also.. .. .. It’s all already too complicated before having to worry about what UB the compiler may try to exploit next week. I have a very strong suspicion that almost any non-trivial C/C++ program has UB somewhere. If so, then something is seriously wrong with this whole concept when useful and practical programs written in C are not technically defined/valid C programs!