4 ms·

Commenters here seem to be missing the core thesis of this article. It's not about what the standard literally means; it's about it's spirit -- and the reason f

Commenters here seem to be missing the core thesis of this article. It's not about what the standard literally means; it's about it's spirit -- and the reason for its spirit. The issue is "undefined behaviour" should never have been interpreted this extremely. The standard may be silent on how extreme, but it is implausible to suggest that the standard was actually written to enable this. Compiler writers for C! dismiss severe issues which occur in compiling any program with undefined behaviour; issues which would render any modern language a bad joke. Compiler writers are using this as a perverse shield to simply fail to optimize for correctness, or provide means to; and to enable them to optimize only for performance. Are we really saying the standard supports this sleight-of-hand? It seems more like using the Second Amendment to murder someone.

steveklabnik 5y ago
Personally, I think that arguing that those who define and implement a standard don’t understand one of the most fundamental aspects of said standard is going to be an uphill battle. You could argue that they’ve lost their way, and the article flirts with this, but the path forward is the hard part, and IMHO rings a bit hollow: it’s asserted that these rules aren’t needed for performance, but no evidence is given, and what similar evidence we do have (compiling on lower optimization levels) doesn’t seem to support this thesis. You could argue that, the kernel, which turns off aliasing, is plenty performant without it, and that’s a decent argument, but it’s not clear that it wouldn’t be even faster with it, and it’s much harder to empirically test this than removing the flag, since it will miscompile.
- bonzini 5y ago
  Different code depends on different optimizations. A loop on an int** might benefit a lot from aliasing optimizations, because the compiler will assume that a[i] will remain the same after writing to a[i][j]. Other code may not benefit at all. Likewise that loop may not benefit from signed overflow; instead an initialization loop that, by way of multiple level of macros, ends up doing a[i]=b[i]*1000/100, might become twice as fast if signed overflow rules let the compiler rewrite the assignment as a[i]=b[i]*10.
- vyodaiken 5y ago
  Wang et al tried this an experiment and found no serious wins.
  - aw1621107 5y ago
    For reference, [0] appears to be the referenced paper. The relevant passage: > To understand how disabling these optimizations may impact performance, we ran SPECint 2006 with GCC and Clang, respectively, and measured the slowdown when compiling the programs with all the three -fno-* [-fno-strict-overflow, -fno-delete-null-pointer-checks, and -fno-strict-aliasing] options shown in Figure 9. The experiments were conducted on a 64-bit Ubuntu Linux machine with an Intel Core i7-980 3.3 GHz CPU and 24 GB of memory. We noticed slowdown for 2 out of the 12 programs, as detailed next. > 456.hmmer slows down 7.2% with GCC and 9.0% with Clang. The first reason is that the code uses an int array index, which is 32 bits on x86-64, as shown below. int k; int *ic, *is; ... for (k = 1; k <= M; k++) { ... ic[k] += is[k]; ... } > As allowed by the C standard, the compiler assumes that the signed addition k++ cannot overflow, and rewrites the loop us- ing a 64-bit loop variable. Without the optimization, however, the compiler has to keep k as 32 bits and generate extra in- structions to sign-extend the index k to 64 bits for array access. This is also observed by LLVM developers [14]. > Surprisingly, by running OProfile we found that the most time-consuming instruction was not the sign extension but loading the array base address is[] from the stack in each iteration. We suspect that the reason is that the generated code consumes one more register for loop variables (i.e., both 32 and 64 bits) due to sign extension, and thus spills is[] on the stack. > If we change the type of k to size_t, then we no longer observe any slowdown with the workaround options. 462.libquantum slows down 6.3% with GCC and 11.8% with Clang. The core loop is shown below. quantum_reg *reg; ... // reg->size: int // reg->node[i].state: unsigned long long for (i = 0; i < reg->size; i++) reg->node[i].state = ...; > With strict aliasing, the compiler is able to conclude that updating reg->node[i].state does not change reg->size, since they have different types, and thus moves the load of reg->size out of the loop. Without the optimization, however, the compiler has to generate code that reloads reg->size in each iteration. If we add a variable to hold reg->size before entering the loop, then we no longer observe any slowdown with the workaround options. > While we observed only moderate performance degradation on two SPECint programs with these workaround options, some previous reports suggest that using them would lead to a nearly 50% drop [6], and that re-enabling strict aliasing would bring a noticeable speed-up [24]. [0]: https://pdos.csail.mit.edu/papers/ub:apsys12.pdf https://pdos.csail.mit.edu/papers/ub:apsys12.pdf [6]: https://lists.gnu.org/archive/html/autoconf-patches/2006-12/msg00149.html https://lists.gnu.org/archive/html/autoconf-patches/2006-12/... [24]: (dead link, doesn't appear to be available on the Wayback Machine) https://www.linaro.org/blog/compiler-flags-used-to-speed-up-linaro-android-2011-10-and-future-optimizations/index.html https://www.linaro.org/blog/compiler-flags-used-to-speed-up-...
scoutt 5y ago
The spirit of the article and your comment seems to underrate the efforts required to come up with something like the standard for a C compiler. It's not a "perverse shield". In C, "optimize for correctness" is the programmer's job. I don't want to sound dismissive, and I don't pretend you to write a compiler, but please tell me how would you word a global standard for generating compilers that can compile for hundreds of architectures, with the main focus of being portable and generating the most performant code (no runtime checks). You might come up with a standard similar to something like Rust (which does not have an standard yet, and has only a single compiler "brand"). But Rust is super-difficult to understand and part of its safeness depends on runtime checks, including runtime checks on ownership like RefCell, impacting on performance. The same goes for Ada and other runtime-checked languages. Or you'll end up with something like a standard for C, in which you assume the programmer can be somewhat trusted allowing the compiler to generate faster code, and having to deal with little caveats that depends on certain architectures.
- mjburgess 5y ago
  I am sympathetic with the view that compiler writers are trapped by the architectures they have to support. However, I think there's just a philosophical difference here about what compilers are for: are they responsible for emitting correct programs; or are they for literal transpiling? Regardless of the history which has led to the latter outcome for C, I have to agree with the author that I think K&R's original vision wasn't quite so accommodating. Perhaps ignorantly, I just have to imagine there is something a little better than the present attitude. Could there not be a --hault-on-all-undef with a serious attempt to realise that in as many respects as possible?
  - scoutt 5y ago
    > emitting correct programs; or are they for literal transpiling? I guess the former. I am sure you are familiar with the "garbage-in, garbage-out" concept. The rules are set in the standard. If you feed the compiler with code outside the rules of the standard (even if syntactically correct), you cannot expect correct programs 100% of the time. The standard (somehow) guarantees that code that follows the rules should translate into correct programs. Some of the rules dictate the compiler to "do this", other dictate "do something but specify what you are doing" and "do whatever you want, including exploding, I don't care". Many of these rules are this way for the sake of generating optimized code. These are the rules. Are these rules too many to remember? Unfortunately yes, they are. > I just have to imagine there is something a little better than the present attitude. My crazy hope is that someday runtime checks will be done at silicon level. That is, compiler emits instructions declaring "this is an array of this dimension", and every time this array is accessed with the proper instructions (and the CPU is somehow aware of this), it triggers an interrupt when accessed out of bounds, for example. > Could there not be a --hault-on-all-undef with a serious attempt to realise that in as many respects as possible? It might not be possible for every piece of code. It will have to stop the compilation (or execution with runtime checks) at every int increment/operation. So I think that if rules cannot be generally applicable then they shouldn't be applicable at all.

steveklabnik 5y ago

Personally, I think that arguing that those who define and implement a standard don’t understand one of the most fundamental aspects of said standard is going to be an uphill battle. You could argue that they’ve lost their way, and the article flirts with this, but the path forward is the hard part, and IMHO rings a bit hollow: it’s asserted that these rules aren’t needed for performance, but no evidence is given, and what similar evidence we do have (compiling on lower optimization levels) doesn’t seem to support this thesis. You could argue that, the kernel, which turns off aliasing, is plenty performant without it, and that’s a decent argument, but it’s not clear that it wouldn’t be even faster with it, and it’s much harder to empirically test this than removing the flag, since it will miscompile.

bonzini 5y ago
Different code depends on different optimizations. A loop on an int** might benefit a lot from aliasing optimizations, because the compiler will assume that a[i] will remain the same after writing to a[i][j]. Other code may not benefit at all. Likewise that loop may not benefit from signed overflow; instead an initialization loop that, by way of multiple level of macros, ends up doing a[i]=b[i]*1000/100, might become twice as fast if signed overflow rules let the compiler rewrite the assignment as a[i]=b[i]*10.
vyodaiken 5y ago
Wang et al tried this an experiment and found no serious wins.
- aw1621107 5y ago
  For reference, [0] appears to be the referenced paper. The relevant passage: > To understand how disabling these optimizations may impact performance, we ran SPECint 2006 with GCC and Clang, respectively, and measured the slowdown when compiling the programs with all the three -fno-* [-fno-strict-overflow, -fno-delete-null-pointer-checks, and -fno-strict-aliasing] options shown in Figure 9. The experiments were conducted on a 64-bit Ubuntu Linux machine with an Intel Core i7-980 3.3 GHz CPU and 24 GB of memory. We noticed slowdown for 2 out of the 12 programs, as detailed next. > 456.hmmer slows down 7.2% with GCC and 9.0% with Clang. The first reason is that the code uses an int array index, which is 32 bits on x86-64, as shown below. int k; int *ic, *is; ... for (k = 1; k <= M; k++) { ... ic[k] += is[k]; ... } > As allowed by the C standard, the compiler assumes that the signed addition k++ cannot overflow, and rewrites the loop us- ing a 64-bit loop variable. Without the optimization, however, the compiler has to keep k as 32 bits and generate extra in- structions to sign-extend the index k to 64 bits for array access. This is also observed by LLVM developers [14]. > Surprisingly, by running OProfile we found that the most time-consuming instruction was not the sign extension but loading the array base address is[] from the stack in each iteration. We suspect that the reason is that the generated code consumes one more register for loop variables (i.e., both 32 and 64 bits) due to sign extension, and thus spills is[] on the stack. > If we change the type of k to size_t, then we no longer observe any slowdown with the workaround options. 462.libquantum slows down 6.3% with GCC and 11.8% with Clang. The core loop is shown below. quantum_reg *reg; ... // reg->size: int // reg->node[i].state: unsigned long long for (i = 0; i < reg->size; i++) reg->node[i].state = ...; > With strict aliasing, the compiler is able to conclude that updating reg->node[i].state does not change reg->size, since they have different types, and thus moves the load of reg->size out of the loop. Without the optimization, however, the compiler has to generate code that reloads reg->size in each iteration. If we add a variable to hold reg->size before entering the loop, then we no longer observe any slowdown with the workaround options. > While we observed only moderate performance degradation on two SPECint programs with these workaround options, some previous reports suggest that using them would lead to a nearly 50% drop [6], and that re-enabling strict aliasing would bring a noticeable speed-up [24]. [0]: https://pdos.csail.mit.edu/papers/ub:apsys12.pdf https://pdos.csail.mit.edu/papers/ub:apsys12.pdf [6]: https://lists.gnu.org/archive/html/autoconf-patches/2006-12/msg00149.html https://lists.gnu.org/archive/html/autoconf-patches/2006-12/... [24]: (dead link, doesn't appear to be available on the Wayback Machine) https://www.linaro.org/blog/compiler-flags-used-to-speed-up-linaro-android-2011-10-and-future-optimizations/index.html https://www.linaro.org/blog/compiler-flags-used-to-speed-up-...

scoutt 5y ago

The spirit of the article and your comment seems to underrate the efforts required to come up with something like the standard for a C compiler. It's not a "perverse shield". In C, "optimize for correctness" is the programmer's job. I don't want to sound dismissive, and I don't pretend you to write a compiler, but please tell me how would you word a global standard for generating compilers that can compile for hundreds of architectures, with the main focus of being portable and generating the most performant code (no runtime checks). You might come up with a standard similar to something like Rust (which does not have an standard yet, and has only a single compiler "brand"). But Rust is super-difficult to understand and part of its safeness depends on runtime checks, including runtime checks on ownership like RefCell, impacting on performance. The same goes for Ada and other runtime-checked languages. Or you'll end up with something like a standard for C, in which you assume the programmer can be somewhat trusted allowing the compiler to generate faster code, and having to deal with little caveats that depends on certain architectures.

mjburgess 5y ago
I am sympathetic with the view that compiler writers are trapped by the architectures they have to support. However, I think there's just a philosophical difference here about what compilers are for: are they responsible for emitting correct programs; or are they for literal transpiling? Regardless of the history which has led to the latter outcome for C, I have to agree with the author that I think K&R's original vision wasn't quite so accommodating. Perhaps ignorantly, I just have to imagine there is something a little better than the present attitude. Could there not be a --hault-on-all-undef with a serious attempt to realise that in as many respects as possible?
- scoutt 5y ago
  > emitting correct programs; or are they for literal transpiling? I guess the former. I am sure you are familiar with the "garbage-in, garbage-out" concept. The rules are set in the standard. If you feed the compiler with code outside the rules of the standard (even if syntactically correct), you cannot expect correct programs 100% of the time. The standard (somehow) guarantees that code that follows the rules should translate into correct programs. Some of the rules dictate the compiler to "do this", other dictate "do something but specify what you are doing" and "do whatever you want, including exploding, I don't care". Many of these rules are this way for the sake of generating optimized code. These are the rules. Are these rules too many to remember? Unfortunately yes, they are. > I just have to imagine there is something a little better than the present attitude. My crazy hope is that someday runtime checks will be done at silicon level. That is, compiler emits instructions declaring "this is an array of this dimension", and every time this array is accessed with the proper instructions (and the CPU is somehow aware of this), it triggers an interrupt when accessed out of bounds, for example. > Could there not be a --hault-on-all-undef with a serious attempt to realise that in as many respects as possible? It might not be possible for every piece of code. It will have to stop the compilation (or execution with runtime checks) at every int increment/operation. So I think that if rules cannot be generally applicable then they shouldn't be applicable at all.