4 ms·

So 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, sig

by gwd 7y ago

So 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 ago
N 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 ago
No, 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 ago
  I hadn’t understood the utility of undefined behaviour until reading this, thank you.
- rbultje 7y ago
  I/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 ago
    Another 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 7y ago
      One could allow the overflow behavior to be specified, for example on the scope level. Idk, with a #pragma ? #pragma integer-overflow-saturate
      - gwd 7y ago
        I'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.
        qppo 7y ago
        I don't know if I agree. Overflow is like uninitialized memory, it's a bug almost 100% of the time, and cases where it is tolerated or intended to occur are the exception. I'd rather have a special type with defined behavior. That's actually what a lot of shops do anyways, and there are some niche compilers that support types with defined overflow (ADI's fractional types on their Blackfin tool chain, for example). It's just annoying to do in C, this is one of those cases where operator overloading in C++ is really beneficial.
        gwd 7y ago
        > I don't know if I agree. Overflow is like uninitialized memory, it's a bug almost 100% of the time, and cases where it is tolerated or intended to occur are the exception. Right, but I think the problem is that UB means literally anything can happen and be conformant to the spec. If you do an integer overflow, and as a result the program formats your hard drive, then it is acting within the C spec. Now compiler writers don't usually format your hard drive when you trigger UB, but they often do things like remove input sanitation or other sorts of safety checks. It's one thing if as a result of overflow, the number in your variable isn't what you thought it was going to be. It's completely different if suddenly safety checks get tossed out the window. When you handle unsanitized input in C on a security boundary, you must literally treat the compiler as a "lawful evil" accomplice to the attackers: you must assume that the compiler will follow the spec to the letter, but will look for any excuse to open up a gaping security hole. It's incredibly stressful if you know that fact, and incredibly dangerous if you don't.
- thayne 7y ago
  Have you considered adding intrinsic functions for arithmetic operations that _do_ have defined behavior on overflow. Such as the overflowing_* functions in rust?
  - flatfinger 7y ago
    The semantics most programs need for overflow are to ensure that (1) overflow does not have intolerable side effects beyond yielding a likely-meaningless value, and (2) some programs may need to know whether an overflow might have produced an observably-arithmetically-incorrect result. A smart compiler for a well-designed language should in many cases be able to meet these requirements much more efficiently than it could rigidly process the aforementioned intrinsics. A couple of easy optimizations, for example, that would be available to a smart compiler processing straightforwardly-written code to use automatic overflow checking, but not to one fed code that uses intrinsics: 1. If code computes x=yz, but then never uses the value of x, a compiler that notices that x is unused could infer that the computation could never be observed to produce an arithmetically-incorrect result, and thus there would be no need to check for overflow. 2. If code computes xy/z, and a compiler knows that y=z*2, the compiler could simplify the calculation to x+x, and would thus merely have to check for overflow in that addition. If code used intrinsics, the compiler would have to overflow check the multiplication, which on most platforms would be more expensive. If an implementation uses wrapping semantics, the cost would be even worse, since an implementation would have to perform an actual division to ensure "correct" behavior in the overflow case. Having a language offer options for the aforementioned style of loose overflow checking would open up many avenues of optimization which would be unavailable in language that only over precise overflow checking or no overflow checking whatsoever.
    - thayne 7y ago
      oops, i meant the wrapping_* functions
      - flatfinger 7y ago
        If one wants a function that will compute xy/z when xy doesn't overflow, and yield some arbitrary value (but without other side-effects) when it does, wrapping functions will often be much slower than would be code that doesn't have to guarantee any particular value in case of overflow. If e.g. y is known to be 30 and z equal to 15, code using a wrapping multiply would need to be processed by multiplying the value by 30, computing a truncated the result, and dividing that by 15. If the program could use loosely-defined multiplication and division operators, however, the expression could be simplified to x+x.
zodiac 7y ago
No, the optimizations referred to include those that will make the program faster when N=100.

by gwd 7y ago

buckminster 7y ago

N 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 ago

No, 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 ago
I hadn’t understood the utility of undefined behaviour until reading this, thank you.
rbultje 7y ago
I/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 ago
  Another 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 7y ago
    One could allow the overflow behavior to be specified, for example on the scope level. Idk, with a #pragma ? #pragma integer-overflow-saturate
    - gwd 7y ago
      I'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.
      - qppo 7y ago
        I don't know if I agree. Overflow is like uninitialized memory, it's a bug almost 100% of the time, and cases where it is tolerated or intended to occur are the exception. I'd rather have a special type with defined behavior. That's actually what a lot of shops do anyways, and there are some niche compilers that support types with defined overflow (ADI's fractional types on their Blackfin tool chain, for example). It's just annoying to do in C, this is one of those cases where operator overloading in C++ is really beneficial.
        gwd 7y ago
        > I don't know if I agree. Overflow is like uninitialized memory, it's a bug almost 100% of the time, and cases where it is tolerated or intended to occur are the exception. Right, but I think the problem is that UB means literally anything can happen and be conformant to the spec. If you do an integer overflow, and as a result the program formats your hard drive, then it is acting within the C spec. Now compiler writers don't usually format your hard drive when you trigger UB, but they often do things like remove input sanitation or other sorts of safety checks. It's one thing if as a result of overflow, the number in your variable isn't what you thought it was going to be. It's completely different if suddenly safety checks get tossed out the window. When you handle unsanitized input in C on a security boundary, you must literally treat the compiler as a "lawful evil" accomplice to the attackers: you must assume that the compiler will follow the spec to the letter, but will look for any excuse to open up a gaping security hole. It's incredibly stressful if you know that fact, and incredibly dangerous if you don't.
thayne 7y ago
Have you considered adding intrinsic functions for arithmetic operations that _do_ have defined behavior on overflow. Such as the overflowing_* functions in rust?
- flatfinger 7y ago
  The semantics most programs need for overflow are to ensure that (1) overflow does not have intolerable side effects beyond yielding a likely-meaningless value, and (2) some programs may need to know whether an overflow might have produced an observably-arithmetically-incorrect result. A smart compiler for a well-designed language should in many cases be able to meet these requirements much more efficiently than it could rigidly process the aforementioned intrinsics. A couple of easy optimizations, for example, that would be available to a smart compiler processing straightforwardly-written code to use automatic overflow checking, but not to one fed code that uses intrinsics: 1. If code computes x=yz, but then never uses the value of x, a compiler that notices that x is unused could infer that the computation could never be observed to produce an arithmetically-incorrect result, and thus there would be no need to check for overflow. 2. If code computes xy/z, and a compiler knows that y=z*2, the compiler could simplify the calculation to x+x, and would thus merely have to check for overflow in that addition. If code used intrinsics, the compiler would have to overflow check the multiplication, which on most platforms would be more expensive. If an implementation uses wrapping semantics, the cost would be even worse, since an implementation would have to perform an actual division to ensure "correct" behavior in the overflow case. Having a language offer options for the aforementioned style of loose overflow checking would open up many avenues of optimization which would be unavailable in language that only over precise overflow checking or no overflow checking whatsoever.
  - thayne 7y ago
    oops, i meant the wrapping_* functions
    - flatfinger 7y ago
      If one wants a function that will compute xy/z when xy doesn't overflow, and yield some arbitrary value (but without other side-effects) when it does, wrapping functions will often be much slower than would be code that doesn't have to guarantee any particular value in case of overflow. If e.g. y is known to be 30 and z equal to 15, code using a wrapping multiply would need to be processed by multiplying the value by 30, computing a truncated the result, and dividing that by 15. If the program could use loosely-defined multiplication and division operators, however, the expression could be simplified to x+x.

zodiac 7y ago

No, the optimizations referred to include those that will make the program faster when N=100.