4 ms·

So, does that mean we should use unsigned integers whenever possible, such that we have defined overflows and still benefit from optimizations?

by Kenji 11y ago

palunon 11y ago
I'm not a compiler expert, but since these optimization are possible due to the fact signed integers don't overflow, they don't apply to unsigned integers...
mikeash 11y ago
I don't think so. Most of those optimizations come from the "no overflow" part, not the "signed" part. If unsigned overflow were also undefined then these optimizations would work there as well. Since unsigned overflow is defined (all operations are modulo 2^bitsize), stuff like transforming `x + c > x` to `true` is not valid, since it can legally be false.
lmm 11y ago
No. You should use a language better aligned to the processor - one in which you can express a "loop exactly n times" construct directly, without having to add a ceremonial iteration variable.
- Kenji 11y ago
  Thank you for telling me not to use C and C++. Unfortunately, I cannot follow your advice due to existing codebases.
  - lmm 11y ago
    A lot of languages support C linkage. It can be surprisingly easy to migrate a codebase a little at a time.
- chrisseaton 11y ago
  > one in which you can express a "loop exactly n times" construct directly The problem with this advice is that there are so many things that the processor may be interested in knowing declaratively, rather than having to claw it back from the semantics of your application somehow, that the problem has become totally unmanageable. And even if we could manage it, the next generation of processor microcodes may be completely uninterested in what we've carefully encoded into your programs are actually want some other information instead.
  - 1amzave 11y ago
    I don't think the problems with that advice are singular. Perhaps the most ultimately-relevant is that looping exactly N times without a "ceremonial" counter is really only very rarely useful. Truly, how often do you see the canonical `for (i = 0; i < N; i++)` pattern in C with no references to `i` anywhere in the loop body? (Hint: if there are any, it's not "ceremonial".) Blindly repeating the exact same sequence of code just isn't something you want to do very often. To address the issue of "okay, in what languages could we do this anyway?": taken in full mathematical generality, such a capability would necessarily require bignum support, which cuts down your options significantly. I'm not sure if that was actually the intent, but if we instead accept the limitation of "up to some largeish power of two", constructing a macro to do this "directly" in C would also be quite easy. So...(shrug)
    - lmm 11y ago
      I agree that it's rare, but aren't those exactly the cases where this kind of optimization is relevant? In the cases where you're using i and it could overflow, the optimization couldn't be applied anyway.
  - lmm 11y ago
    Premature optimization is the root of all evil - a lot of programs perform more than adequately when just written in a way that directly expresses programmer intent. In cases where you need to push the very limits of performance, you'll have to add extra processor-specific information (or at least information based on educated guesses about how processors in general behave) - I don't think there's any way to avoid that. But if you're including extra information in the source that clutters up developer intent and doesn't help the processor optimize, something has gone very wrong.
- geofft 11y ago
  What language would you suggest?
  - pjmlp 11y ago
    The majority of programming languages don't have UB as part of their standard. It only happened in C, and its derivatives, because by the time ANSI C came to be, no compiler vendor wanted to give up on their hardware specific behaviors so it got all tossed under UB carpet.
brigade 11y ago
Unsigned has its own can of worms. Unsigned has higher promotion order than signed, so if you do a-b where either a or b is unsigned, you can end up with 4294967295 where you expect -1.

So, does that mean we should use unsigned integers whenever possible, such that we have defined overflows and still benefit from optimizations?

by Kenji 11y ago

So, does that mean we should use unsigned integers whenever possible, such that we have defined overflows and still benefit from optimizations?

palunon 11y ago

I'm not a compiler expert, but since these optimization are possible due to the fact signed integers don't overflow, they don't apply to unsigned integers...

mikeash 11y ago

I don't think so. Most of those optimizations come from the "no overflow" part, not the "signed" part. If unsigned overflow were also undefined then these optimizations would work there as well. Since unsigned overflow is defined (all operations are modulo 2^bitsize), stuff like transforming `x + c > x` to `true` is not valid, since it can legally be false.

lmm 11y ago

No. You should use a language better aligned to the processor - one in which you can express a "loop exactly n times" construct directly, without having to add a ceremonial iteration variable.

Kenji 11y ago
Thank you for telling me not to use C and C++. Unfortunately, I cannot follow your advice due to existing codebases.
- lmm 11y ago
  A lot of languages support C linkage. It can be surprisingly easy to migrate a codebase a little at a time.
chrisseaton 11y ago
> one in which you can express a "loop exactly n times" construct directly The problem with this advice is that there are so many things that the processor may be interested in knowing declaratively, rather than having to claw it back from the semantics of your application somehow, that the problem has become totally unmanageable. And even if we could manage it, the next generation of processor microcodes may be completely uninterested in what we've carefully encoded into your programs are actually want some other information instead.
- 1amzave 11y ago
  I don't think the problems with that advice are singular. Perhaps the most ultimately-relevant is that looping exactly N times without a "ceremonial" counter is really only very rarely useful. Truly, how often do you see the canonical `for (i = 0; i < N; i++)` pattern in C with no references to `i` anywhere in the loop body? (Hint: if there are any, it's not "ceremonial".) Blindly repeating the exact same sequence of code just isn't something you want to do very often. To address the issue of "okay, in what languages could we do this anyway?": taken in full mathematical generality, such a capability would necessarily require bignum support, which cuts down your options significantly. I'm not sure if that was actually the intent, but if we instead accept the limitation of "up to some largeish power of two", constructing a macro to do this "directly" in C would also be quite easy. So...(shrug)
  - lmm 11y ago
    I agree that it's rare, but aren't those exactly the cases where this kind of optimization is relevant? In the cases where you're using i and it could overflow, the optimization couldn't be applied anyway.
- lmm 11y ago
  Premature optimization is the root of all evil - a lot of programs perform more than adequately when just written in a way that directly expresses programmer intent. In cases where you need to push the very limits of performance, you'll have to add extra processor-specific information (or at least information based on educated guesses about how processors in general behave) - I don't think there's any way to avoid that. But if you're including extra information in the source that clutters up developer intent and doesn't help the processor optimize, something has gone very wrong.
geofft 11y ago
What language would you suggest?
- pjmlp 11y ago
  The majority of programming languages don't have UB as part of their standard. It only happened in C, and its derivatives, because by the time ANSI C came to be, no compiler vendor wanted to give up on their hardware specific behaviors so it got all tossed under UB carpet.

brigade 11y ago

Unsigned has its own can of worms. Unsigned has higher promotion order than signed, so if you do a-b where either a or b is unsigned, you can end up with 4294967295 where you expect -1.