Yeah. Not doing that on modern processors is actually quite disruptive.
Here:
for(i = offset; i < (offset + 16); i++) {
arr[i] = i + 32;
}
What C compilers currently do is, in line with the standard, ignore the case that offset + 16 might overflow. This makes this eligible for loop unrolling, and depending on the specifics of the math inside the loop, the compiler can do a lot to pre-calculate things because it knows this is happening 16 times exactly.If, instead, we force compilers to think about the fact that offset + 16 could have some implementation-defined meaning like wrapping, then all bets are off & we have to throw a bunch of optimization opportunities out the window.
Lots and lots of hot & tight loops which are currently able to be compiled into something suitable for the preferences of modern CPUs instead has to be to be naively compiled because of the need to hold back due to the possibility of something that largely wasn’t happening, happening.
Most people write most loops this way, never expecting or intending to overflow anything. Most loops are benefitting from this optimization. A lot of code would get slower, and programmers would have to do a lot more fragile hand-unrolling of operations to get that performance back. And they’d need to update that more often, as whatever the optimal “stride” of unrolling changes with the evolution of CPU pipelines.
It’s slower code and more work more often for more people, to satisfy a minority use-case that should really just have its own separate “please wrap this” construct.
To what end?
for(i = offset; i < (offset + 16); i++) {
arr[i] = i + 32;
}
like most loops in most programs isn't designed to overflow. The program isn't any more correct for emitting two translations of the loop, one unrolled and one which is purely a bugged case anyways.Changing the way the UB manifests while altering the nature of the optimization hasn't actually fixed anything at all here. All this would seem to accomplish would be to increase pressure on the icache.
That’s not an airbag, that’s a crumple zone that rams the steering column through your sternum to avoid the engine crushing your legs. You’re still dead, we’ve just uselessly shuffled the details around.
Uh huh. If `i` is declared as `unsigned int` instead of `int`, then overflow is defined and the compiler can't apply those optimizations. And yet the world doesn't end and the sun will still rise tomorrow...
Surely you agree that treating unsigned overflow differently from signed does not make any sense semantically? Why is signed overflow UB, but unsigned wrapping, and not the other way around? The terms 'signed' and 'unsigned' denote the value range, not "operations on this type might overflow/will never overflow".
However, the canonical representation of this system runs from 0 to 2^n+1. Hence, if you were going to make one kind of integer overflow, and not the other, C made the correct choice.
That leaves out the question of whether the difference between the two cases is significant enough to have a difference in how overflow works.
That's true, I agree that that would be a clever way to handle this particular case. It would still happily invoke undefined behavior if the indices don't match the array's length, of course. Many assumptions about the programmer knowing what they are doing goes into the optimization of C code.
> Surely you agree that treating unsigned overflow differently from signed does not make any sense semantically?
Yes. Silently wrapping unsigned overflow is also very often semantically meaningless.
Since you've posted a lot along the lines of "these optimizations don't even make a difference", you might want to see if Clang's safer-looking version is as fast as GCC's.
No, you just get much slower, non-vectorized code because the compiler is forced to forgo an optimization if you use unsigned int as the loop bound (EDIT: tom_mellior's reply illustrates this extremely well: https://gcc.godbolt.org/z/cje6naYP4)
Which is precisely the point: forcing a bunch of existing code with int loop bounds, which currently enjoys optimization, to take on the unsigned int semantics and get slower, is just going to piss off a different (and probably larger) set of people than the "compilers shouldn't assume that unsigned behaviour can't happen" set of people.
It's a tradeoff with some big downsides; this isn't the obvious win the anti-optimization crowd pretends it is.
This is a poorly written loop. C design model is that if it is not critical, we don't care, and if it is, the programmer should fix it so optimization can work. https://gcc.godbolt.org/z/ErMP4cn6s
void foo(int offset, int *arr) {
for(int i = offset; i < (offset + 16); i++) {
arr[i] = i + 32;
}
}
If you call this with offset = 100, the arr[i] in the loop will write to arr[100], arr[101], ..., arr[115]. void bar(unsigned int offset, int *arr) {
if(offset+16 < offset)fail();
for(size_t i = 0; i < 16; i++) {
arr[i] = i+ offset + 32;
}
}
If you call this with offset = 100, the arr[i] in the loop will write to arr[0], arr[1], ..., arr[15]. if (offset >= INT_MAX - 16) fail();
in foo()?(I mean, besides the fact that the size of the buffer pointed to by arr is highly unlikely to agree exactly with either INT_MAX or UNIT_MAX.)
That is precisely how it works already. The reason your code has no bounds checks is exactly because the compiler can assume that you have done your part and ensured that all indices are in bounds. This is what "the compiler can ignore UB" is all about.
The signed integer kerfuffle is just the same: The compiler assumes your cooperation in ensuring, beforehand, that your signed arithmetic never overflows. Its part of the bargain is generating the best possible code it can. Another part of its bargain is offering you the -fwrapv flag to communicate more about your expectations. A third part of the bargain is offering you sanitizers that can inform you that you have done something you probably didn't want.
Every single C program is potentially in that "minority". Nobody can tell when the compiler writers are going to change up behavior on you.
It doesn't matter how carefully the codebase has been written, whether you've had `-Wall -Wextra` enabled. What was fine at one time is no longer fine today. Any C program may suddenly start exhibiting misbehavior from innocuous to catastrophic to horrendously insecure.
It's psycho, maddening, irresponsible. And the only way to deal with it is to purge C programs compiled by these psychotic compilers from our systems.
This is ridiculously hyperbolic, and bringing unthinking emotional responses like "psycho" and "irresponsible" only obscures the fact that there are very serious engineering tradeoffs involved in trying to balance "not surprising people whose code contains an assumption that some case is going to behave a certain way when by-the-standard-as-written that case can be ignored" and "not making everything with a hot loop 8x slower because we can't assume anything about loop bounds any more", and that compilers that do the latter are unlikely to prove popular with a lot of people either.
The amount of code that looks like this in a big enough hot loop to make a difference is negligible. Can you provide even one real-world example where this makes a difference, i.e. not some microbenchmark? The amount of code that can break as a result of signed overflows being UB, on the other hand, is huge.
> programmers would have to do a lot more fragile hand-unrolling of operations to get that performance back
Much easier ways to do this, e.g. by using an assert wrapper around __builtin_unreachable. Alternatively, an unsafe_int_t could be defined that gives the optimize-able behavior. The important thing is to make it opt-in; sensible defaults matter.
Sure. I don't even have to leave this thread to find one: https://news.ycombinator.com/item?id=27223954 reports a measurable speed impact to PostgreSQL when compiled with -fwrapv, which rules out the exact optimization in question.
This shouldn't be surprising; loops are extremely common and superscalar processors benefit enormously from almost anything other than a naïve translation of them.
Here's -fwrapv cutting performance of a function in half in Cython vs the non-fwrapv compilation: https://stackoverflow.com/questions/46496295/poor-performanc...
z = x+y; if(z< x )overflowerror(); //important computation and
for(i=start, i >= start && i < n; i++)docomputation(x[i]); etc.
C++ recently decided to not make signed overflow defined, despite having the explicit opportunity to do so. Here is the reasoning:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p090...
> Performance concerns, whereby defining the behavior prevents optimizers from assuming that overflow never occurs;
> Implementation leeway for tools such as sanitizers;
> Data from Google suggesting that over 90% of all overflow is a bug, and defining wrapping behavior would not have solved the bug.
Presumably, data from Google disproves your assertion that the amount of code that breaks due to signed overflow being UB is huge.
> least disruptive
Like starting to optimize away loop checks that can "never happen" because signed integer overflow is UB, suddenly changing the behavior of programs that were fine for years?
I wish I could just fence off this insanity by never starting another project in C. Unfortunately, C is ubiquitous in the ecosystem so all of us are stuck cleaning it up.