75

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.

  • 19
    just as a note, for C# you can use checked { } section to mark the parts of the code that should perform Arithmetic Overflow checks. This is due to performance – Paweł Łukasik May 8 '17 at 11:09
  • 14
    "Ever tried to sum up all numbers from 1 to 2,000,000 in your favorite programming language?" – Yes: (1..2_000_000).sum #=> 2000001000000. Another one of my favorite languages: sum [1 .. 2000000] --=> 2000001000000. Not my favorite: Array.from({length: 2000001}, (v, k) => k).reduce((acc, el) => acc + el) //=> 2000001000000. (To be fair, the last one is cheating.) – Jörg W Mittag May 8 '17 at 11:28
  • 27
    @BernhardHiller Integer in Haskell is arbitrary-precision, it will hold any number as long as you don't run out of allocatable RAM. – Polygnome May 8 '17 at 13:27
  • 50
    The Ariane 5 crash was caused by checking for an overflow that didn't matter - the rocket was in a part of the flight where the result of a calculation wasn't even needed any more. Instead, the overflow was detected, and that caused the flight to abort. – Simon B May 8 '17 at 15:16
  • 9
    But with the 10,000,000,000 repetitions, the time taken by a check is still less than 1 nanosecond. that's an indication of the loop being optimized out. Also that sentence contradicts previous numbers which appear very valid to me. – usr May 8 '17 at 15:40

14 Answers 14

85

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.

  • 9
    @DmitryGrigoryev unsigned int shouldn't come to mind because a language with overflow checking should be checking all integer types by default. You should have to write wrapping unsigned int. – immibis May 8 '17 at 21:07
  • 31
    I don't buy the cost argument. The CPU does check overflow on EVERY SINGLE integer calculation and set the carry flag in the ALU. It's the programming language support that's missing. A simple didOverflow() inline function or even a global variable __carry that allow access to the carry flag would cost zero CPU time if you don't use it. – slebetman May 9 '17 at 2:24
  • 37
    @slebetman: That's x86. ARM does not. E.g. ADD doesn't set the carry (you need ADDS). Itanium doesn't even have a carry flag. And even on x86, AVX doesn't have carry flags. – MSalters May 9 '17 at 8:40
  • 30
    @slebetman It sets the carry flag, yes (on x86, mind you). But then you have to read the carry flag and decide on the result - that's the expensive part. Since arithmetic operations are often used in loops (and tight loops at that), this can easily prevent many safe compiler optimizations that can have a very big impact on performance even if you only needed one extra instruction (and you need a lot more than that). Does it mean it should be the default? Maybe, especially in a language like C# where saying unchecked is easy enough; but you might be overestimating how often overflow matters. – Luaan May 9 '17 at 10:15
  • 11
    ARM's adds is the same price as add (it's just a instruction 1-bit flag that selects whether the carry flag is updated). MIPS's add instruction traps on overflow - you have to ask to not trap on overflow by using addu instead! – immibis May 9 '17 at 10:58
64

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.

  • 2
    Excellent answer. So what's your theory about why they decided to do it that way? Just copying everyone else who copied C and ultimately assembly and binary? – jpmc26 May 8 '17 at 23:32
  • 19
    When 99% of your user base expects a behavior, you tend to give it to them. And as for "copying C," it actually isn't a copy of C, but an extension of it. C guarantees exception free behavior for unsigned integers only. The behavior of signed integer overflow is actually undefined behavior in C and C++. Yes, undefined behavior. It just so happens that nearly everyone implements it as 2's complement overflow. C# actually makes it official, rather than leaving it UB like C/C++ – Cort Ammon May 8 '17 at 23:51
  • 10
    @CortAmmon: The language Dennis Ritchie designed had defined wraparound behavior for signed integers, but wasn't really suitable for use on non-two's-complement platforms. While allowing certain deviations from precise two's-complement wraparound can greatly assist some optimizations (e.g. allowing a compiler to replace x*y/y with x could save a multiplication and a division), compiler writers have interpreted Undefined Behavior not as an opportunity to do what makes sense for a given target platform and application field, but rather as an opportunity to throw sense out the window. – supercat May 9 '17 at 0:21
  • 3
    @CortAmmon - Check the code generated by gcc -O2 for x + 1 > x (where x is an int). Also see gcc.gnu.org/onlinedocs/gcc-6.3.0/gcc/… . 2s-complement behavior on signed overflow in C is optional, even in real compilers, and gcc defaults to ignoring it in normal optimization levels. – Jonathan Cast May 9 '17 at 5:06
  • 2
    @supercat Yeah, most C compiler writers are more interested in making sure some unrealistic benchmark runs 0.5% faster than trying to provide reasonable semantics to programmers (yes I understand why it's not an easy problem to solve and there are some reasonable optimisations that can cause unexpected results when combined, yada, yada but still it's just no focus and you notice it if you follow the conversations). Luckily there are some people who try to do better. – Voo May 9 '17 at 20:51
30

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.

  • 28
    That's somehow like saying that checks for Buffer Overflow should be omitted because they hardly ever occur... – Bernhard Hiller May 8 '17 at 12:48
  • 73
    @BernhardHiller: and that's exactly what C and C++ do. – Michael Borgwardt May 8 '17 at 13:08
  • 12
    @DavidBrown: As do arithmetic overflows. The former do not compromise the VM though. – Deduplicator May 8 '17 at 18:41
  • 35
    @Deduplicator makes an excellent point. The CLR was carefully designed so that verifiable programs cannot violate the invariants of the runtime even when bad stuff happens. Safe programs can of course violate their own invariants when bad stuff happens. – Eric Lippert May 8 '17 at 19:37
  • 7
    @svick Arithmetic operations are probably far more common than array indexing operations. And most integer sizes are large enough that it's very rare to perform arithmetic that overflows. So the cost-benefit ratios are very different. – Barmar May 9 '17 at 0:07
20

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.

  • 18
    It's definitely not an oversight in the design of C#. The designers of C# deliberately created two modes: checked and unchecked, added syntax for switching between them locally and also command line switches (and project settings in VS) to change it globally. You might disagree with making unchecked the default (I do), but all this is clearly very deliberate. – svick May 8 '17 at 17:05
  • 8
    @slebetman - just for the record: the cost here is not the cost of checking for the overflow (which is trivial), but the cost of running different code depending on whether the overflow happened (which is very expensive). CPUs do not like conditional branch statements. – Jonathan Cast May 9 '17 at 5:07
  • 5
    @jcast Wouldn't branch prediction on modern processors almost eliminate that conditional branch statement penalty? After all the normal case should be no overflow, so it's very predictable branching behavior. – CodeMonkey May 9 '17 at 8:01
  • 4
    Agree with @CodeMonkey. A compiler would put in a conditional jump in case of overflow, to a page that's normally not loaded/cold. The default prediction for that is "not taken", and it probably will not change. Total overhead is one instruction in the pipeline. But that is one instruction overhead per arithmetic instruction. – MSalters May 9 '17 at 8:47
  • 2
    @MSalters yes, there is an additional instruction overhead. And the impact might be large if you have exclusively CPU bound problems. In most applications with a mix of IO and CPU heavy code I'd assume the impact is minimal. I like the Rust way, of adding the overhead only in Debug builds, but removing it in Release builds. – CodeMonkey May 9 '17 at 8:56
20

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.

  • 6
    @DmitryGrigoryev that's the opposite of an effective way to check for overflows, for example on Haswell it reduces the throughput from 4 normal additions per cycle to only 1 checked addition, and that's before considering the impact of branch mispredictions of the jo's, and the more global effects of the pollution they add to the branch predictor state and the increased code size. If that flag was sticky it would offer some real potential.. and then you still can't do it properly in vectorized code. – user49272 May 8 '17 at 17:10
  • 2
    Since you're linking to a blog post written by John Regehr, I thought it would be appropriate to also link to another of his article, written a few months before the one you linked. These articles talk about different philosophies: In the earlier article, integers are fixed size; integer arithmetic are checked (i.e. the code can't continue its execution); there's either an exception or a trap. The newer article talks about ditching fixed-size integers altogether, which eliminates overflows. – rwong May 8 '17 at 20:05
  • 2
    @rwong Infinite-sized integers have their problems as well. If your overflow is the result of a bug (which it often is), it may turn a quick crash into a prolonged agony that consumes all server resources until everything fails horribly. I'm mostly a fan of the "fail early" approach - less chance of poisoning the whole environment. I'd prefer the Pascal-ish 1..100 types instead - be explicit about the expected ranges, rather than being "forced" into 2^31 etc. Some languages offer this, of course, and they tend to do overflow checking by default (sometimes at compile-time, even). – Luaan May 9 '17 at 10:34
  • 1
    @Luaan: What is interesting is that often times intermediate computations may temporarily overflow, but the result does not. For example, on your 1..100 range, x * 2 - 2 may overflow when x is 51 even though the result fits, forcing you to rearrange your computation (sometimes in unnatural way). In my experience, I've found that I generally prefer to run the computation in a larger type, and then check whether the result fits or not. – Matthieu M. May 9 '17 at 11:32
  • 1
    @MatthieuM. Yeah, that's where you get into the "sufficiently smart compiler" territory. Ideally, a value of 103 should be valid for a 1..100 type as long as it is never used in a context where a true 1..100 is expected (e.g. x = x * 2 - 2 should work for all x where the assignment results in a valid 1..100 number). That is, operations on the numeric type may have a higher precision than the type itself as long as the assignment fits. This would be quite useful in cases like (a + b) / 2 where ignoring (unsigned) overflows may be the correct option. – Luaan May 9 '17 at 11:48
10

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.

  • 2
    "it is fashionable for modern compilers..." -- similarly, it was briefly fashionable for the developers of certain well-known kernels to choose not to read the documentation regarding the optimisation flags they used, and then act angry all over the internet because they were forced to add even more compiler flags to get the behaviour they wanted ;-). In this case, -fwrapv results in defined behaviour, albeit not the behaviour the questioner wants. Granted, gcc optimisation does turn any kind of C development into a thorough exam on the standard and the compiler behaviour. – Steve Jessop May 9 '17 at 9:59
  • 1
    @SteveJessop: C would be a much healthier language if compiler writers recognized a low-level dialect where "undefined behavior" meant "do whatever would make sense on the underlying platform", and then added ways for programmers to waive unnecessary guarantees implied thereby, rather than presuming that the phrase "non-portable or erroneous" in the Standard simply means "erroneous". In many cases, the optimal code that can be obtained in a language with weak behavioral guarantees will be much better than can be obtained with stronger guarantees or no guarantees. For example... – supercat May 9 '17 at 15:18
  • 1
    ...if a programmer needs to evaluate x+y > z in a fashion that will never do anything other than yield 0 or yield 1, but either result would be equally acceptable in case of overflow, a compiler which offers that guarantee could often generate better code for the expression x+y > z than any compiler would be able to generate for a defensively-written version of the expression. Realistically speaking, what fraction of useful overflow-related optimizations would be precluded by a guarantee that integer calculations other than division/remainder will execute with no side-effects? – supercat May 9 '17 at 15:24
  • I confess that I'm not fully into the details, but the fact that your grudge is with "compiler writers" in general, and not specifically "someone on gcc who won't accept my -fwhatever-makes-sense patch", strongly suggests to me that there's more to it than whimsy on their part. The usual arguments I've heard are that code inlining (and even macro expansion) benefit from deducing as much as possible about the specific use of a code construct, since either thing commonly results in inserted code that deals with cases it doesn't need to, that the surrounding code "proves" impossible. – Steve Jessop May 9 '17 at 19:16
  • So for a simplified example, if I write foo(i + INT_MAX + 1), compiler-writers are keen to apply optimisations to the inlined foo() code which rely for correctness on its argument being non-negative (fiendish divmod tricks, perhaps). Under your additional restrictions, they could only apply optimisations whose behaviour for negative inputs makes sense for the platform. Of course, personally I'd be happy for that to be a -f option that switches on -fwrapv etc, and likely must disable some optimisations there's no flag for. But it's not like I can be bothered to do all that work myself. – Steve Jessop May 9 '17 at 19:31
9

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.

  • Note that there is a difference between detecting overflow (and then have a signal, panic, exception, ...) and switching to big nums. The former should be doable much more cheaply than the latter. – Matthieu M. May 9 '17 at 6:34
  • @MatthieuM. Absolutely - and I realize I am not clear about that in my answer. – Nemanja Trifunovic May 9 '17 at 12:19
7

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.

  • 10
    This was particularly the case for C#, which was in its early days compared to Java and C++ not on developer productivity metrics, which are hard to measure, or on cash-saved-from-not-dealing-with-security-breaches metrics, which are hard to measure, but on trivial performance benchmarks. – Eric Lippert May 8 '17 at 19:41
  • 1
    And likely, CPU's performance is checked with some simple number crunching. Thus optimizations for overflow detection may yield "bad" results on those tests. Catch22. – Bernhard Hiller May 11 '17 at 7:39
5

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.

3

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.

3

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.

  • 1
    I've sometimes wondered if the people who are pushing UB-driven insanity in C were secretly trying to undermine it in favor of some other language. That would make sense. – supercat May 9 '17 at 23:37
  • Treating x+1>x as unconditionally true would not require a compiler to make any "assumptions" about x if a compiler is allowed to evaluate integer expressions using arbitrary larger types as convenient (or behave as though it's doing so). A nastier example of overflow-based "assumptions" would be deciding that given uint32_t mul(uint16_t x, uint16_t y) { return x*y & 65535u; } a compiler can use sum += mul(65535, x) to decide that x cannot be greater than 32768 [behavior that would likely shock the people who wrote the C89 Rationale, which suggests that one of the deciding factors... – supercat May 11 '17 at 19:47
  • ...in making unsigned short promote to signed int was the fact that two's-complement silent-wraparound implementations (i.e. the majority of C implementations then in use) would treat code like the above the same way whether unsigned short promoted to int or unsigned. The Standard didn't require implementations on silent-wraparound two's-complement hardware to treat code like the above sanely, but the authors of the Standard seem to have expected that they'd do so anyhow. – supercat May 11 '17 at 19:50
2

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#.

  • I came here to give this answer as well. – Mr Lister May 11 '17 at 20:39
  • Unfortunately, some people seem to regard as grossly unreasonable the notion that people writing low-level C code on a platform should have the audacity to expect that a C compiler suitable for such purpose would behave in constrained fashion in case of overflow. Personally, I think it reasonable for a compiler to behave as though computations are performed using arbitrarily-extended precision at the compiler's convenience (so on a 32-bit system, if x==INT_MAX, then x+1 might arbitrarily behave as either +2147483648 or -2147483648 at the compiler's convenience), but... – supercat May 11 '17 at 21:56
  • some people seem to think that if x and y are uint16_t and code on a 32-bit system computes x*y & 65535u when y is 65535, a compiler should assume that code will never be reached when x is greater than 32768. – supercat May 11 '17 at 21:59
1

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.

-1

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'.
  • 3
    It's not really possible for a programmer to add efficient overflow checking if a language doesn't provide for it. If a function computes a value that is ignored, a compiler can optimize out the computation. If a function computes a value which is overflow-checked but otherwise ignored, a compiler must perform the computation and trap if it overflows, even if an overflow would otherwise not affect the program's output and could be safely ignored. – supercat May 9 '17 at 0:23
  • 1
    You can't go from INT_MAX to INT_MIN by multiplying by -1. – David Conrad May 9 '17 at 8:34
  • The solution is obviously to provide a way for the programmer to turn the checks off in a given block of code or compilation unit. – David Conrad May 9 '17 at 8:34
  • for(i=0;i>=0;++i){...} is the style of code I try to discourage in my team: it relies on special effects / side effects and does not express clearly what it is meant to do. But still I appreciate your answer as it shows a different programming paradigm. – Bernhard Hiller May 10 '17 at 8:03
  • 1
    @Delioth: If i is a 64-bit type, even on an implementation with consistent silent-wraparound two's-complement behavior, running a billion iterations per second, such a loop could only be guaranteed to find the largest int value if it's allowed to run for hundreds of years. On systems which don't promise consistent silent-wraparound behavior, such behaviors would not be guaranteed no matter how long code is given. – supercat May 10 '17 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.