Hacker News Reader

(Technically it is not really an overflow check the problem in that case, but typically more the need of extending an index from 32 to 64 bits because the instruction set in 64 bits do not support indexing with 32 bits index)

If you want perf in a critical tight loop that has been identified by some profiling, you can easily optimize it yourself (and yes, typically bumping the counter type to size_t / ptrdiff_t is enough to optimize, but the advantage you have is that you can actually check that this transformation is sound according of the intent of the programmer of the original code, whether in the context of the C programming language, the compiler doesn't even try to check that itself, it merely blindly makes the hypothesis that there is absolutely no UB ever, and to hell if there actually was)

But anyway we have since invented sane languages in which we BOTH have safety, and the capability to apply that kind of transformations that have a small but positive perf impact. In some cases it is actually way easier to optimize using those approaches from safe languages than from mostly unchecked ones culturally full of type punning and other kind of insanity (like C is), and this is not even a recent discovery: there is a reason for why number crunching stuck to Fortran. So C should be kind of considered as a legacy programming language, at this point. A very important one for historical reasons, but one should think twice before writing new critical infrastructure with it...

> the article complains that unsigned integer overflow is defined in C while signed integer overflow is not.

The article complains that signed integer overflow is undefined, while unsigned integer overflow is not. There's a difference.

> the Clang team believes this makes loops up to 20% faster

I'd love to see the benchmarks they conducted. Anyway, undefined behaviour was the wrong way to solve the problem. The C language should have grown a `for` loop that's more than a thin veneer of syntax sugar over `while`. Seriously, how hard would the following be?

  for (int i = start; end)) {
      // body
  }

No explicit comparison, evaluate `start` and `end` at the start of the loop, maybe cast them to the type of i, and increment implicitly. While loops can handle the weird cases. There you have your 20%.

> > the article complains that unsigned integer overflow is defined in C while signed integer overflow is not.

> The article complains that signed integer overflow is undefined, while unsigned integer overflow is not. There's a difference.

You are correct.

> > the Clang team believes this makes loops up to 20% faster

> I'd love to see the benchmarks they conducted.

It wouldn’t surprise me if they have micro benchmarks. I convinced myself they were telling the truth based on crude instruction counting: a loop must be converted into something like:

- loop body (assume it contains at least one machine instruction)

- increment loop variable

- (for unsigned): clear overflow flag

- test loop variable, exit loop if appropriate

- goto beginning of loop

I believe they don’t have to actually check the overflow flag, it’s OK to let the overflow happen. But they do have to clear the flag to avoid a spurious error if the flag gets looked at later.

I’m no expert, so it’s possible this oversimplifies things, but removing the instruction to clear the flag does remove a big chunk of this loop. But it’s a big chunk only because it’s a tight loop.

For the record, I happily use the foreach loop constructs in C++, D, Java, C#, Python, Perl, etc. but I originally avoided them until I saw a comment by Walter Bright that there is no performance penalty in D (the compiler rewrites the loop appropriately; there may be a penalty in Java because the feature might be defined in terms of their relatively heavy iterators).

Microbenchmark can be very misleading compared to real impact in real programs. Still, the gains allowed by UB of signed overflow (when you are lucky enough that this transformation is actually correct in the context of what the original programmer had in mind...) are positive and probably measurable even in real programs, or if hardly measurable, maybe they at least permit a few percent of whole system perf improvement when using SMT processors. But they are more suited to other programming language than C, and actually yes, in C++ (and probably in most languages at this point) it is better both of code readability (most important!) and performance (nice to have, but very secondary compared to code readability) to use for each constructs compared to maintaining an index yourself.

Technically there is no overflow flag to reset, it is just that some CPU instruction sets do not support indexing with a 32 bit register when using 64 bits addressing, so you have to insert an extra sign extend instruction if you want to support 2s-complement signed overflow on 32 bits indexes. So you typically already don't have any cost if your indexes are already size_t/ptrdiff_t, but ptrdiff_t signed overflow is still UB according to the C standard, which is also a shame, because it allows for far less interesting "optimizations" at this point (maybe a + w >= a --> true if w is positive, but that's actually typically dangerous, because that was historically what was used to check for overflow at source level, and now the compiler is suppressing all the checks!)

So all of that really only are trade-offs, and in the modern age (with e.g. a security picture that is kind of worrying, etc.) some people are arguing that this was a terrible idea to use this approach so carelessly, in their opinion. Most experts now think that no non-trivial codebase exist with no potential UB in it, so it is not just rants all around, some even are working on the mathematical model of the llvm optimizer to make it actually sound (for now even internally, it seems that it is not -- so unfortunately with this approach of optimisation for now there is no mathematical justification as for why the optimizations performed are actually correct even with the hypothesis of strict conformance to the C standard, so I let you imagine what happens in practice when almost no program is actually conforming...)

If there are microbenchmarks, I didn’t write them. And I’ll acknowledge that my instruction-counting approach has limits, especially since I don’t really know the details of the platform. And my approach also doesn’t account for pipelining.

But I would expect someone complaining about this optimization to do more than simply hand wave with a “supposedly.” They could instead say that the optimization can be applied when the compiler can prove x < x + 1, which it can show when both the beginning and end of the loop are known at compile time. In fact, I think it’s better to say “omit the pessimization that applies when the compiler has to allow for overflow.”

But going no farther than labeling it a “supposed optimization” turns the complaint into a standard rant.

I've done benchmarks and see no performance improvement with a small loop body. If there is a minor improvement on a trivial loop - that's not much gain.

Try it yourself.

I forgot to do this last night. I think the compiler is able to apply the optimization in many cases even if the loop variable is unsigned, so it’s more accurate to say that a pessimization is added when the compiler has to account for overflow.

If the rant had said the pessimization wasn’t all that common, or that a decent programmer should ask “how can I go through this loop fewer times?” before asking “how can I speed up each time through the loop?” I wouldn’t consider it a rant. As it is, the writer acknowledges that the other side has an argument, and then he dismisses it with a hand wave and a “supposedly.”

So "rant" is an unnecessary pejorative. Try to make your case without yelling. And I don't get your point. You have just agreed that the compiler can optimize these loops without UB. The pessimization is minor and programmer choice. So what is the argument on the other side ? How do you justify a code transformation that, e.g. produces an infinite loop by removing a programmer check for a condition that actually can occur?

I don’t think that saying “the article is a rant because it doesn’t make a serious effort to respond to counterguments” qualifies as yelling.

As for my point: in my opinion, the title promised something interesting, but the article didn’t deliver. It acknowledged that the standard committee and compiler writers disagree with its premise, but then simply asserts that the committee and compiler writers are wrong. I put it at DH3 ( http://www.paulgraham.com/disagree.html ).

If I claim somebody is ranting and raving, I’m not claiming anything about whether I’m yelling, but whether they are.

Of course, “rant” has more than one meaning. I did not mean “the writer should be held in a mental institution as a threat to themself or others,” or even “writer should feel embarrassed and ashamed for publishing this.” I meant “article makes statements that generally aren’t supported by valid arguments.”

I then gave an example that (1) was not the only case of a supporting argument not actually supporting the claim, and (2) perhaps wasn’t completely fair. But first, a story:

Recently, one of my sons had diarrhea. He complained that his sister made him sick, since she had just recovered from a cold. He never understood why we rejected that argument (yes, people with colds can give other people colds, but he didn’t have a cold), and then told him he didn’t have anything to support his claim. As far as he was concerned, he had made something that looked like a valid argument: his sister had a cold, now he was sick, q.e.d.

So when I said that the statement “‘supposed’ optimization” isn’t really an argument, but a statement that “there are people who disagree with me, but they’re wrong,” which isn’t a supporting argument — if anything, it’s a placeholder for a supporting argument — I forgot that the essay does advance one reason to reject the “‘supposed’ optimization,” but I rejected this reason (the issue about whether it’s slower to increment a value that has defined overflow than one that does not isn’t a question of whether the two values are the same size), and then said the statement had no support.

It is true that at this point, I can provide other reasons to reject the compiler writers’ argument, but then the whole exercise feels like a psychic reading (writer: “I feel like blue will be important for my next argument, can you tell me why?” reader: “wow, that’s uncanny; blue is important ...”).