Why is Arithmetic Overflow ignored?

Question

Ever tried to sum up all numbers from 1 to 2,000,000 in your favorite programming language? The result is easy to calculate manually: 2,000,001,000,000, which some 900 times larger than the maximum value of an unsigned 32bit integer.

C# prints out -1453759936 - a negative value! And I guess Java does the same.

That means there are some common programming languages which ignore Arithmetic Overflow by default (in C#, there are hidden options for changing that). That's a behavior which looks very risky to me, and wasn't the crash of Ariane 5 caused by such an overflow?

So: what are the design decisions behind such a dangerous behavior?

Edit:

The first answers to this question express the excessive costs of checking. Let's execute a short C# program to test this assumption:

Stopwatch watch = Stopwatch.StartNew();
checked
{
    for (int i = 0; i < 200000; i++)
    {
        int sum = 0;
        for (int j = 1; j < 50000; j++)
        {
            sum += j;
        }
    }
}
watch.Stop();
Console.WriteLine(watch.Elapsed.TotalMilliseconds);

On my machine, the checked version takes 11015ms, while the unchecked version takes 4125ms. I.e. the checking steps take almost twice as long as adding the numbers (in total 3 times the original time). But with the 10,000,000,000 repetitions, the time taken by a check is still less than 1 nanosecond. There may be situation where that is important, but for most applications, that won't matter.

Edit 2:

I recompiled our server application (a Windows service analyzing data received from several sensors, quite some number crunching involved) with the /p:CheckForOverflowUnderflow="false" parameter (normally, I switch the overflow check on) and deployed it on a device. Nagios monitoring shows that the average CPU load stayed at 17%.

This means that the performance hit found in the made-up example above is totally irrelevant for our application.

Answer 1

There are 3 reasons for this:

1. The cost of checking for overflows (for every single arithmetic operation) at run-time is excessive.

2. The complexity of proving that an overflow check can be omitted at compile-time is excessive.

3. In some cases (e.g. CRC calculations, big number libraries, etc) "wrap on overflow" is more convenient for programmers.

Answer 2

Who says it's a bad tradeoff?!

I run all of my production apps with overflow checking enabled. This is a C# compiler option. I actually benchmarked this and I was not able to determine the difference. The cost of accessing the database to generate (non-toy) HTML overshadows the overflow checking costs.

I do appreciate the fact that I know that no operations overflow in production. Almost all code would behave erratically in the presence of overflows. The bugs would not be benign. Data corruption is likely, security issues a possibility.

In case I need the performance, which is sometimes the case, I disable overflow checking using unchecked {} on a granular basis. When I want to call out that I rely on an operation not overflowing I might redundantly add checked {} to the code to document that fact. I am mindful of overflows but I don't necessarily need to be thanks to the checking.

I believe the C# team made the wrong choice when they chose to not check overflow by default but that choice is now sealed in due to strong compatibility concerns. Note, that this choice was made around the year 2000. Hardware was less capable and .NET did not have a lot of traction yet. Maybe .NET wanted to appeal to Java and C/C++ programmers in this way. .NET is also meant to be able to be close to the metal. That's why it has unsafe code, structs and great native call abilities all of which Java does not have.

The faster our hardware gets and the smarter out compilers get the more attractive overflow checking by default is.

I also believe that overflow checking is often better than infinitely sized numbers. Infinitely sized numbers have a performance cost that is even higher, harder to optimize (I believe) and they open up the possibility of unbounded resource consumption.

JavaScript's way of dealing with overflow is even worse. JavaScript numbers are floating point doubles. An "overflow" manifests itself as leaving the fully precise set of integers. Slightly wrong results will occur (such as being off by one - this can turn finite loops into infinite ones).

For some languages such as C/C++ overflow checking by default is clearly inappropriate because the kinds of applications that are being written in these languages need bare metal performance. Still, there are efforts to make C/C++ into a safer language by allowing to opt in into a safer mode. This is commendable since 90-99% of code tends to be cold. An example is the fwrapv compiler option that forces 2's complement wrapping. This is a "quality of implementation" feature by the compiler, not by the language.

Haskell has no logical call stack and no specified evaluation order. This makes exceptions occur at unpredictable points. In a + b it is unspecified whether a or b is evaluated first and whether those expressions terminate at all or not. Therefore, it makes sense for Haskell to use unbounded integers most of the time. This choice is suitable to a purely functional language because exceptions are really inappropriate in most Haskell code. And division by zero is indeed a problematic point in Haskells language design. Instead of unbounded integers they could have used fixed-width wrapping integers as well but that does not fit with the "focus on correctness" theme that the language features.

An alternative to overflow exceptions are poison values that are created by undefined operations and propagate through operations (like the float NaN value). That seems far more expensive than overflow checking and makes all operations slower, not just the ones that can fail (barring hardware acceleration which floats commonly have and ints commonly do not have - although Itanium has NaT which is "Not a Thing"). I also do not quite see the point of making the program continue to limp along with bad data. It's like ON ERROR RESUME NEXT. It hides errors but does not help get correct results. supercat points out that it's sometimes a performance optimization to do this.

Answer 3

Because it's a bad trade-off to make all calculations a lot more expensive in order to automatically catch the rare case that an overflow does occur. It's much better to burden the programmer with recognizing the rare cases where this is an issue and add special preventions than to make all programmers pay the price for functionality that they don't use.

Answer 4

what are the design decisions behind such a dangerous behavior?

"Don't force users to pay a performance penalty for a feature they may not need."

It's one of the most basic tenets in the design of C and C++, and stems from a different time when you had to go through ridiculous contortions to get barely adequate performance for tasks that are today considered trivial.

Newer languages break with this attitude for many other features, such as array bounds checking. I'm not sure why they didn't do it for overflow checking; it could be simply an oversight.

Answer 5

Legacy

I would say that the issue is likely rooted in legacy. In C:

• signed overflow is undefined behavior (compilers support flags to make it wrap),
• unsigned overflow is defined behavior (it wraps).

This was done to get the best possible performance, following the principle that the programmer knows what it's doing.

Leads to Statu-Quo

The fact that C (and by extension C++) do not require the detection of overflow in turns means that overflow checking is sluggish.

Hardware mostly caters to C/C++ (seriously, x86 has a strcmp instruction (aka PCMPISTRI as of SSE 4.2)!), and since C doesn't care, common CPUs do not offer efficient ways of detecting overflows. In x86, you have to check a per-core flag after each potentially overflowing operation; when what you'd really want is a "tainted" flag on the result (much like NaN propagates). And vector operations may be even more problematic. Some new players may appear on the market with efficient overflow handling; but for now x86 and ARM do not care.

Compiler optimizers are not good at optimizing overflow checks, or even optimizing in the presence of overflows. Some academics such as John Regher complain about this statu-quo, but the fact is that when the simple fact of making overflows "failures" prevents optimizations even before the assembly hits the CPU can be crippling. Especially when it prevents auto-vectorization...

With cascading effects

So, in the absence of efficient optimization strategies and efficient CPU support, overflow-checking is costly. Much more costly than wrapping.

Add in some annoying behavior, such as x + y - 1 may overflow when x - 1 + y doesn't, which may legitimately annoy users, and overflow-checking is generally discarded in favor of wrapping (which handles this example and many others gracefully).

Still, not all hope is lost

There has been an effort in the clang and gcc compilers to implement "sanitizers": ways to instrument binaries to detect cases of Undefined Behavior. When using -fsanitize=undefined, signed overflow is detected and aborts the program; very useful during testing.

The Rust programming language has overflow-checking enabled by default in Debug mode (it uses wrapping arithmetic in Release mode for performance reasons).

So, there is growing concern about overflow-checking and the dangers of bogus results going undetected, and hopefully this will in turn spark interest in the research community, compiler community and hardware community.

Answer 6

Languages which attempt to detect overflows have historically defined the associated semantics in ways that severely restricted what would otherwise have been useful optimizations. Among other things, while it will often be useful to perform computations in a different sequence from what is specified in code, most languages that trap overflows guarantee that given code like:

for (int i=0; i<100; i++)
{
  Operation1();
  x+=i;
  Operation2();
}

if the starting value of x would cause an overflow to occur on the 47th pass through the loop, Operation1 will execute 47 times and Operation2 will execute 46. In the absence of such a guarantee, if nothing else within the loop uses x, and nothing will use the value of x following a thrown exception by Operation1 or Operation2, code could be replaced with:

x+=4950;
for (int i=0; i<100; i++)
{
  Operation1();
  Operation2();
}

Unfortunately, performing such optimizations while guaranteeing correct semantics in cases where an overflow would have occurred within the loop is difficult--essentially requiring something like:

if (x < INT_MAX-4950)
{
  x+=4950;
  for (int i=0; i<100; i++)
  {
    Operation1();
    Operation2();
  }
}
else
{
  for (int i=0; i<100; i++)
  {
    Operation1();
    x+=i;
    Operation2();
  }
}

If one considers that a lot of real-world code uses loops that are more involved, it will be obvious that optimizing code while preserving overflow semantics is difficult. Further, because of caching issues, it's entirely possible that the increase in code size would make the overall program run more slowly even though there are fewer operations on the commonly-executed path.

What would be needed to make overflow detection inexpensive would be a defined set of looser overflow-detection semantics which would make it easy for code to report whether a computation was performed without any overflows that might have affected the results(*), but without burdening the compiler with details beyond that. If a language spec were focused on reducing the cost of overflow detection to the bare minimum necessary to achieve the above, it could be made much less costly than it is in existing languages. I'm unaware of any efforts to facilitate efficient overflow detection, however.

(*) If a language promises that all overflows will be reported, then an expression like x*y/y cannot be simplified to x unless x*y can be guaranteed not to overflow. Likewise, even if the result of a computation would be ignored, a language that promises to report all overflows will need to perform it anyway so it can perform the overflow check. Since overflow in such cases cannot result in arithmetically-incorrect behavior, a program would not need to perform such checks to guarantee that no overflows have caused potentially-inaccurate results.

Incidentally, overflows in C are especially bad. Although almost every hardware platform that supports C99 uses two's-complement silent-wraparound semantics, it is fashionable for modern compilers to generate code which may cause arbitrary side-effects in case of overflow. For example, given something like:

#include <stdint.h>
uint32_t test(uint16_t x, uint16_t y) { return x*y & 65535u; }
uint32_t test2(uint16_t q, int *p)
{
  uint32_t total=0;
  q|=32768;
  for (int i = 32768; i<=q; i++)
  {
    total+=test(i,65535);
    *p+=1;
  }
  return total;
}

GCC will generate code for test2 which unconditionally increments (*p) once and returns 32768 regardless of the value passed into q. By its reasoning, the computation of (32769*65535) & 65535u would cause an overflow and there is thus no need for the compiler to consider any cases where (q | 32768) would yield a value larger than 32768. Even though there is no reason that the computation of (32769*65535) & 65535u should care about the upper bits of the result, gcc will use signed overflow as justification for ignoring the loop.

Answer 7

Not all programming languages ignore integer overflows. Some languages provide safe integer operations for all numbers (most Lisp dialects, Ruby, Smalltalk,...) and others via libraries - for instance there are various BigInt classes for C++.

Whether a language makes integer safe from overflow by default or not depends on its purpose: system languages like C and C++ need to provide zero cost abstractions and "big integer" is not one. Productivity languages, such as Ruby, can and do provide big integers out of the box. Languages such as Java and C# that are somewhere in between should IMHO go with the safe integers out of the box, by they don't.

Answer 8

As you have shown, C# would have been 3 times slower if it had overflow checks enabled by default (assuming your example is a typical application for that language). I agree that performance is not always the most important feature, but languages / compilers are typically compared on their performance in typical tasks. This is in part due to the fact that the quality of language features is somewhat subjective, while a performance test is objective.

If you were to introduce a new language which is similar to C# in most aspects but 3 times slower, getting a market share wouldn't be easy, even if in the end most of your end users would benefit from overflow checks more than they would from higher performance.

Answer 9

Beyond the many answers that justify lack of overflow checking based on performance, there are two different kinds of arithmetic to consider:

1. indexing calculations (array indexing and/or pointer arithmetic)

2. other arithmetic

If the language uses an integer size that is the same as the pointer size, then a well constructed program will not overflow doing indexing calculations because it would necessarily have to run out of memory before the indexing calculations would cause overflow.

Thus, checking memory allocations is sufficient when working with pointer arithmetic and indexing expressions involving allocated data structures. For example, if you have a 32-bit address space, and use 32-bit integers, and allow a maximum of 2GB of heap to allocated (about half the address space), indexing/pointer calculations (basically) will not overflow.

Further, you might be surprised as to how much of addition/subtraction/multiplication involves array indexing or pointer calculation, thus falling into the first category. Object pointer, field access, and array manipulations are indexing operations, and many programs do no more arithmetic computation than these! Essentially, this the primary reason that programs work as well as they do without integer overflow checking.

All non-indexing and non-pointer computations should be classified as either those that want/expect overflow (e.g. hashing computations), and those that don't (e.g. your summation example).

In the latter case, programmers will often use alternative data types, such as double or some BigInt. Many calculations require a decimal data type rather than double, e.g. financial calculations. If they don't and stick with integer types, then they need to take care to check for integer overflow -- or else, yes, the program can reach an undetected error condition as you're pointing out.

As programmers, we need to be sensitive to our choices in numeric data types and the consequences of them in terms of the possibilities for overflow, not to mention precision. In general (and especially when working with the C family of languages with the desire to use the fast integer types) we need to be sensitive to and aware of the differences between indexing calculations vs. others.

Answer 10

In Swift, any integer overflows are detected by default and instantly stop the program. In cases where you need wraparound behaviour, there are different operators &+, &- and &* that achieve that. And there are functions that perform an operation and tell whether there was an overflow or not.

It's fun to watch beginners try to evaluate the Collatz sequence and have their code crash :-)

Now the designers of Swift are also the designers of LLVM and Clang, so they know a bit or two about optimisation, and are quite capable of avoiding unnecessary overflow checks. With all optimisations enabled, overflow checking doesn't add much to code size and execution time. And since most overflows lead to absolutely incorrect results, it's code size and execution time well spent.

PS. In C, C++, Objective-C signed integer arithmetic overflow is undefined behaviour. That means whatever the compiler does in the case of signed integer overflow is correct, by definition. Typical ways to cope with signed integer overflow is to ignore it, taking whatever result the CPU gives you, building assumptions into the compiler that such overflow will never happen (and conclude for example that n+1 > n is always true, since overflow is assumed to never happen), and a possibility that is rarely used is to check and crash if overflow happens, like Swift does.

Answer 11

The language Rust provides an interesting compromise between checking for overflows and not, by adding the checks for the debugging build and removing them in the optimized release version. This allows you to find the bugs during testing, while still getting full performance in the final version.

Because the overflow wraparound is sometimes wanted behaviour, there are also versions of the operators that never checks for overflow.

You can read more about the reasoning behind the choice in the RFC for the change. There is also plenty of interesting information in this blog post, including a list of bugs that this feature has helped with catching.

Answer 12

Actually, the real cause for this is purely technical/historical: CPU's ignore sign for the most part. There generally is only a single instruction to add two integers in registers, and the CPU does not care a bit whether you interpret these two integers as signed or unsigned. The same goes for subtraction, and even for multiplication. The only arithmetic operation that needs to be sign-aware is the division.

The reason why this works, is the 2's complement representation of signed integers that is used by virtually all CPUs. For instance, in 4-bit 2's complement the addition of 5 and -3 looks like this:

  0101   (5)
  1101   (-3)
(11010)  (carry)
  ----
  0010   (2)

Observe how the wrap-around behavior of throwing away the carry-out bit yields the correct signed result. Likewise, CPUs usually implement the subtraction x - y as x + ~y + 1:

  0101   (5)
  1100   (~3, binary negation!)
(11011)  (carry, we carry in a 1 bit!)
  ----
  0010   (2)

This implements subtraction as an addition in hardware, tweaking only the inputs to the arithmetical-logical-unit (ALU) in trivial ways. What could be simpler?

Since multiplication is nothing else than a sequence of additions, it behaves in a similarly nice way. The result of using 2's complement representation and ignoring the carry out of arithmetic operations is simplified circuitry, and simplified instruction sets.

Obviously, since C was designed to work close to the metal, it adopted this exact same behavior as the standardized behavior of unsigned arithmetic, allowing only signed arithmetic to yield undefined behavior. And that choice carried over to other languages like Java, and, obviously, C#.

Answer 13

Some answers have discussed the cost of checking, and you've edited your answer to dispute that this is a reasonable justification. I'll try to address those points.

In C and C++ (as examples), one of the languages design principles is not to provide functionality that wasn't asked for. This is commonly summed up by the phrase "don't pay for what you don't use". If the programmer wants overflow checking then s/he can ask for it (and pay the penalty). This makes the language more dangerous to use, but you choose to work with the language knowing that, so you accept the risk. If you don't want that risk, or if you are writing code where safety is of paramount performance, then you can select a more appropriate language where the performance/risk tradeoff is different.

But with the 10,000,000,000 repetitions, the time taken by a check is still less than 1 nanosecond.

There are a few things wrong with this reasoning:

1. This is environment specific. It generally makes very little sense to quote specific figures like this, because code is written for all sorts of environments that vary by orders of magnitude in terms of their performance. Your 1 nanosecond on a (I assume) desktop machine might seem amazingly fast to someone coding for an embedded environment, and unbearably slow to someone coding for a super computer cluster.

2. 1 nanosecond might seem like nothing for a segment of code that runs infrequently. On the other hand, if it is in an inner loop of some calculation that is the main function of the code, then every single fraction of time you can shave off can make a big difference. If you're running a simulation on a cluster then those saved fractions of a nanosecond in your inner loop can translate directly to money spent on hardware and electricity.

3. For some algorithms and contexts, 10,000,000,000 iterations could be insignificant. Again, it doesn't generally make sense to talk about specific scenarios that only apply in certain contexts.

There may be situation where that is important, but for most applications, that won't matter.

Perhaps you are right. But again, this is a matter of what the goals of a particular language are. Many languages are in fact designed to accommodate the needs of "most" or to favour safety over other concerns. Others, like C and C++, prioritise on efficiency. In that context, making everyone pay a performance penalty simply because most people won't be bothered, goes against what the language is trying to achieve.

Answer 14

There are good answers, but I think there's a missed point here: the effects of an integer overflow aren't necessarily a bad thing, and after-the-fact it's difficult to know whether i went from being MAX_INT to being MIN_INT was due to an overflow problem or if it was intentionally done by multiplying by -1.

For example, if I want to add all the representable integers greater than 0 together, I'd just use a for(i=0;i>=0;++i){...} addition loop- and when it overflows it stops the addition, which is the goal behavior (throwing an error would mean I have to circumvent an arbitrary protection because it's interfering with standard arithmetic). It's bad practice to restrict primitive arithmetics, because:

• They're used in everything- a slowdown in primitive maths is a slowdown in every functioning program
• If a programmer needs them, they can always add them
• If you have them and the programmer doesn't need them (but does need faster runtimes), they can't remove them easily for optimization
• If you have them and the programmer needs them to not be there (like in the example above), the programmer is both taking the run-time hit (which may or may not be relevant), and the programmer still needs to invest time removing or working around the 'protection'.