3 ms·

The solution is to have the compiler automatically split iteration into a known in-bounds part and a possibly-out-of-bounds part. In this case, generating an ad

by titzer 3y ago

The solution is to have the compiler automatically split iteration into a known in-bounds part and a possibly-out-of-bounds part. In this case, generating an additional check that {ARRAY_WIDTH < (INT_MAX - offset)} would be sufficient to guarantee that {i + offset} doesn't wrap around, enabling further reasoning in a specialized copy of the loop. (In this example, it's unclear what the relation to ARRAY_WIDTH is to in and out). The HotSpot C2 compiler (and AFAIK, Graal) do partitition iteration spaces in this way. This does have some complexity cost in the compiler, of course, and it produces more code, especially if the compiler generates multiple copies of the loop. But given that relatively few super-hot loops of this kind are in typical programs, it is worth it.

logicchains 3y ago
>But given that relatively few super-hot loops of this kind are in typical programs, it is worth it. In C programs these kind of super-hot loops are quite common, because if someone didn't have many such loops they probably wouldn't need to write in C/C++. And if C had the same overhead as Java in these cases, then people who needed to squeeze out every drop of performance would use a different language.
- titzer 3y ago
  > these kind of super-hot loops are quite common People say this, then they write microbenchmarks. Then compilers optimize the heck out of these microbenchmarks (and numerical kernels). Rinse and repeat for several decades, and every dirty trick that you can think of gets blessed under the guise of UB. When in reality, real programs do not spend all their time in one (or even a handful) of super-hot loops. C was designed to let compilers have a field day so that 1980s supercomputers could get 5% more FP performance, by hook or by crook. This kind of dangerous optimizations do not make much different for the vast majority of application code, the majority of which spends its time chasing pointers and chugging through lots of abstraction layers.
  - haberman 3y ago
    > When in reality, real programs do not spend all their time in one (or even a handful) of super-hot loops. This paper from 2015 finds that a large amount of CPU in Google data centers is spent in a relatively small number of core components, known as the "datacenter tax": https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/44271.pdf https://static.googleusercontent.com/media/research.google.c... > [We] identify common building blocks in the lower levels of the software stack. > This “datacenter tax” can comprise nearly 30% of cycles > across jobs running in the fleet, which makes its constituents > prime candidates for hardware specialization in future server > systems-on-chips. Some of the components they identify are memmove() (definitely a loop), protocol buffers (proto parsing is a loop), and compression/decompression (a loop).
  - TapamN 3y ago
    >C was designed to let compilers have a field day so that 1980s supercomputers could get 5% more FP performance, by hook or by crook. C was designed to help create Unix. It just happened to turn out to be something that could be compiled into more efficient code than most other languages at the time, without being overly difficult to work with. From what I understand, 80s supercomputers were more likely to run Fortran. Fortran has fewer problems with pointer aliasing than C, so a Fortran compiler could generate better code than a C compiler for the type of code they would be running.
kllrnohj 3y ago
The idea that only a tiny portion of code is "hot" is just not true. But you're also missing the entire idea anyway. It's not about bounds checking, it's about at what point overflow occurs. `int` is a sized type, so if overflow is defined for it then it has to also overflow at that size. This prevents using native size of the machine if it's larger than that of `int`. Which these days it very often is since int is 32bit. So you couldn't promote it to a 64bit relative address as then it'll overflow at 64bits instead of 32bits.
- titzer 3y ago
  > This prevents using native size of the machine if it's larger than that of `int`. Having implemented multiple compiler backends for 64-bit machines, this is not true. All 64-bit machines I am aware of, and certainly all modern ones, do 32-bit arithmetic just fine.
  - kllrnohj 3y ago
    Yes it is, see x86 example in https://youtu.be/yG1OZ69H_-o https://youtu.be/yG1OZ69H_-o at about the 40 minute mark for a real world example
    - titzer 3y ago
      It's actually really annoying to get an example from a video, but nevertheless... The example shows you still didn't really seem to grok my point, which I will state again. A compiler can introduce additional checks for overflow that guard a large region (e.g. the repeated code in that example plus the loop after--maybe even the whole function!) and then make exactly the same transformations in the guarded region. The result is exactly the same machine code. It will go fast and not go out-of-bounds or wrap around. If the program would go out-of-bounds or wrap around, the guard will dynamically catch than and branch to a slower copy of the code that does exactly the right behavior at the right place. This is exactly how Java JITs approach C code quality. They use all the same tricks, they just have to try harder to handle the edge cases. And besides, there are several other ways to get that code--instead of using int32_t, it could have been uintptr_t, which replaces UB with platform-specific behavior but nevertheless lets the compiler do the LEA and other addressing mode tricks. No need to resort to UB. The entire mindset of opening holes in the language specification to allow compilers to optimize without thinking hard is just wrong. Programs have bugs. They go out of bounds. Preserving the exact out-of-bounds behavior is what allows programmers to debug their code. Checking bounds is what keeps programs from getting pwned all the time. It's not an opportunity for magic go-fast at the expense of security and debuggability. We're here in this muck today because of a persistent and deliberate choice to be hostile to programmers, programs, and people running those programs because compiler designers didn't want to work hard. That doesn't fly in literally any other programming language domain; C is the odd duck and it's frankly ruined people's reasoning centers.

by titzer 3y ago

logicchains 3y ago

>But given that relatively few super-hot loops of this kind are in typical programs, it is worth it. In C programs these kind of super-hot loops are quite common, because if someone didn't have many such loops they probably wouldn't need to write in C/C++. And if C had the same overhead as Java in these cases, then people who needed to squeeze out every drop of performance would use a different language.

titzer 3y ago
> these kind of super-hot loops are quite common People say this, then they write microbenchmarks. Then compilers optimize the heck out of these microbenchmarks (and numerical kernels). Rinse and repeat for several decades, and every dirty trick that you can think of gets blessed under the guise of UB. When in reality, real programs do not spend all their time in one (or even a handful) of super-hot loops. C was designed to let compilers have a field day so that 1980s supercomputers could get 5% more FP performance, by hook or by crook. This kind of dangerous optimizations do not make much different for the vast majority of application code, the majority of which spends its time chasing pointers and chugging through lots of abstraction layers.
- haberman 3y ago
  > When in reality, real programs do not spend all their time in one (or even a handful) of super-hot loops. This paper from 2015 finds that a large amount of CPU in Google data centers is spent in a relatively small number of core components, known as the "datacenter tax": https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/44271.pdf https://static.googleusercontent.com/media/research.google.c... > [We] identify common building blocks in the lower levels of the software stack. > This “datacenter tax” can comprise nearly 30% of cycles > across jobs running in the fleet, which makes its constituents > prime candidates for hardware specialization in future server > systems-on-chips. Some of the components they identify are memmove() (definitely a loop), protocol buffers (proto parsing is a loop), and compression/decompression (a loop).
- TapamN 3y ago
  >C was designed to let compilers have a field day so that 1980s supercomputers could get 5% more FP performance, by hook or by crook. C was designed to help create Unix. It just happened to turn out to be something that could be compiled into more efficient code than most other languages at the time, without being overly difficult to work with. From what I understand, 80s supercomputers were more likely to run Fortran. Fortran has fewer problems with pointer aliasing than C, so a Fortran compiler could generate better code than a C compiler for the type of code they would be running.

kllrnohj 3y ago

The idea that only a tiny portion of code is "hot" is just not true. But you're also missing the entire idea anyway. It's not about bounds checking, it's about at what point overflow occurs. `int` is a sized type, so if overflow is defined for it then it has to also overflow at that size. This prevents using native size of the machine if it's larger than that of `int`. Which these days it very often is since int is 32bit. So you couldn't promote it to a 64bit relative address as then it'll overflow at 64bits instead of 32bits.

titzer 3y ago
> This prevents using native size of the machine if it's larger than that of `int`. Having implemented multiple compiler backends for 64-bit machines, this is not true. All 64-bit machines I am aware of, and certainly all modern ones, do 32-bit arithmetic just fine.
- kllrnohj 3y ago
  Yes it is, see x86 example in https://youtu.be/yG1OZ69H_-o https://youtu.be/yG1OZ69H_-o at about the 40 minute mark for a real world example
  - titzer 3y ago
    It's actually really annoying to get an example from a video, but nevertheless... The example shows you still didn't really seem to grok my point, which I will state again. A compiler can introduce additional checks for overflow that guard a large region (e.g. the repeated code in that example plus the loop after--maybe even the whole function!) and then make exactly the same transformations in the guarded region. The result is exactly the same machine code. It will go fast and not go out-of-bounds or wrap around. If the program would go out-of-bounds or wrap around, the guard will dynamically catch than and branch to a slower copy of the code that does exactly the right behavior at the right place. This is exactly how Java JITs approach C code quality. They use all the same tricks, they just have to try harder to handle the edge cases. And besides, there are several other ways to get that code--instead of using int32_t, it could have been uintptr_t, which replaces UB with platform-specific behavior but nevertheless lets the compiler do the LEA and other addressing mode tricks. No need to resort to UB. The entire mindset of opening holes in the language specification to allow compilers to optimize without thinking hard is just wrong. Programs have bugs. They go out of bounds. Preserving the exact out-of-bounds behavior is what allows programmers to debug their code. Checking bounds is what keeps programs from getting pwned all the time. It's not an opportunity for magic go-fast at the expense of security and debuggability. We're here in this muck today because of a persistent and deliberate choice to be hostile to programmers, programs, and people running those programs because compiler designers didn't want to work hard. That doesn't fly in literally any other programming language domain; C is the odd duck and it's frankly ruined people's reasoning centers.