12
$\begingroup$

For a long time, the rules for processing basic operations in various languages have been overflow.

But this is actually very strange.

The addition of two positive numbers can be a negative number, and the multiplication of two positive numbers can also be a negative number, which ultimately leads to various unexpected problems.

I wonder if my language compiles the default behavior of + into saturation_add, and requires the user to manually call wrapping_add, if user want to prevent overflow, the user can also manually call checked_add.

Will this effectively reduce inadvertent mistakes?

$\endgroup$
6
  • 3
    $\begingroup$ Do you intend to claim IEEE-754 compliance? $\endgroup$
    – Pseudonym
    Feb 24 at 9:01
  • 4
    $\begingroup$ "For a long time, the rules for processing basic operations in various languages have been overflow." – I would contest this statement. Literally none of the languages I learned to program with has this behavior. Most of the languages I use today don't have it. When I first saw it, I considered it a bug or at best, shoddy coding. I still do. $\endgroup$ Feb 24 at 10:59
  • 6
    $\begingroup$ Hi. Do you mean "should be saturation on overflow instead of wraparound on overflow"? "Overflow" by itself just means the max value was exceeded, but it doesn't presume on how to handle the situation. $\endgroup$
    – Stef
    Feb 24 at 14:33
  • 1
    $\begingroup$ @Pseudonym IEEE-754 saturates (to +/-Inf), it doesn't wrap. $\endgroup$
    – OrangeDog
    Feb 25 at 0:51
  • $\begingroup$ Note that wrapping is probably very fast because the operation does not do anything, really (overflow is simply unsigned modulo arithmetic which is what the CPU always does). $\endgroup$ Feb 25 at 15:29

4 Answers 4

36
$\begingroup$

To be clear, "overflow" just means that the result of an arithmetic operation is out-of-bounds; the behaviour you're describing is called wrapping. Saturation is a different kind of overflow behaviour.

It's worth noting that saturation already exists in many languages. Notably, floating-point numbers saturate at $\pm \infty$, but even on integers there are Rust's Saturating integer types, JavaScript's Uint8ClampedArray, and so on.

Will this effectively reduce inadvertent mistakes?

The only way that saturation could prevent a mistake caused by wrapping, is if wrapping occurs when the programmer mistakenly believes that saturation will occur ─ and that is not really plausible. The mistake is generally that the programmer neglects to consider out-of-bounds results at all. Otherwise, a wrong answer from saturation is not better than a wrong answer from wrapping.

On the other hand, occasionally overflows can cancel out: for example, in a + b - c, the addition might overflow and then the subtraction might underflow, giving the correct result for the expression. This is a consequence of a more general fact that arithmetic with wrapping forms a ring where the usual algebraic laws of arithmetic still apply, so that e.g. (a + b) - c always gives the same result as (a - c) + b, and the latter might not wrap even though the former does twice. In contrast, addition with saturation does not form a ring, so it becomes harder for the programmer and the compiler to reason about and rearrange code while preserving its behaviour.

If your goal is to reduce mistakes, then I would recommend either using arbitrary-precision integers so that overflow simply cannot occur (as Python does), or by throwing an exception at runtime so the mistake is easier to detect and diagnose (as C# and Rust do in checked/debug mode).


I would also like to address a couple of points raised by the other answer.

Although overflow is undefined behaviour in some languages, in many languages wrapping on overflow is specified (e.g. Java, C# in unchecked mode, and Rust in release mode), and can be relied on intentionally by the programmer. So you aren't necessarily just getting whatever the CPU would do, but on the other hand the design choice to specify wrapping on overflow might be made because that's what the CPU already does.

Also, there are specific use-cases for saturating arithmetic where likewise the saturation can be relied on intentionally by the programmer because that is the correct behaviour in context. In that case, saturation doesn't necessarily "mean it is an error, but didn't error too much". These contexts are typically in image processing or signal processing, where the numbers are supposed to represent pixel brightness or audio amplitude, which are logically bound within finite intervals, and saturation is generally a user requirement rather than a mistake. Nonetheless, these use-cases are domain-specific so I wouldn't recommend saturation as the default behaviour in a general-purpose language, though it might be a good idea for a domain-specific language.

$\endgroup$
5
  • $\begingroup$ Arbitrary-precision integers won't overflow, but may run out of memory. [I wonder if that can be exploited, hmmm...] $\endgroup$
    – Pablo H
    Feb 26 at 17:05
  • $\begingroup$ @PabloH: Also the severity of data races becomes a lot higher when reallocation is involved. For primitive numbers, a race may corrupt the result but in practice the damage tends to be contained in the single memory location. For arbitrary-precision, a race is much more likely to access memory no longer owned by the object, trash the memory allocator's internal metadata, and break stuff everywhere in the process. $\endgroup$
    – Ben Voigt
    Feb 26 at 17:32
  • 2
    $\begingroup$ "Otherwise, a wrong answer from saturation is not better than a wrong answer from wrapping." I see where you're coming from, but it's an exaggeration. In many real-world applications, saturation (unexpected by the programmer) would have far less severe consequences than overflow. An infamous example is the Therac-25: with saturation, it might have only given patients perhaps twice the intended dose rather than a deadly hundredfold. ... $\endgroup$ Feb 26 at 18:37
  • 1
    $\begingroup$ ... The flip side is that bugs related to overflow also tend to be more obvious and consequently have a better chance of being patched soon than saturation-related bugs, but that's not exactly an argument for both being equally bad. $\endgroup$ Feb 26 at 18:39
  • $\begingroup$ @leftaroundabout There's an argument to be made that saturation can reduce the impact of mistakes, but I don't think that applies generally. There are situations where integer quantites are roughly continuous, as in the dose of a drug, but there are also situations where what matters more is things like uniqueness (e.g. incrementing IDs) or other properties (e.g. a pointer plus a multiple of the word size being properly aligned). $\endgroup$
    – kaya3
    Feb 26 at 18:58
4
$\begingroup$

What you have observed in many languages, is at least initially not overflow, but "undefined behavior" (or any other ways saying "don't care"). That is, an erroneous behavior that anything could happen if not checked. For efficiency, the compiler may use what is the easiest in the CPU instructions, that is usually overflow mod 2^(word length).

Languages may choose to do otherwise and get it precisely defined if they decide it is worth the extra cost. But floating point numbers are already implemented in your way. And someone agreeing with you may also think floating point has other good properties such as being able to represent huge numbers. So, it's likely they just choose to use floating points everywhere, like the case of JavaScript.

There are indeed some use cases for saturating arithmetic. But that would basically mean it is an error, but didn't error too much, so that it doesn't need to be checked. It is difficult to say whether most uses of integers would be better in this kind of arithmetic. And if someone makes such assumptions, they may make more assumptions that go straight to floating point. I think it would be helpful to have multiple integer types, just like signed and unsigned, for modulo and saturating arithmetic, which should be easier to use than differentiating them per operation. But if compilers make decisions for the user, it makes sense they end up with something with better CPU support and even more features.

Wikipedia says there are already some CPU implementations of saturating arithmetic, but mostly only in SIMD instructions.

$\endgroup$
4
  • $\begingroup$ Interesting point, maybe I could define i32, i32m, i32c as basic types, which have different default behavior, but can be implicitly converted $\endgroup$
    – Aster
    Feb 24 at 7:00
  • 1
    $\begingroup$ It's not about "easiest in the CPU" its about fastest because most of users won't really care as they operate in value ranges where there's no difference. $\endgroup$
    – feldentm
    Feb 24 at 7:03
  • $\begingroup$ @Aster In rarer cases, someone may also want it to be checked, but set the value to mod or saturated before throwing an exception. For example to do carry, and to disable something else when a value is infinity. $\endgroup$
    – user23013
    Feb 24 at 8:02
  • 2
    $\begingroup$ I don't think your answer should have mentioned undefined behavior. Most languages don't have any undefined behavior, and many still allow overflow. $\endgroup$ Feb 24 at 11:31
4
$\begingroup$

When you have an overflow, the following things can happen:

  • Some form of error/exception is returned/triggered
  • Wraparound, i.e. computing modulo 2^bits, and behaves differently for signed and unsigned integers (which seems to be the behaviour you're describing)
  • Saturation/clamping (you can't go beyond the minimum/maximum values)

Wraparound is probably the most common on integers in languages like C which are very much portable macro-assemblers, because it translates to the corresponding assembler instructions of the target CPU, and for efficiency CPUs will usually do wraparound, as, especially for addition, this is a very simple operation in two's complement (though they will often set status bits indicating that overflow happened, e.g. a carry bit).

I'm not sure saturation would actually "reduce inadvertent mistakes". It will just give another incorrect and possibly undetected result. Yes, it's certainly less confusing than getting a negative result after adding or multiplying two positive values, but it's still false.

If you really want to "reduce inadvertent mistakes", then the appropriate "default" behaviour would probably be to trigger an exception instead (like division by 0 often does, for instance). But some people will still want the wraparound method in some cases, so it can be useful to provide that. You can also provide the saturation/clamping version if you feel that is useful.

$\endgroup$
1
  • 1
    $\begingroup$ Wraparound doesn't behave differently for signed and unsigned integers. Both generate exactly the same bit pattern. Only the interpretation of the result is different. (And this breaks the assumption in the question that wraparound and saturation are equally viable, because saturation does require different hardware for signed vs unsigned operands) $\endgroup$
    – Ben Voigt
    Feb 26 at 17:28
0
$\begingroup$

Others have already pointed out that there are many different ways to handle this issue. And for existing languages, you can't change their behavior without breaking lots of existing code. So then the question is, what should the default behavior be for new languages? The ideal behavior would be that integers work like pure mathematical integers: they don't wrap, don't saturate, don't throw exceptions, and don't result in undefined behavior. I see two ways to implement this:

  1. Make the built-in integer type one that supports arbitrarily large integers. The downside is that operations will be slower and that it requires (potentially large) memory allocations.
  2. Make any operation on a fixed-size integer type result in a value of the next larger integer size. For example, the result of any of the mentioned operations on two 32-bit integers can always be represented using a 64-bit integer. The downside is that this quickly spirals out of control, and/or requires the programmer to safely cast the result back to a smaller integer size.

Wrapping and clamping are both useful in certain situations, but I wouldn't want to pick either of as the default behavior.

$\endgroup$
1
  • 2
    $\begingroup$ "The downside is that operations will be slower and that it requires (potentially large) memory allocations." the other downside is that it opens up DOS vulnerabilities see CVE-2020-10735 for an example. $\endgroup$ Feb 26 at 18:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .