On a slightly more personal note: What are some undefined behaviors that you would like to turn into defined behavior, but can't change for whatever reasons that be?
Quoting 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.
The fact is that if the compiler encounters undefined behaviour, it can do basically whatever it wants and it will still be standard-compliant.
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.
I've gone a lifetime programming, and this kind of stuff never, ever matters one iota.
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=30475 shows someone going hyperbolic over the issue. The technical arguments favor the GCC maintainers. However I prefer the position of the person going hyperbolic.
GCC has the behavior that overflowing a signed integer gives you a negative one. But an if tests that TESTS for that is optimized away!
The reason is that overflow is undefined behavior, and therefore they are within their rights to do anything that they want. So they actually overflow in the fastest way possible, and optimize code on the assumption that overflow can't happen.
The fact that almost no programmers have a mental model of the language that reconciles these two facts is an excellent reason to say that very few programmers should write in C. Because the compiler really is out to get you.
unsigned mul(unsigned short x, unsigned short y)
{ return x*y; }
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?
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.
for (int i = 0; i < N; i += 2) {
//
}
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.
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.
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.
This is exactly what every C programmer does, all the time.
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?
I guess that doesn’t necessarily help in the “+=2” case, where you probably want the optimizer to do a “result += x/2”.
In general, I’d greatly prefer to work with a compiler that detected the potential infinite loop and flagged it as an error.
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;
}
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;
}
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.)
You're correct about how it behaves with "int" and "unsigned", very interesting. But it occurs to me that on x64 we'd probably want to use 64-bit values. If I change your typedef to either "long" or "unsigned long" that seems to give me the SSE version of the code! (in x86-64 gcc 9.3) Why should longs behave so differently from ints?
I very much agree that getting good numerics performance out of the optimizer seems to be a black art. But does the design of C really help here, or are there ways it could help more? Does changing types from signed to unsigned, or int to long, really convey your intentions as clearly as possible?
I remain skeptical that undefined behaviour is a good "hook" for compilers to use to judge programmer intention, in order to balance the risks and rewards of optimizations. (Admittedly I'm not in HPC where this stuff is presumably of utmost importance!) It all seems dangerously fragile.
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.
I strongly agree with the first part of this -- communicating your intent to the compiler is key.
It's the second part that seems really risky. Just because your compiler did the right thing this time doesn't mean it will continue to do so in future, or on a different architecture, and of course who knows what a different compiler might do? And if you end up with the "wrong thing", that may not just mean slow code, but incorrect code.
I’m sure there are ways that it could help more. But you have to find an improvement that is also feasible as an incremental change to the language. Given the colossal inertia of the C standard, and the zillions of lines of existing C code that must continue to run, what can you do?
What I don’t want to see are tiny, incremental changes that make one small corner of your code base slightly safer. Most people don’t want to see performance regressions across their code base. That doesn’t leave a lot of room for innovation.
> It all seems dangerously fragile.
If performance is critical you run benchmarks on CI to detect regression.
> It's the second part that seems really risky.
It is safer than the alternatives, unless you write it in a different language. The “fast” code here is idiomatic, simple C the way you would write it in CS101, with maybe a couple builtins added. The alternative is intrinsics, which poses additional difficulty. Intrinsics are less portable and less safe. Less safe because their semantics are often unusual or surprising, and also less safe because code written with intrinsics is hard to read and understand (so if it has errors, they are hard to find). If you are not using intrinsics or the autovectorizer, then sorry, you are not getting vector C code today.
This is also not, strictly speaking, just an HPC concern. Ordinary phones, laptops, and workstations have processors with SIMD for good reason—because they make an impact on the real-life usability of ordinary people doing ordinary tasks on their devices.
So if we can get SIMD code by writing simple, idiomatic, and “obviously correct” C code, then let’s take advantage of that.
Some additional value would be gained by allowing stores to automatic objects whose address isn't taken to maintain such extra range at their convenience, without any requirement to avoid having such extra range randomly appear and disappear. Provided that a program coerces values into range in when necessary, such semantics would often be sufficient to meet application requirements without having to prevent overflow.
What additional benefits are achieved by granting compilers unlimited freedom beyond that? I don't see any such benefits that would be worth anything near the extra cost imposed on programmers.
if ((uintptr_t)ptr & alignment) {
char *p = NULL;
printf("%c\n", *p);
}It might seem like defining the semantics for signed overflow would be helpful but it turns out it's not, either from a security view or for efficiency. In general, defining the behavior in cases that commonly harbor bugs is not necessarily a good way to fix them.
Personally, I would like to get rid of many of the trap representations (e.g., for integers) because there is no existing hardware in many cases that supports them and it gives implementers the idea that uninitialized reads are undefined behavior.
On the other hand, I just wrote a proposal to WG14 to make zero-byte reallocations undefined behavior that was unanimously accepted for C2x.
Unsigned types have their own issues, though: they overflow at "small" values like -1, which means that doing things like correctly looping "backwards" over an array with an unsigned index is non-trivial.
> On the other hand, I just wrote a proposal to WG14 to make zero-byte reallocations undefined behavior that was unanimously accepted for C2x.
You're saying that realloc(foo, 0) will no longer free the pointer?
If people used them while parsing binary inputs that would prevent a lot of security bugs.
The fact that this question exists and is full of wrong answers suggests a language solution is needed: https://stackoverflow.com/questions/1815367/catch-and-comput...
http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2466.pdf
(signal is a strong word... maybe indicate?)
(Note that while `-ftrapv` would seem equivalent, I've found it to be less reliable, particularly with compile-time checking.)
if (FAILED(DWordMult(a, b, &product)))
{
// handle error
}I know there's recently been some movement towards standardizing something in this direction, but I don't know what the status of that work is. Probably one of the folks doing the AUA can update.
The generic heterogeneous operations also avoid the identifier blowup. The only real argument against them that I see is that they are not easily implementable in C itself, but that's nothing new for the standard library (and should be a non-goal, in my not-a-committee-member opinion).
Obviously, I'm not privy to the committee discussions around this, so there may be good reasons for the choice, but it worries me a lot to see that document.
Hi Stephen, thank you for bringing this to our attention. David Svoboda and I are now working to revise the proposal to add a supplemental proposal to support operations on heterogeneous types. We are leaning toward proposing a three-argument syntax, where the 3rd argument specifies the return type, like:
ckd_add(a, b, T)
ckd_add(a, b)
>once you have the heterogeneous operations, is there any reason to keep the others around
The two-argument form is shorter, but perhaps that isn't a strong enough reason to keep it. Also, requiring a redundant 3rd argument can provide an opportunity for mistakes to happen if it gets out of sync with the type of first two arguments.
As for the non-generic functions (e.g., ckd_int_add, ckd_ulong_add, etc.), we are considering removing them in favor of having only the generic function-like macros.
Your code assumes that negating a negative value is positive. Your division check forgot about INT_MIN / -1. Your signed integer average is wrong. You confused bitshift with division. etc. etc. etc.
Unsigned arithmetic is tractable and should be treated with caution. Signed arithmetic is terrifying and should be treated with the same PPE as raw pointers or `volatile`.
This applies if arithmetic maps to CPU instructions, but not to Python or Haskell or etc. If you have automatic bignums, signed arithmetic is of course better.
I presume you'd want signed overflow to have the usual 2's-complement wraparound behavior.
One problem with that is that a compiler (probably) couldn't warn about overflows that are actually errors.
For example:
int n = INT_MAX;
/* ... */
n++;
A compiler could have an option to warn about detected overflow/wraparound even if it's well defined. But really, how often do you want wraparound for signed types? In the code above, is there any sense in which INT_MIN is the "right" answer for any typical problem domain?
There is no answer different that INT_MIN that would be right and make sense, i.e. the natural properties of the + operator (associativity, commutativity) are respected. Thus, by want of another possibility, INT_MIN is precisely the right answer to your code.
I read your code and it seems to me very clear that INT_MIN is exactly what the programmer intended.
Well, I'm the author and that's not what I intended.
I used INT_MAX as the initial value because it was a simple example. Imagine a case where the value happens to be equal to INT_MAX, and then you add 1 to it.
The fact that no result other than INT_MIN makes sense doesn't imply that INT_MIN does make sense. Saturation (having INT_MAX + 1 yield INT_MAX) or reporting an error seem equally sensible. We don't know which behavior is "correct" without knowing anything about the problem domain and what the program is supposed to do.
A likely scenario is that the programmer didn't intend the computation to overflow at all, but the program encountered input that the programmer hadn't anticipated.
INT_MAX + 1 commonly yields INT_MIN because typical hardware happens to work that way. It's not particularly meaningful in mathematical terms.
As for "natural properties", it violates "n + 1 > n". C integers are not, and cannot be, mathematical integers (unless you can restrict values to the range they support).
Sometimes you're writing code where it really, really matters and you're more than willing to spend the extra cycles for every add/mul/etc. Having these new types as a portable idiom would help.
N2466 2020/02/09 Svoboda, Towards Integer Safety
http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2466.pdf
The committee asked the proposers for further work on this effort.
Integer types that saturate are an interesting idea. Because signed integer overflow is undefined behavior, implementations are not prohibited from implementing saturation or trapping on overflow.
The entire notion that "since this is undefined behavior it does not exist" is the biggest fallacy in modern compilers.
You're exactly right that this is why there is a distinction between conforming and strictly conforming code.
Implementations define undefined behavior all the time and users rely on it. For instance, POSIX defines that you can convert an object pointer into a function pointer (for dlsym to work), or implementations often rely on offsets from a null pointer for their 'offsetof' macro implementation.