4 ms·

One other advantage of signed overflow not listed here -- loop termination. Consider the following loop: for(int i = A; i <= B; i+=4) ... This loop can be

One other advantage of signed overflow not listed here -- loop termination. Consider the following loop: for(int i = A; i <= B; i+=4) ... This loop can be infinite if overflow is defined, and B is less than 4 from the largest value. Checking for this is a pain (and extra code), and in practice (almost) no-one would ever mean to write this and get an infinite loop when B is close to the top of the integer range. Special case checking for this case is a pain for various kinds of loop unrolling / peeling, and also removing empty loops if they don't contain any code (which often comes up in practice with C++ templates).

cokernel_hacker 11y ago
Speaking as a professional compiler engineer, this is the biggest reason why signed overflow is treated as UB. It is incredibly useful to talk about a loop's trip count or the values an induction variable can have. It turns out that taking advantage of signed overflow lets us do that in more places, a boon to all the programs which don't dynamically execute signed overflow. The tradeoff, however, is that the programing model gets way more complicated. I have talked to the engineer who introduced this optimizing power to our compiler and he sorta regrets it. IMO, we need better, higher level ways of talking about a loop's iteration space. Today, in C or C++, we are forced to represent the iteration space of a loop using the language's algebra. This is severely limiting when each operation on a signed type might introduce UB. With a higher level mechanism, we can separate the behavior that we want for loops from the behavior we want for everything else in a nice, clean way.
- pcwalton 11y ago
  > With a higher level mechanism, we can separate the behavior that we want for loops from the behavior we want for everything else in a nice, clean way. Yes! One decisive advantage that high-level iteration constructs have over for loops is that they're easier to optimize. One obvious example here is bounds checks: there's no need to have infrastructure to optimize out bounds checks over arrays during loops if you have a construct that eliminates the indexing entirely.
  - btrask 11y ago
    Genuine question: what do you do when you want to implement your own loop mechanism, iterator, array type, or whatever?
    - cokernel_hacker 11y ago
      It is the job of the language to ensure that language primitives are reusable and composable. I think this would apply to whatever mechanism is designed to describe a loop's iteration space.
      - Sean1708 11y ago
        Most languages use some sort of interface whereby if you implement certain methods for a type then that type can be iterated over using a for loop.
dsfuoi 11y ago
It's just one line. Put this before the loop if the code logically shouldn't trigger this. assert( B < B_TYPE_MAX - 4 ); Or use an if statement if it could trigger at runtime. Also the code is clearer on intent.
- pcwalton 11y ago
  You misunderstood the problem. The problem isn't that programmers can't write loops that are easy to optimize. It's rather that, in practice, they don't write loops that are easy to optimize. That's ultimately a problem with the C language.
  - dsfuoi 11y ago
    If the loops can be written and the programmers don't write them, the problem is with the language!? No, it's pretty clear where the problem is with C, programmers.
    - pcwalton 11y ago
      The easiest way to write the loop is the way that is hard to optimize. This is a fact that is beyond dispute: empirically, programmers use int to index over arrays in for loops without writing asserts. That is in fact a problem with the language.
      - dsfuoi 11y ago
        programmers use int to index over arrays in for loops without writing asserts. That is in fact a problem with the language. Ok let me get this clear, you're saying that the language is at fault because the programmers don't write correct code. I have no words.
        pcwalton 11y ago
        > Ok let me get this clear, you're saying that the language is at fault because the programmers don't write correct code. Yes. A good language makes the correct thing the easy thing.
deleted 11y ago
[deleted]

cokernel_hacker 11y ago

Speaking as a professional compiler engineer, this is the biggest reason why signed overflow is treated as UB. It is incredibly useful to talk about a loop's trip count or the values an induction variable can have. It turns out that taking advantage of signed overflow lets us do that in more places, a boon to all the programs which don't dynamically execute signed overflow. The tradeoff, however, is that the programing model gets way more complicated. I have talked to the engineer who introduced this optimizing power to our compiler and he sorta regrets it. IMO, we need better, higher level ways of talking about a loop's iteration space. Today, in C or C++, we are forced to represent the iteration space of a loop using the language's algebra. This is severely limiting when each operation on a signed type might introduce UB. With a higher level mechanism, we can separate the behavior that we want for loops from the behavior we want for everything else in a nice, clean way.

pcwalton 11y ago
> With a higher level mechanism, we can separate the behavior that we want for loops from the behavior we want for everything else in a nice, clean way. Yes! One decisive advantage that high-level iteration constructs have over for loops is that they're easier to optimize. One obvious example here is bounds checks: there's no need to have infrastructure to optimize out bounds checks over arrays during loops if you have a construct that eliminates the indexing entirely.
- btrask 11y ago
  Genuine question: what do you do when you want to implement your own loop mechanism, iterator, array type, or whatever?
  - cokernel_hacker 11y ago
    It is the job of the language to ensure that language primitives are reusable and composable. I think this would apply to whatever mechanism is designed to describe a loop's iteration space.
    - Sean1708 11y ago
      Most languages use some sort of interface whereby if you implement certain methods for a type then that type can be iterated over using a for loop.

dsfuoi 11y ago

It's just one line. Put this before the loop if the code logically shouldn't trigger this. assert( B < B_TYPE_MAX - 4 ); Or use an if statement if it could trigger at runtime. Also the code is clearer on intent.

pcwalton 11y ago
You misunderstood the problem. The problem isn't that programmers can't write loops that are easy to optimize. It's rather that, in practice, they don't write loops that are easy to optimize. That's ultimately a problem with the C language.
- dsfuoi 11y ago
  If the loops can be written and the programmers don't write them, the problem is with the language!? No, it's pretty clear where the problem is with C, programmers.
  - pcwalton 11y ago
    The easiest way to write the loop is the way that is hard to optimize. This is a fact that is beyond dispute: empirically, programmers use int to index over arrays in for loops without writing asserts. That is in fact a problem with the language.
    - dsfuoi 11y ago
      programmers use int to index over arrays in for loops without writing asserts. That is in fact a problem with the language. Ok let me get this clear, you're saying that the language is at fault because the programmers don't write correct code. I have no words.
      - pcwalton 11y ago
        > Ok let me get this clear, you're saying that the language is at fault because the programmers don't write correct code. Yes. A good language makes the correct thing the easy thing.

deleted 11y ago

[deleted]