7 ms·

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

by 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.
  - tom_mellior 5y ago
    > 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. 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.
- vyodaiken 5y ago
  Clang uses vectors for both. https://gcc.godbolt.org/z/G997Ge9KT https://gcc.godbolt.org/z/G997Ge9KT
  - tom_mellior 5y ago
    Yes, with lots of extra ceremony around it. (More than is needed, since it doesn't seem to realize that it will always process exactly 16 loop iterations.) 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.
    - vyodaiken 5y ago
      It's not an interesting optimization. Micro-benchmarks are of limited utility. The extra complication is to protect the code from flying off and writing on random memory. Well worth it.
msbarnett 5y ago
> And yet the world doesn't end and the sun will still rise tomorrow... 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 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.
- vyodaiken 5y ago
  And switch the i to a size_t and get vector code without the possibility of writing to random memory because your int overflows and GCC wants to pretend it cannot. 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 https://gcc.godbolt.org/z/ErMP4cn6s
  - tom_mellior 5y ago
    You changed writes to indices offset..offset+15 to writes to indices 0..15.
    - vyodaiken 5y ago
      the offset is used to compute the index, not the count.
      - tom_mellior 5y ago
        But you're not using the offset to compute the index in bar(). 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].

by adwn 5y ago

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.
- tom_mellior 5y ago
  > 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. 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.
vyodaiken 5y ago
Clang uses vectors for both. https://gcc.godbolt.org/z/G997Ge9KT https://gcc.godbolt.org/z/G997Ge9KT
- tom_mellior 5y ago
  Yes, with lots of extra ceremony around it. (More than is needed, since it doesn't seem to realize that it will always process exactly 16 loop iterations.) 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.
  - vyodaiken 5y ago
    It's not an interesting optimization. Micro-benchmarks are of limited utility. The extra complication is to protect the code from flying off and writing on random memory. Well worth it.

msbarnett 5y ago

> And yet the world doesn't end and the sun will still rise tomorrow... 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 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.

vyodaiken 5y ago
And switch the i to a size_t and get vector code without the possibility of writing to random memory because your int overflows and GCC wants to pretend it cannot. 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 https://gcc.godbolt.org/z/ErMP4cn6s
- tom_mellior 5y ago
  You changed writes to indices offset..offset+15 to writes to indices 0..15.
  - vyodaiken 5y ago
    the offset is used to compute the index, not the count.
    - tom_mellior 5y ago
      But you're not using the offset to compute the index in bar(). 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].