6 ms·
Signed overflow being undefined behavior allows optimizations that wouldn't otherwise be possible Quoting http://blog.llvm.org/2011/05/what-every-c-programmer-
by cataphract 7y ago
Signed overflow being undefined behavior allows optimizations that wouldn't otherwise be possible
Quoting http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html http://blog.llvm.org/2011/05/what-every-c-programmer-should-...
> This behavior enables certain classes of optimizations that are important for some code. For example, knowing that INT_MAX+1 is undefined allows optimizing "X+1 > X" to "true". Knowing the multiplication "cannot" overflow (because doing so would be undefined) allows optimizing "X*2/2" to "X". While these may seem trivial, these sorts of things are commonly exposed by inlining and macro expansion. A more important optimization that this allows is for "<=" loops like this:
> for (i = 0; i <= N; ++i) { ... }
> In this loop, the compiler can assume that the loop will iterate exactly N+1 times if "i" is undefined on overflow, which allows a broad range of loop optimizations to kick in. On the other hand, if the variable is defined to wrap around on overflow, then the compiler must assume that the loop is possibly infinite (which happens if N is INT_MAX) - which then disables these important loop optimizations. This particularly affects 64-bit platforms since so much code uses "int" as induction variables.
- gwd 7y agoSo in a corner case where you have a loop that iterates over all integer values (when does this ever happen?) you can optimize your loop. As a consequence, signed integer arithmetic is very difficult to write while avoiding UB, even for skilled practitioners. Do you think that's a useful trade-off, and do you think anything can be done for those of us who think it's not?
- buckminster 7y agoN is a variable. It might be INT_MAX so the compiler cannot optimise the loop for any value of N. Unless you make this UB.
- andrepd 7y agoNo, it's exactly the opposite. Without UB the compiler must assume that the corner case may arise at any time. Knowing it is UB we can assert `n+1 > n`, which without UB would be true for all `n` except INT_MAX. Standardising wrap-on-overflow would mean you can now handle that corner case safely, at the cost of missed optimisations on everything else.
- vermilingua 7y agoI hadn’t understood the utility of undefined behaviour until reading this, thank you.
- rbultje 7y agoI/we understand the optimization, and I'm sure you understand the problem it brings to common procedures such as DSP routines that multiply signed coefficients from e.g. video or audio bitstreams: for (int i = 0; i < 64; i++) result[i] = inputA[i] * inputB[i]; If inputA[i] * inputB[i] overflowed, why are my credit card details at risk? The question is: can we come up with an alternate behaviour that incorporates both advantages of the i<=N optimization, as well as leave my credit card details safe if the multiplication in the inner loop overflowed? Is there a middle road?
- qppo 7y agoAnother problem is that there's no way to define it, because in that example the "proper" way to overflow is with saturating arithmetic, and in other cases the "proper" overflow is to wrap. Even on CPUs/DSPs that support saturating integer arithmetic in hardware, you either need to use vendor intrinsics or control the status registers yourself.
- jononor 6y agoOne could allow the overflow behavior to be specified, for example on the scope level. Idk, with a #pragma ? #pragma integer-overflow-saturate
- gwd 6y agoI'd almost rather have a separate "ubsigned" type which has undefined behavior on overflow. By default, integers behave predictably. When people really need that extra 1% performance boost, they can use ubsigned just in the cases where it matters.
- 6y ago
- zodiac 6y agoNo, the optimizations referred to include those that will make the program faster when N=100.
- rbultje 7y ago> for (i = 0; i <= N; ++i) { ... } The worst thing is that people take it as acceptable that this loop is going to operate differently upon overflow (e.g. assume N is TYPE_MAX) depending on whether i or N are signed vs. unsigned.
- JoeAltmaier 7y agoIs this a real concern, beyond 'experts panel' esoteric discussion? Do folks really put a number into an int, that is sometimes going to need to be exactly TYPE_MAX but no larger? I've gone a lifetime programming, and this kind of stuff never, ever matters one iota.
- sdegutis 6y agoThe very few times I've ever put in a check like that, I always do something like i < MAX_INT - 5 just to be sure, because I'm never confident that I intuitively understand off-by-one errors.
- JoeAltmaier 6y agoSame here. But I instead run a loop over a range around MAX_INT (or wherever the issue is) and print the result, so I know I'm doing what I think I'm doing. Exhaustive testing is quick, with a computer!
- GTP 6y agoThis isn't a good idea either: if you're dealing with undefined behavior the way the complier translates your code can change from version to version, so you could end up with a code that works with the current version of GCC but doesn't work on the next. Personally I don't agree with the way GCC and other comipers deal with UB, but this would be off topic.
- JoeAltmaier 6y agoHm. May be off-topic by now. Incrementing an int is going to work the same on the same hardware, forever. Nothing the compile has any say in.
- userbinator 6y agoI've always thought that assuming such things should be wrong, because if you were writing the Asm manually, you would certainly think about it and NOT optimise unless you had a very good reason why it won't overflow. Likewise, I think that unless the compiler can prove that it, it should, like the sane human, refrain from making the assumption.
- scaredginger 6y agoWell, by that reasoning, if you were coding in C, you would certainly think about it and ensure overflows won't happen. The fact is that if the compiler encounters undefined behaviour, it can do basically whatever it wants and it will still be standard-compliant.