5 ms·

Just going to inject that this impacts a bunch of random optimizations and benchmarks. Just to fabricate an example: for (int i = 0; i < N; i += 2) {

Just going to inject that this impacts a bunch of random optimizations and benchmarks. Just to fabricate an example: for (int i = 0; i < N; i += 2) { // } Reasonably common idea but the compiler is allowed to assume the loop terminates precisely because signed overflow is undefined. I’m not trying to argue that signed overflow is the right tool for the job here for expressing ideas like “this loop will terminate”, but making signed overflow defined behavior will impact the performance of numerics libraries that are currently written in C. From my personal experience, having numbers wrap around is not necessarily “better” than having the behavior undefined, and I’ve had to chase down all sorts of bugs with wraparound in the past. What I’d personally like is four different ways to use integers: wrap on overflow, undefined overflow, error on overflow, and saturating arithmetic. They all have their places and it’s unfortunate that it’s not really explicit which one you are using at a given site.

alerighi 7y ago
The compiler assumes that the loop will alwasy terminate and that assumption is wrong, because in reality there is the possibility that the loop will not terminate, since the hardware WILL overflow. So it's not the best solution. If we want to make this behaviour for optimizations (that are to me not worthed, giving the risk of potentially critical bugs) we must make that behavior explicit, not implicit: thus is the programmer that has to say to the compiler, I guarantee you that this operation will never overflow, if it does it's my fault. We can agree that having a number that wraps around is not a particularly good choice. But unless we convince Intel in some way that this is bad and make the CPU trap on an overflow, so we can catch that bug, this is the behaviour that we have because is the behaviour of the hardware.
- klodolph 7y ago
  > The compiler assumes that the loop will alwasy terminate and that assumption is wrong, because in reality there is the possibility that the loop will not terminate, since the hardware WILL overflow. The language is not a model of hardware, nor should it be. If you want to write to the hardware, the only option continues to be assembly.
- coliveira 7y ago
  > I guarantee you that this operation will never overflow, if it does it's my fault. This is exactly what every C programmer does, all the time.
iainmerrick 7y ago
the compiler is allowed to assume the loop terminates precisely because signed overflow is undefined. Just to be sure I understand the fine details of this -- what would the impact be if the compiler assumed (correctly) that the loop might not terminate? What optimization would that prevent?
- klodolph 7y ago
  > …what would the impact be if the compiler assumed (correctly) that the loop might not terminate? Loaded question—the compiler is absolutely correct here. There are two viewpoints where the compiler is correct. First, from the C standard perspective, the compiler implements the standard correctly. Second, if we have a real human look at this code and interpret the programmer’s “intent”, it is most reasonable to assume that overflow does not happen (or is not intentional). The only case which fails is where N = INT_MAX. No other case invokes undefined behavior. Here is an example you can compile for yourself to see the different optimizations which occur: typedef int length; int sum_diff(int *arr, length n) { int sum = 0; for (length i = 0; i < n; i++) { sum += arr[2*i+1] - arr[2*i]; } return sum; } At -O2, GCC 9.2 (the compiler I happened to use for testing) will use pointer arithmetic, compiling it as something like the following: int sum_diff(int *arr, length n) { int sum = 0; int *ptr = arr; int *end = arr + n; while (ptr < end) { sum += ptr[1] - ptr[0]; ptr += 2; } return sum; } At -O3, GCC 9.2 will emit SSE instructions. You can see this yourself with Godbolt. Now, try replacing "int" with "unsigned". Neither of these optimizations happen any more. You get neither autovectorization nor pointer arithmetic. You get the original loop, compiled in the most dumb way possible. I wouldn’t read into the exact example here too closely. It is true that you can often figure out a way to get the optimizations back and still use unsigned types. However, it is a bit easier if you work with signed types in the first place. Speaking as someone who does some numerics work in C, there is something of a “black art” to getting good numerics performance. One easy trick is to switch to Fortran. No joke! Fortran is actually really good at this stuff. If you are going to stick with C, you want to figure out how to communicate to the compiler some facts about your program that are obvious to you, but not obvious to the compiler. This requires a combination of understanding the compiler builtins (like __builtin_assume_aligned, or __builtin_unreachable), knowledge of aliasing (like use of the "restrict" keyword), and knowledge of undefined behavior. If you need good performance out of some tight inner loop, the easiest way to get there is to communicate to the compiler the “obvious” facts about the state of your program and check to see if the compiler did the right thing. If the compiler did the right thing, then you’re done, and you don’t need to use vector intrinsics, rewrite your code in a less readable way, or switch to assembly. (Sometimes the compiler can’t do the right thing, so go ahead and use intrinsics or write assembly. But the compiler is pretty good and you can get it to do the right thing most of the time.)
nickodell 7y ago
Under C11, the compiler is still allowed to assume termination of a loop if the controlling expression is non-constant and a few other conditions are met. https://stackoverflow.com/a/16436479/530160 https://stackoverflow.com/a/16436479/530160

alerighi 7y ago

The compiler assumes that the loop will alwasy terminate and that assumption is wrong, because in reality there is the possibility that the loop will not terminate, since the hardware WILL overflow. So it's not the best solution. If we want to make this behaviour for optimizations (that are to me not worthed, giving the risk of potentially critical bugs) we must make that behavior explicit, not implicit: thus is the programmer that has to say to the compiler, I guarantee you that this operation will never overflow, if it does it's my fault. We can agree that having a number that wraps around is not a particularly good choice. But unless we convince Intel in some way that this is bad and make the CPU trap on an overflow, so we can catch that bug, this is the behaviour that we have because is the behaviour of the hardware.

klodolph 7y ago
> The compiler assumes that the loop will alwasy terminate and that assumption is wrong, because in reality there is the possibility that the loop will not terminate, since the hardware WILL overflow. The language is not a model of hardware, nor should it be. If you want to write to the hardware, the only option continues to be assembly.
coliveira 7y ago
> I guarantee you that this operation will never overflow, if it does it's my fault. This is exactly what every C programmer does, all the time.

iainmerrick 7y ago

the compiler is allowed to assume the loop terminates precisely because signed overflow is undefined. Just to be sure I understand the fine details of this -- what would the impact be if the compiler assumed (correctly) that the loop might not terminate? What optimization would that prevent?

klodolph 7y ago
> …what would the impact be if the compiler assumed (correctly) that the loop might not terminate? Loaded question—the compiler is absolutely correct here. There are two viewpoints where the compiler is correct. First, from the C standard perspective, the compiler implements the standard correctly. Second, if we have a real human look at this code and interpret the programmer’s “intent”, it is most reasonable to assume that overflow does not happen (or is not intentional). The only case which fails is where N = INT_MAX. No other case invokes undefined behavior. Here is an example you can compile for yourself to see the different optimizations which occur: typedef int length; int sum_diff(int *arr, length n) { int sum = 0; for (length i = 0; i < n; i++) { sum += arr[2*i+1] - arr[2*i]; } return sum; } At -O2, GCC 9.2 (the compiler I happened to use for testing) will use pointer arithmetic, compiling it as something like the following: int sum_diff(int *arr, length n) { int sum = 0; int *ptr = arr; int *end = arr + n; while (ptr < end) { sum += ptr[1] - ptr[0]; ptr += 2; } return sum; } At -O3, GCC 9.2 will emit SSE instructions. You can see this yourself with Godbolt. Now, try replacing "int" with "unsigned". Neither of these optimizations happen any more. You get neither autovectorization nor pointer arithmetic. You get the original loop, compiled in the most dumb way possible. I wouldn’t read into the exact example here too closely. It is true that you can often figure out a way to get the optimizations back and still use unsigned types. However, it is a bit easier if you work with signed types in the first place. Speaking as someone who does some numerics work in C, there is something of a “black art” to getting good numerics performance. One easy trick is to switch to Fortran. No joke! Fortran is actually really good at this stuff. If you are going to stick with C, you want to figure out how to communicate to the compiler some facts about your program that are obvious to you, but not obvious to the compiler. This requires a combination of understanding the compiler builtins (like __builtin_assume_aligned, or __builtin_unreachable), knowledge of aliasing (like use of the "restrict" keyword), and knowledge of undefined behavior. If you need good performance out of some tight inner loop, the easiest way to get there is to communicate to the compiler the “obvious” facts about the state of your program and check to see if the compiler did the right thing. If the compiler did the right thing, then you’re done, and you don’t need to use vector intrinsics, rewrite your code in a less readable way, or switch to assembly. (Sometimes the compiler can’t do the right thing, so go ahead and use intrinsics or write assembly. But the compiler is pretty good and you can get it to do the right thing most of the time.)

nickodell 7y ago

Under C11, the compiler is still allowed to assume termination of a loop if the controlling expression is non-constant and a few other conditions are met. https://stackoverflow.com/a/16436479/530160 https://stackoverflow.com/a/16436479/530160