7
$\begingroup$

I've always wondered. Why do major languages let their addition and multiplication operators be so prone to integer overflow? My programming language would have separate operators to handle overflow. Here's Haskell-esque pseudocode:

class RigCarry a where
    (+?) :: a -> a -> (a, a)
    (*?) :: a -> a -> (a, a)

class RigCarry a => RingCarry a where
    nagateCarry :: a -> (a, a)

So for example, in instance RigCarry Word8, 0x80 +? 0x80 would give (0x01, 0x00), and 0x80 *? 0x80 would give (0x40, 0x00).

Why don't major languages do this? Is this because of a hardware issue?

$\endgroup$
1
  • 2
    $\begingroup$ Consider that addition and multiplication are really separate cases. Multiplying two N-bit unsigned values, for example, can produce up to a 2N bit result (and thus N bits of overflow, a completely separate value of the same size), whereas adding them can only produce a single bit of overflow regardless of N. $\endgroup$ Jul 3, 2023 at 17:17

5 Answers 5

17
$\begingroup$

Overflow checking has a (small) cost

The hardware will always overflow. It doesn't care. In order to check if an overflow happened, you need extra instructions (typically just a single jc/jo [jump if carry/jump if overflow], I'd assume), which has a cost.

While this cost is small, since math additions are also very fast and you'll tend to do a lot of them, it adds up.

For example, in debug builds, Rust will check for overflows, but in release builds you have to opt in to that.

$\endgroup$
3
  • 1
    $\begingroup$ Swift always checks for this unless you explicitly tell it not to. Worse, it emits a separate ud2 instruction for each operation, so sometimes your assembly contains a field of ud2s. $\endgroup$
    – Bbrk24
    May 17, 2023 at 0:25
  • 4
    $\begingroup$ And carry flags are now out of fashion too, for obvious reasons. Modern OoO CPUs cannot afford having implicit dependencies between consequent ops (as in, there'll be as many carry flags as you have arithmetic ops in flight, selecting the right one without an explicit register reference is not easy). ISAs like RISC-V don't even have an implicit carry. $\endgroup$
    – SK-logic
    Jul 9, 2023 at 10:46
  • $\begingroup$ @SK-logic It was not obvious to me at all, until I read your comment! Very important point you make there. $\endgroup$
    – Pablo H
    Jul 18, 2023 at 12:24
7
$\begingroup$

In addition to @Radvylf Programs' answer, some compilers for languages like C/C++ which abuse undefined behaviour can make use of assuming that overflow simply does not exist, and eliminate branches where overflows would occur for sometimes huge optimizations: https://stackoverflow.com/questions/54510094/why-how-does-gcc-compile-the-undefined-behaviour-in-this-signed-overflow-test-so

$\endgroup$
1
  • 1
    $\begingroup$ "abuse" here is used very subjectively. I'd pronounce that as "understand". $\endgroup$ Jul 10, 2023 at 15:11
7
$\begingroup$

While overflow-trapped arithmetic may impose only a moderate cost to a non-optimizing compiler, most languages that support overflow trapping treat any signals, traps, exceptions, etc. as strongly sequenced behaviors. This means that a compiler given something like:

extern int f1(void);
extern void f2(int, int, int);

void test(int x, int y)
{
  int temp = x*y;
  if (f1())
    f2(temp, x, y);
}

would be required to perform the multiplication before calling f1(), and would not be able to skip the useless multiplication in cases where f1() would return zero.

In order for a language to allow compilers to perform an optimizing transform to yield:

extern int f1(void);
extern void f2(int, int, int);

void test(int x, int y)
{
  if (f1())
    f2(x*y, x, y);
}

it would be necessary to either:

  1. Specify that the multiplication will never have side effects,

  2. Characterize as Undefined Behavior all situations where the multiplication could have observable side effects, or

  3. Have a recognized category of "loosely sequenced" side effects which compilers would be allowed to reorder relative to other operations, and sometimes skip altogether, provided they didn't cross special ordering barriers.

IMHO, #3 would be the best approach, but I've not seen language designers use it. Of those two choices, #1 is vastly superior to #2, but #3 would be vastly better yet.

$\endgroup$
6
$\begingroup$

Aside from the runtime cost, representing the overflow in integer computations has an added complexity cost for the programmer. Unlike floats, where there is a NaN available to signal that something bad happened in the same value, we typically have no such reserved value for integers. For a scripting language it therefore makes more sense to go for BigIntegers that do not overflow, and for low level languages some default behaviour is chosen (trap, wrap, UB) to make it simple to work with.

$\endgroup$
3
$\begingroup$

Expressions are prone to overflow because computers are designed top to bottom to have that proneness.

Both the term "integer" and the syntax for expressions is drawn from traditional mathematics, but in fact in computing integers are invariably fixed-width and have a circular progression (unlike in mathematics by default), and the operations on these fixed-width integers are specified in a way (using an "expression" syntax that was developed in mathematics, which operates under different assumptions) that it is easy to lose track of when a result may exceed the specified width of storage.

$\endgroup$

You must log in to answer this question.

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