5 ms·

> adding two large integers can result in an integer that cannot be represented in the integer type. We often refer to such error conditions as overflows. Ther

> adding two large integers can result in an integer that cannot be represented in the integer type. We often refer to such error conditions as overflows. There's a subtlety here that's missed in the article: In C and C++ this is only called "overflow" for signed integers. That's because that word specifically refers to the case where the behaviour is undefined, and for unsigned integers the result is always well defined: it is the correct result modulo the size of the integer type (which must be a power of 2). For example, UINT_MAX + 1 is guaranteed to equal 0. In particular, the -ftrapv flag mentioned in the article is described in the GCC docs as (emphasis mine): > This option generates traps for signed overflow on addition, subtraction, multiplication operations. (Another subtlety, albeit a bit less likely to cause confusion: with signed integers it's possible that the result is negative but doesn't fit into the type, e.g. INT_MIN-1, and this is also called overflow. I mention it because it's tempting to call this "underflow", but that word is reserved for talking about floating point numbers where the result is too small in magnitude to be represented by a non-zero value.) I don't know Swift at all so I'm quite curious about this bit of the article: > In a programming languages like Swift, an overflow will result in the program aborting its execution. Unfortunately, because the article is sloppy about the meaning of "overflow", I don't know how to interpret it. Is it just about signed numbers or not? Also, what other languages are there that are "like Swift"?

loa_in_ 6y ago
So overflow means overflow, but underflow as well, while underflow means precision loss. What a bad case of misnomers.
- bregma 6y ago
  To be fair it's not just underflow, but equality that differs between numeric types. The equality of signed and unsigned integers might not mean what you think it means, but it's exact. The equality of real-valued types always means what you think it means, but it's inexact so you need to write it as "close enough to" instead of "equals". With integers, "overflow" means "wrap around because the internal representation is really on a modulo field" whereas with floating point "overflow" means "the result is NAN or INF" and undeflow means "the result is NAN or zero or DENORM" but it's awkward to use such phrases in everyday conversation. Especially to your boss, whose eyes glaze over when you start using such words and he'll just interrupt with a "when will the JIRA be done? I have another meeting in five." The rule of thumb is that you have to know what you're doing to use lower-level languages like C++. That already eliminates 80% of the programmers out there but thank goodness there are high-level languages that reduce to simplistic concepts and let software be churned out at a rapid pace.
- tom_mellior 6y ago
  Overflow doesn't mean underflow. Overflow means overflow. You can use "negative overflow" for the special case of overflow where a negative number's magnitude is too big. Though why would you care about the difference between positive and negative overflow, really?
amelius 6y ago
We probably need different integer types to express the differences. Perhaps whether or not we check for overflow can be encoded in the type of the integer.
- pjc50 6y ago
  Yes. For some time I've wondered about doing a programming language for conservative arithmetic, in which you don't ask for "integer" but specify "32-bit signed, exception on overflow" or "16-bit, do not exception immediately but set a flag which I can check at the end of the function" or "8-bit, use saturation arithmetic". The exact opposite of the scripting language "everything is just a thing and you can add numbers to strings or whatever idk". Saturation arithmetic is useful in e.g. audio codecs as it corresponds to "clipping"; there's hardware support for it in some SIMD instruction sets and I think it's required for some compression standards. But compilers won't generate it because there's no way to easily represent it in most languages other than hope for pattern-matching in the optimizer. Would also be a good place for "please compile this function with constant execution time regardless of inputs and fail if you can't do that", useful for crypto.
  - jandrewrogers 6y ago
    People have written C++ libraries for integer type generation that allow you to specify many properties including various types of arithmetic and runtime behavior. It is pretty transparent to the programmer and efficient. However, there is real complexity, in terms of library implementation, in figuring out how this zoo of exotic integer types interact with each other consistently and correctly. Doubly so if you want the safety of these interactions to be verified at compile-time to the extent possible.
    - amelius 6y ago
      I think you also want to use the hardware capabilities of the target platform (overflow detection, automatic trapping) as much as possible and at the same time also allow all other integer arithmetic optimizations. Not sure if all of this can be done from within a user library.
stabbles 6y ago
How does this relate to the change in the C++20 standard about two's complement? "signed integers are now defined to be represented using two's complement (signed integer overflow remains undefined behavior)"
- gumby 6y ago
  That change was simply to reflect de facto reality, removing some undefined behavior in order to make life easier for people writing portable code. I haven’t seen a ones complement machine in decades.
  - quietbritishjim 6y ago
    That makes it sound like, in the old spec, you could totally ignore the problem so long as your particular architecture is two's complement. But that's not true: remember that C and C++ are (notoriously) not just high-level assembly, but instead are defined against an abstract virtual machine. What that means in practice is that if your code invokes any undefined behaviour, even if it seems like it ought to work in a particular way given the actual machine it runs on, then the optimiser is allowed to do whatever it likes. For example, if you convert a number from unsigned to signed and then test `if (x<0)` then the compiler is allowed to optimise away that whole if statement because there's no standards-compliant program that would ever take that path. As another example, if the compiler can prove that a value will be greater than INT_MAX and then you convert it to signed then the computer is allowed to replace that conversion, and the code following it, with a call to `abort()` – after all, no compliant program could possibly follow that path so it can assume that what it has really proved is that that code will never be executed. This change to the standard means you don't need to worry about those possibilities, even on machines that actually are two's complement.
- quietbritishjim 6y ago
  The main effect is that you can convert from an unsigned number to a signed number and it will do what you would expect from a two's complement representation. Previously this was undefined behaviour (not even just implementation defined!) if the value was greater than would fit in the signed type. This was true even if you were doing an explicit cast, so doing the conversion in a safe way was notoriously fiddly. [1] Converting signed to unsigned had always been fine, all the way back to C89 I believe. That was specified as being converted modulo 2^N, which matches what happens naturally with two's complement, even on architectures that aren't. (With the change in C++20 the wording for this conversion is simplified, but the effect is unchanged.) The introduction of the proposal [2] lists some other changes and non-changes. It mentions that demanding wrapping behaviour in arithmetic operations had been a goal of the proposal but there was strong resistance to it so it was dropped. One thing that stands out is that right shift of negative numbers is now defined as sign-extended rather than undefined behaviour, which I think had probably caught a lot of people out in the past. Oddly, it mentions signed to unsigned conversion as a change even though it's effectively the same as before, and signed to unsigned isn't mentioned in the introduction at all even though that's a major change. The rest are mainly to do with representations e.g. if you're memcopying to or from signed numbers. [1] https://stackoverflow.com/questions/13150449/efficient-unsigned-to-signed-cast-avoiding-implementation-defined-behavior https://stackoverflow.com/questions/13150449/efficient-unsig... [2] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0907r1.html http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p090...
masklinn 6y ago
> Is it just about signed numbers or not? No. You can plug an `UInt8(255)` in an online playground and try to increment it, it’ll crash unless you use an overflowing operator. > Also, what other languages are there that are "like Swift"? In debug mode, Rust will panic on overflow (regardless of signing). You can also enable overflow-checks in release mode.
- zeotroph 6y ago
  So is Swift effectively adding a jo / jump on overflow instruction after each normal integer operation?
  - saeta 6y ago
    `+` is checked for overflow by default (can be overridden with compiler flags), and `&+` is overflowing addition and does auto-vectorize equivalently to C++. I'd be quite interested in seeing a benchmark comparing checked and unchecked addition that doesn't get auto-vectorized to understand the performance in practice for non-numerical computing.
- bregma 6y ago
  Huh. That would make classic LCG PRNGs pretty useless. I guess it's "safer" in that it prevents rare dangerous edge cases at the expense of common everyday safe operations, but that's a tradeoff.
  - twic 6y ago
    For your LCG you would use an explicitly wrapping type: https://doc.rust-lang.org/std/num/struct.Wrapping.html https://doc.rust-lang.org/std/num/struct.Wrapping.html
  - OskarS 6y ago
    If you want the wrapping behaviour (like with an LCG), you can prepend the operator with an ampersand(i.e &+ instead of +).
  - masklinn 6y ago

loa_in_ 6y ago

So overflow means overflow, but underflow as well, while underflow means precision loss. What a bad case of misnomers.

bregma 6y ago
To be fair it's not just underflow, but equality that differs between numeric types. The equality of signed and unsigned integers might not mean what you think it means, but it's exact. The equality of real-valued types always means what you think it means, but it's inexact so you need to write it as "close enough to" instead of "equals". With integers, "overflow" means "wrap around because the internal representation is really on a modulo field" whereas with floating point "overflow" means "the result is NAN or INF" and undeflow means "the result is NAN or zero or DENORM" but it's awkward to use such phrases in everyday conversation. Especially to your boss, whose eyes glaze over when you start using such words and he'll just interrupt with a "when will the JIRA be done? I have another meeting in five." The rule of thumb is that you have to know what you're doing to use lower-level languages like C++. That already eliminates 80% of the programmers out there but thank goodness there are high-level languages that reduce to simplistic concepts and let software be churned out at a rapid pace.
tom_mellior 6y ago
Overflow doesn't mean underflow. Overflow means overflow. You can use "negative overflow" for the special case of overflow where a negative number's magnitude is too big. Though why would you care about the difference between positive and negative overflow, really?

amelius 6y ago

We probably need different integer types to express the differences. Perhaps whether or not we check for overflow can be encoded in the type of the integer.

pjc50 6y ago
Yes. For some time I've wondered about doing a programming language for conservative arithmetic, in which you don't ask for "integer" but specify "32-bit signed, exception on overflow" or "16-bit, do not exception immediately but set a flag which I can check at the end of the function" or "8-bit, use saturation arithmetic". The exact opposite of the scripting language "everything is just a thing and you can add numbers to strings or whatever idk". Saturation arithmetic is useful in e.g. audio codecs as it corresponds to "clipping"; there's hardware support for it in some SIMD instruction sets and I think it's required for some compression standards. But compilers won't generate it because there's no way to easily represent it in most languages other than hope for pattern-matching in the optimizer. Would also be a good place for "please compile this function with constant execution time regardless of inputs and fail if you can't do that", useful for crypto.
- jandrewrogers 6y ago
  People have written C++ libraries for integer type generation that allow you to specify many properties including various types of arithmetic and runtime behavior. It is pretty transparent to the programmer and efficient. However, there is real complexity, in terms of library implementation, in figuring out how this zoo of exotic integer types interact with each other consistently and correctly. Doubly so if you want the safety of these interactions to be verified at compile-time to the extent possible.
  - amelius 6y ago
    I think you also want to use the hardware capabilities of the target platform (overflow detection, automatic trapping) as much as possible and at the same time also allow all other integer arithmetic optimizations. Not sure if all of this can be done from within a user library.

stabbles 6y ago

How does this relate to the change in the C++20 standard about two's complement? "signed integers are now defined to be represented using two's complement (signed integer overflow remains undefined behavior)"

gumby 6y ago
That change was simply to reflect de facto reality, removing some undefined behavior in order to make life easier for people writing portable code. I haven’t seen a ones complement machine in decades.
- quietbritishjim 6y ago
  That makes it sound like, in the old spec, you could totally ignore the problem so long as your particular architecture is two's complement. But that's not true: remember that C and C++ are (notoriously) not just high-level assembly, but instead are defined against an abstract virtual machine. What that means in practice is that if your code invokes any undefined behaviour, even if it seems like it ought to work in a particular way given the actual machine it runs on, then the optimiser is allowed to do whatever it likes. For example, if you convert a number from unsigned to signed and then test `if (x<0)` then the compiler is allowed to optimise away that whole if statement because there's no standards-compliant program that would ever take that path. As another example, if the compiler can prove that a value will be greater than INT_MAX and then you convert it to signed then the computer is allowed to replace that conversion, and the code following it, with a call to `abort()` – after all, no compliant program could possibly follow that path so it can assume that what it has really proved is that that code will never be executed. This change to the standard means you don't need to worry about those possibilities, even on machines that actually are two's complement.
quietbritishjim 6y ago
The main effect is that you can convert from an unsigned number to a signed number and it will do what you would expect from a two's complement representation. Previously this was undefined behaviour (not even just implementation defined!) if the value was greater than would fit in the signed type. This was true even if you were doing an explicit cast, so doing the conversion in a safe way was notoriously fiddly. [1] Converting signed to unsigned had always been fine, all the way back to C89 I believe. That was specified as being converted modulo 2^N, which matches what happens naturally with two's complement, even on architectures that aren't. (With the change in C++20 the wording for this conversion is simplified, but the effect is unchanged.) The introduction of the proposal [2] lists some other changes and non-changes. It mentions that demanding wrapping behaviour in arithmetic operations had been a goal of the proposal but there was strong resistance to it so it was dropped. One thing that stands out is that right shift of negative numbers is now defined as sign-extended rather than undefined behaviour, which I think had probably caught a lot of people out in the past. Oddly, it mentions signed to unsigned conversion as a change even though it's effectively the same as before, and signed to unsigned isn't mentioned in the introduction at all even though that's a major change. The rest are mainly to do with representations e.g. if you're memcopying to or from signed numbers. [1] https://stackoverflow.com/questions/13150449/efficient-unsigned-to-signed-cast-avoiding-implementation-defined-behavior https://stackoverflow.com/questions/13150449/efficient-unsig... [2] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0907r1.html http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p090...

masklinn 6y ago

> Is it just about signed numbers or not? No. You can plug an `UInt8(255)` in an online playground and try to increment it, it’ll crash unless you use an overflowing operator. > Also, what other languages are there that are "like Swift"? In debug mode, Rust will panic on overflow (regardless of signing). You can also enable overflow-checks in release mode.

zeotroph 6y ago
So is Swift effectively adding a jo / jump on overflow instruction after each normal integer operation?
- saeta 6y ago
  `+` is checked for overflow by default (can be overridden with compiler flags), and `&+` is overflowing addition and does auto-vectorize equivalently to C++. I'd be quite interested in seeing a benchmark comparing checked and unchecked addition that doesn't get auto-vectorized to understand the performance in practice for non-numerical computing.
bregma 6y ago
Huh. That would make classic LCG PRNGs pretty useless. I guess it's "safer" in that it prevents rare dangerous edge cases at the expense of common everyday safe operations, but that's a tradeoff.
- twic 6y ago
  For your LCG you would use an explicitly wrapping type: https://doc.rust-lang.org/std/num/struct.Wrapping.html https://doc.rust-lang.org/std/num/struct.Wrapping.html
- OskarS 6y ago
  If you want the wrapping behaviour (like with an LCG), you can prepend the operator with an ampersand(i.e &+ instead of +).
- masklinn 6y ago