10 ms·

The reason for leaving integer overflow undefined was not primarily because of one's complement machines. It was for loop optimization. Consider for (int i = 0

• Filligree 3y ago
  Maybe the idea hadn't been invented back then, but it seems obvious to me that the correct response is an iterator protocol. Or at least a hardcoded for-in syntax.
  • dahfizz 3y ago
    Care to explain? An iterator is a nice high level concept, but the CPU still has to do the &in + i + offset arithmetic. I don't see how replacing `i` with syntactic sugar changes the need to check for overflow.
    • nostrademons 3y ago
      I think the point the GP is making is that with an iterator protocol, the iterator implementation itself is free to make a different choice on implementation strategies, based on the shape of the data and the hardware available, and this is transparent to client code. So for example, a container containing only primitive ints or floats on a machine with a NVidia Hopper GPU might choose to allocate arrays as a multiple of 64, and then iterate by groups of 64, taking advantage of the full warp without needing any overflow checks. Obviously a linked list or an array of strings couldn't do this, but then, they wouldn't want to, and hiding the loop behind an iterator lets the container choose the appropriate loop structure for the format and hardware. I've heard criticisms of C and C++ that they are simultaneously too high-level and too low-level. Too high-level in that the execution model doesn't actually match the sort of massively parallel numeric computations that modern hardware gives, and too low-level that the source code input into the compiler doesn't give enough information about the real structure of the program to make decisions that really matter, like algorithm choice. It's interesting that the most compute-intensive machine learning models are actually implemented in Python, which doesn't even pretend to be low-level. The reason is because the actual computation is done in GPU/TPU-specific assembly, so Python just holds the high-level intent of the model and the optimization occurs on the primitives that the processor actually uses.
      • PaulDavisThe1st 3y ago
        "It's interesting that a lot of performance-critical code tends to be written in C++, which sometimes pretends not to be that low level. The reason is because the actual performance critical code is really running CPU-specific assembly, so C++ just holds the high level intent of the model and the optimization happens on the primitives that the processor actually uses."
      • dahfizz 3y ago
        > the iterator implementation itself is free to make a different choice on implementation strategies That's just UB with more steps. What will the spec say? "Behavior of integer overflow is undefined. Unless the overflow happens within an iterated for loop, in which case the behavior is undefined and the iterator can do whatever it wants". > I've heard criticisms of C and C++ that they are simultaneously too high-level and too low-level. I've heard this as well, and I think there is some truth to it, but C is the least-bad offender relative to any other language. C maps extremely well to assembly. The fact that assembly no longer perfectly captures the implementation of the CPU has nothing to do with C. Every other general purpose[1] language has to target the same abstraction that C does. Given that reality, C in fact maps better to the hardware than any other language. Because it is faster than any other language. Any higher level language that gives the compiler more information about algorithm choice is slower than C is. That's the bottom line. [1] This is ignoring proprietary, hardware specific tools like CUDA. That's clearly in a different category when discussing programming languages, IMO.
        • nostrademons 3y ago
          The reasoning behind the decision to make integer overflow UB changes. As the thread starter mentioned, that reasoning was loops, so you don't need an overflow counter for everyday loops. Take loops out of the equation, and take certain high-performance integer computations where arguably you should have a dedicated FixedInt type, and the logical spec behavior might be silent promotion to BigInt (like JS, Python 3, Lisp, Scheme, Haskell) or a panic (like in Rust). > [1] This is ignoring proprietary, hardware specific tools like CUDA. That's clearly in a different category when discussing programming languages, IMO. Arguably they should be part of the conversation. One main reason for the recent ascendancy of NVidia over Intel is that they're basically unwrapping all the layers of microcode translation that Intel uses to make a modern superscalar processor act like an 8086, and saying "Here, we're going to devote that silicon to giving you more compute cores, you figure out how to use them effectively."
  • alexvitkov 3y ago
    Adding an iterator in C++ means adding at least 2 more objects, multiple function calls, operator overload, templates, the whole package. You don't trust your compiler to optimize the sane trivial C case, but you trust it to optimize all that garbage away?
    • RicardoLuis0 3y ago
      if your data's sequential, creating an iterator in C++ is as simple as returning a begin and end pointer, and will be optimized away by any level other than O0 https://godbolt.org/z/WEjzEr5j4 https://godbolt.org/z/WEjzEr5j4
      • josefx 3y ago
        But iterating over pointers is once again optimized with lots of undefined behavior at the corners. So you are replacing one source of undefined behavior with another.
        • yazaddaruvala 3y ago
          Pointer arithmetic optimization based on undefined behavior is a problem regardless. Life is always better after minimizing the total number of types of undefined behavior.
        • AYoung010 3y ago
          Replacing undefined behavior at the program-level with undefined behavior written and tested as part of the standard library, usually vendored and distributed in concert with the compiler, seems like an obvious net-positive to me.
        • commonlisp94 3y ago
          > with lots of undefined behavior at the corners. What behavior is undefined in incrementing a pointer between a begin and end range?
          • 3y ago
  • kimixa 3y ago
    If you don't initialize the initial iterator state, or compare with something that isn't a valid iterator of the same container, you kinda end up with the same issues. The complaint here is that the warnings/errors for the integer case don't seem to be on by default. With the warnings command line flags enabled, this case is easily detected by the compiler, same as if it was some iterator object.
• andersa 3y ago
  It sure would be nice if modern CPUs had two sets of integer instructions: one that wraps, and one that triggers an exception on wrap, with zero overhead in non-wrapping case. Then we could compile all code with the latter, except for specifically marked edge cases where wrap is a desired part of the logic.
  • explaininjs 3y ago
    Language-level concern imo. https://doc.rust-lang.org/nightly/core/num/struct.Wrapping.html https://doc.rust-lang.org/nightly/core/num/struct.Wrapping.h...
    • andersa 3y ago
      It could be, if the hardware supported it. Consider this quote from that page: "in some debug configurations overflow is detected and results in a panic" That's not good enough. We want to always detect it! Many critical bugs are caused by this in production builds too. Solving it at the language level would require inserting branches on every integer operation which is obviously not acceptable.
      • tialaramex 3y ago
        > That's not good enough. We want to always detect it So, select the configuration where that's the behaviour? overflow-checks = true > Solving it at the language level would require inserting branches on every integer operation Yes, so that's what you have to do if you actually want this, if you won't pay for it then you can't have it.
        • andersa 3y ago
          Well, the whole point of my post was that I would really like a hardware feature that does it without overhead. How that would work behind the scenes, I have no idea. Not a hardware engineer.
          • 3y ago
• 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).
• IshKebab 3y ago
  That sounds very unlikely given that unsigned overflow is defined. The original motivation for undefined behaviour was not performance. I'm pretty sure autovectorisation was not a thing in 1989. The author's theory sounds far more likely. I'd love to see an actual citation though if you aren't just guessing.
• dundarious 3y ago
  I don't think that was the historical justification, but regardless, it is a terribly limiting and oblique hack of a convention for guiding the compiler. Why should this guidance only be possible for signed values? Why have such an important distinction be controlled in such an indirect fashion? Just 2 reasons why I prefer explicit vectorization anywhere that I feel it is important to have vectorized code.