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.

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.

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.

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

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

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

> implemented in Python,

A program which constructs an AST out of python classes and spits out GPU code is a compiler. The python is never executed.

Trivially, compilers can generate code faster than their hose language, but that doesn't make the host language fast. The compiler would be even faster if it were written in C++.

That's sort of the point. If you want to make programs really fast and really expressive, your target language ought to be as close to the hardware as possible, and your source language ought to be as expressive as possible, and then you just write a compiler to translate between them.

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?

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

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.

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.

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.

> with lots of undefined behavior at the corners.

What behavior is undefined in incrementing a pointer between a begin and end range?

Of course a basic iteration between begin()/end() will never contain out of range elements, but neither will valid increment between two integers. No need for iterators in that case either.

Say I want to do something fancy, like getting element number 11 from an array.

With an integer index I can pass 11, with random access iterators I can use begin() + 11.

Now my array only has five elements. So I check.

11 < 5? Comparison valid, successfully avoided a crash.

begin() + 11 < end() ? How where the rules for pointer comparison again, something about within an allocation and one past the end?

> something about within an allocation and one past the end?

Yeah, I forgot about that. So I agree there is some subtly which is likely to catch beginners.

Your example could safely be:

   if (std::distance(begin, end) > 5) 

Another approach I would recommend is to write a `guarded_advance` which takes an integer and the end pointer.

Also note that the situation you are describing is still a little unusual because the baseline assumption is it takes linear time to advance an iterator by more than 1 increment.

> but neither will valid increment between two integers. No need for iterators in that case either.

The purpose of an iterator is to abstract data structure access. The coordinate inside a complex data structure may not be representable by an integer.

A pointer is a valid C++ iterator.

> but you trust it to optimize all that garbage away?

Yep, if you learn about compilers you learn what kind of optimizations are easy and hard for them to make. The kind that just flattens a few levels of nested definitions are easier.

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.

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.

ARM actually kind of has that. The register file has an overflow flag that is not cleared on subsequent operations (sticky overflow). So instead of triggering an exception, which is prohibitively expensive, you can do a series of calculations and check afterwards if an overflow happened in any of them. A bit like NaN for floating point. From what I understand the flag alone is still costly, so we will have to see if it survives.

It doesn't matter if triggering the exception is expensive. At that point overflow has already occured, so your program state is now nonsense, and you might as well just let it crash unhandled. Much better outcome than reading memory at some mysterious offset.

If just having the ability for an exception to occur during an instruction causes overhead, that would be a big problem though.

Think about it like that. If you allow an exception you essentially create many branches with all their negative consequences. With the sticky bit you combine them to one branch (that is still expensive[1]).

[1] https://news.ycombinator.com/item?id=8766417

> At that point overflow has already occured, so your program state is now nonsense, and you might as well just let it crash unhandled.

The trick is to check and clear the flag before any instruction that would have a side-effect, that depends on the arithmetic result.

IEEE 754-compliant floating point units have a similar behaviour with NaN that is a bit more versatile: an arithmetic instruction results in NaN if any operand is NaN, but an instruction with side-effect (compare, convert or store) will raise an exception if given a NaN.

That's quite interesting and reasonable

That doesn't help at all if your loop variable is a 32 bit int that your compiler decided to transform away into vectorized loads from a 64 bit pointer.

But that's exactly one of the transformations that get enabled by assuming undefined overflow.

But in that case, it's not going to be wrapping either. We'll just read beyond the end of the buffer, which a bounds check should catch.

Or perhaps I'm not thinking of the specific sequence that would 1) not wrap during modifying index and 2) not hit bounds check after.

It would need to be a requirement that compilers can't upcast all your ints to 64 bit ones, do all the math, and then write them back - would need specific instructions for each size.

Language-level concern imo. https://doc.rust-lang.org/nightly/core/num/struct.Wrapping.h...

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.

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

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.

If you really want it, use it. Hardware vendors optimise stuff they see being done, they don't optimise stuff that somebody mentioned on a forum they'd kinda like but have never used because it was expensive. Maybe if you have Apple money and can buy ARM or something then you could just express such whims, but for mere mortals that's not an option.

Newer CPUs in several lines clearly optimise to do Acquire-Release because while it's not the only possible concurrency ordering model, it's the one the programmers learned, so if you make that one go faster your benchmark numbers improve.

Modern CPUs often have onboard AES. That's not because it won a competition, not directly, it's because everybody uses it - without hardware support they use the same encryption in software.

The Intel 486DX and then the Pentium happened because it turns out that people like FPUs, and eventually enough people were buying an FPU for their x86 computer that you know, why not sell them a $100 CPU and a $100 FPU as a single device for $190, they save $10 and you keep the $80+ you saved because duh, that's the same device as the FPU nobody is making an actual separate FPU you fools.

Even the zero-terminated string, which I think is a terrible idea, is sped up on "modern" hardware because the CPU vendors know C programs will use that after the 1970s.

You can compile code with -fwrapv and for most programs the overhead is minimal (the exception being that if you're writing number crunching code, the overhead is going to be huge). For my personal projects I have -fwrapv as part of the default compiler flags, and I remove the flag in opt builds. I honestly haven't caught that many bugs using it, but for the few bugs it did catch it saved me a lot of debugging time.

MIPS for example has this. It has `addu` for normal integer addition that does not trap and `add` if you want to trap on overflows.

x86 had overflow checking support (via OF flag and INTO insn) but it got slowed down and later dropped from 64 bit mode.

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.

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

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

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

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

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.

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

Yes it is, see x86 example in https://youtu.be/yG1OZ69H_-o at about the 40 minute mark for a real world example

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.

> The entire mindset of opening holes in the language specification to allow compilers to optimize without thinking hard is just wrong.

I would counter that 2's compliment overflow is a worse design in practice as easily 99% of the time overflow happening at all is a bug. Rust almost got this right by making overflow be a panic in debug builds, but then they took the worst option in making it defined 2's compliment in release builds

But also the mindset that everything must be extensively defined is just wrong. Nobody's standard library does this anyway, but also it's not feasible to do. You cannot define the exact outcome of data races, for example. UB is inevitable, it'll always exist in all languages. The debate is as such over where you put that line, not whether or not it exists at all

> UB is inevitable

There's a huge difference between UB (as in C/C++) and nondeterminism, so I don't accept this assertion. UB in C gives no semantics to executions containing it; it is neither spatially nor temporally contained. No other programming language has such a ridiculous and program- and programmer-hostile concept. And for good reason. It makes reasoning about buggy programs a non-starter. And all programs have bugs. We debug them by analyzing their runtime behavior! Crashing immediately upon a bug, exactly the same way on every machine, is the absolute best way to find and fix bugs that cannot be caught statically.

It is more true in good code than it is in bad code. If you use atomic reference counting everywhere or you're constantly allocating memory and freeing it all over the place, like a lot of "modern" code, you do tend to get quite flat profiles. But in good code, which allocates very infrequently, and is designed around flat arrays of data being processed in loops, you naturally do sit in tight loops a lot.

No, it still isn't true. Consider things like a web browser. Huge codebases where damn near the entire thing is "hot." Or OS's like iOS and Android - again, huge codebases where everything is "hot" (everything is either impacting responsiveness or battery life, after all), and vanishingly few if any "super hot tight loops." Same again with game engines like Unreal. It does have data processing hot loops like physics simulations, but it also has audio paths, rendering, AI, etc... that are also all still very much hot. Even the code that does loading, a "rare" event, is still hot because the user is blocked on it.

The "hot data processing loop" definitely exists in some systems, notably those that really just do one single thing, but those are also far from even the majority case. At least not on anything where the end user is directly paying the computational bill (aka, very few client apps fit the "single hot loop" profile)

But if you go pitch Apple with a "hey, we want iOS to be 20-30% slower because some people are uncomfortable with narrow contracts" they would rightly laugh you right out of the room.

Web browsers are the worst offenders for what I described: highly dynamic retained-mode GUIs with huge amounts of memory allocation all over the place. They are bloated and very much badly designed, so even simple websites slow any 5+-year-old computer to a crawl.

If people cared about performance (including latency and power usage) on mobile they wouldnt write such heavy apps. Reality is, people plug their phones in every day and so power usage isnt actually that important. Kept in mind, but clearly not optimised for.

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.

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.