6 ms·

> 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

> 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? 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.

rectang 5y ago
> to satisfy a minority use-case 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.
- msbarnett 5y ago
  > Every single C program is potentially in that "minority". Nobody can tell when the compiler writers are going to change up behavior on you. 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.
adwn 5y ago
> 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. 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...
- tom_mellior 5y ago
  The world doesn't end, but in the "int" case you get nice vector code and in the "unsigned int" case you get much less nice scalar code: https://gcc.godbolt.org/z/cje6naYP4 https://gcc.godbolt.org/z/cje6naYP4
  - adwn 5y ago
    Yes, that is true. The proper way for a compiler to handle this, would be to add a single overflow check before the loop, which branches to a scalar translation of the loop. Most realistic code will need a scalar version anyway, to deal with the prolog/epilog of the unrolled loop for iteration counts that aren't multiples of the unrolling factor. 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".
    - rocqua 5y ago
      To a mathematician, wrapping 2^n+1 back to 0 is a lot more intuitive than wrapping 2^n to -2^n. Mathematically the two systems are largely equivalent. They are equivalent when considering addition and multiplication. Both implement arithmetic modulo 2^n+1. 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.
bhk 5y ago
Well-defined integer overflow would not preclude loop unrolling in this case. One simple alternative would be for the compiler to emit a guard, skipping unrolling in the case that (offset+16) overflows. This guard would be outside the unrolled loop. Furthermore, unsigned values are often used for indices (the unsigned-ness of size_t pushes programmers in that direction) and unsigned overflow is well-defined, so any compiler engineer implementing unrolling should be be able to emit such a guard so that the optimization can be applied to loops with unsigned indices.
- deleted 5y ago
  [deleted]
- msbarnett 5y ago
  > Well-defined integer overflow would not preclude loop unrolling in this case. One simple alternative would be for the compiler to emit a guard, skipping unrolling in the case that (offset+16) overflows. 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.
  - vyodaiken 5y ago
    It's not designed to overflow, and automobiles are not designed to crash, but airbags are good engineering anyways
    - msbarnett 5y ago
      When loops that aren’t designed to overflow cheerfully wrap, they mostly just execute millions of unintended iterations reading or writing before the beginning of arrays they were indexing. 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.
dooglius 5y ago
> minority use-case 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.
- msbarnett 5y ago
  > Can you provide even one real-world example where this makes a difference, i.e. not some microbenchmark Sure. I don't even have to leave this thread to find one: https://news.ycombinator.com/item?id=27223954 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-performance-of-c-function-in-cython https://stackoverflow.com/questions/46496295/poor-performanc...
  - vyodaiken 5y ago
    Sure, if you leave out error checks code runs faster. Compile mutexes to no-ops and get an even better speedup.
    - msbarnett 5y ago
      The optimizations impacted by -fwrapv have nothing whatsoever to do with “leaving out error checks”
      - vyodaiken 5y ago
vyodaiken 5y ago
This is a common argument, but it is flat out wrong. If, as claimed, compilers have complete freedom of choice about how to handle UB, they have the choice to e.g. make this behavior depend on the processor architecture. Compiler developers are choosing to use UB to make C semantics defective.

rectang 5y ago

> to satisfy a minority use-case 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.

msbarnett 5y ago
> Every single C program is potentially in that "minority". Nobody can tell when the compiler writers are going to change up behavior on you. 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.

adwn 5y ago

> 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. 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...

tom_mellior 5y ago
The world doesn't end, but in the "int" case you get nice vector code and in the "unsigned int" case you get much less nice scalar code: https://gcc.godbolt.org/z/cje6naYP4 https://gcc.godbolt.org/z/cje6naYP4
- adwn 5y ago
  Yes, that is true. The proper way for a compiler to handle this, would be to add a single overflow check before the loop, which branches to a scalar translation of the loop. Most realistic code will need a scalar version anyway, to deal with the prolog/epilog of the unrolled loop for iteration counts that aren't multiples of the unrolling factor. 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".
  - rocqua 5y ago
    To a mathematician, wrapping 2^n+1 back to 0 is a lot more intuitive than wrapping 2^n to -2^n. Mathematically the two systems are largely equivalent. They are equivalent when considering addition and multiplication. Both implement arithmetic modulo 2^n+1. 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.

bhk 5y ago

Well-defined integer overflow would not preclude loop unrolling in this case. One simple alternative would be for the compiler to emit a guard, skipping unrolling in the case that (offset+16) overflows. This guard would be outside the unrolled loop. Furthermore, unsigned values are often used for indices (the unsigned-ness of size_t pushes programmers in that direction) and unsigned overflow is well-defined, so any compiler engineer implementing unrolling should be be able to emit such a guard so that the optimization can be applied to loops with unsigned indices.

deleted 5y ago
[deleted]
msbarnett 5y ago
> Well-defined integer overflow would not preclude loop unrolling in this case. One simple alternative would be for the compiler to emit a guard, skipping unrolling in the case that (offset+16) overflows. 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.
- vyodaiken 5y ago
  It's not designed to overflow, and automobiles are not designed to crash, but airbags are good engineering anyways
  - msbarnett 5y ago
    When loops that aren’t designed to overflow cheerfully wrap, they mostly just execute millions of unintended iterations reading or writing before the beginning of arrays they were indexing. 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.

dooglius 5y ago

> minority use-case 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.

msbarnett 5y ago
> Can you provide even one real-world example where this makes a difference, i.e. not some microbenchmark Sure. I don't even have to leave this thread to find one: https://news.ycombinator.com/item?id=27223954 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-performance-of-c-function-in-cython https://stackoverflow.com/questions/46496295/poor-performanc...
- vyodaiken 5y ago
  Sure, if you leave out error checks code runs faster. Compile mutexes to no-ops and get an even better speedup.
  - msbarnett 5y ago
    The optimizations impacted by -fwrapv have nothing whatsoever to do with “leaving out error checks”
    - vyodaiken 5y ago

vyodaiken 5y ago

This is a common argument, but it is flat out wrong. If, as claimed, compilers have complete freedom of choice about how to handle UB, they have the choice to e.g. make this behavior depend on the processor architecture. Compiler developers are choosing to use UB to make C semantics defective.