4 ms·

I found the title a little misleading: there isn’t much about where the standard is heading or even where it’s been. I would vote for the title “a rant on unde

I found the title a little misleading: there isn’t much about where the standard is heading or even where it’s been. I would vote for the title “a rant on undefined behavior in C.” —— Simple example: the article complains that unsigned integer overflow is defined in C while signed integer overflow is not. There is very little in the article about this except for the claim that the performance for incrementing a signed int should match the performance for incrementing an unsigned int. The writer refuses to believe otherwise, even though he accepts that undefined behavior “supposedly” allows the compiler to omit overflow checks. It’s the “supposedly” that makes this a rant. The article’s sources mention that Clang does omit overflow checks and that the Clang team believes this makes loops up to 20% faster (“up to” because the optimization can’t be applied to all loops, and the performance increase will depend on how tight the loop is, i.e., how much overhead there is in incrementing and testing the loop variable in comparison to the loop body).

loup-vaillant 8y ago
> 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%.
- maxlybbert 8y ago
  > > 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).
  - xorblurb 8y ago
    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...)
    - maxlybbert 8y ago
      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.
vyodaiken 8y ago
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.
- maxlybbert 8y ago
  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.”
  - vyodaiken 8y ago
    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?
    - maxlybbert 8y ago
      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 http://www.paulgraham.com/disagree.html ).
    - maxlybbert 8y ago
xorblurb 8y ago
(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...

loup-vaillant 8y ago

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

maxlybbert 8y ago
> > 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).
- xorblurb 8y ago
  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...)
  - maxlybbert 8y ago
    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.

vyodaiken 8y ago

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.

maxlybbert 8y ago
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.”
- vyodaiken 8y ago
  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?
  - maxlybbert 8y ago
    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 http://www.paulgraham.com/disagree.html ).
  - maxlybbert 8y ago

xorblurb 8y ago

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