Hacker News Reader

Comment by loup-vaillant | Hacker News Reader

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

View on HN

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

Reply on news.ycombinator.com