News for hackers. Stuff that matters.
Re:How expensive is integer-overflow trapping in C++? by quietbritishjim on Thursday September 24, 2020 @05:07AM (#24576735)
> 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"?

Re:How expensive is integer-overflow trapping in C++? by masklinn on Thursday September 24, 2020 @05:39AM (#24576907)
> 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.

Re:How expensive is integer-overflow trapping in C++? by bregma on Thursday September 24, 2020 @07:01AM (#24577351)
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.
Re:How expensive is integer-overflow trapping in C++? by twic on Thursday September 24, 2020 @07:09AM (#24577390)
For your LCG you would use an explicitly wrapping type: https://doc.rust-lang.org/std/num/struct.Wrapping.html
Re:How expensive is integer-overflow trapping in C++? by OskarS on Thursday September 24, 2020 @07:14AM (#24577429)
If you want the wrapping behaviour (like with an LCG), you can prepend the operator with an ampersand(i.e &+ instead of +).
Re:How expensive is integer-overflow trapping in C++? by masklinn on Thursday September 24, 2020 @11:07AM (#24579300)
As hinted in my comment, Swift provides overflowing operators. You would implement your PRNG using those.
Re:How expensive is integer-overflow trapping in C++? by zeotroph on Thursday September 24, 2020 @05:48AM (#24576955)
So is Swift effectively adding a jo / jump on overflow instruction after each normal integer operation?
Re:How expensive is integer-overflow trapping in C++? by saeta on Thursday September 24, 2020 @10:15AM (#24578795)
`+` 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.

Re:How expensive is integer-overflow trapping in C++? by quietbritishjim on Thursday September 24, 2020 @07:12AM (#24577410)
Thanks for answering about unsigned numbers.

I don't believe Rust is anything like Swift. Do you think that by "like Swift" it just meant "languages where an overflow will result in the program aborting its execution"? If so then that was a pretty useless tautology. (I had assumed it meant something like "like Java" meaning any language that uses the JVM.)

Re:How expensive is integer-overflow trapping in C++? by masklinn on Thursday September 24, 2020 @11:10AM (#24579329)
> I don't believe Rust is anything like Swift. Do you think that by "like Swift" it just meant "languages where an overflow will result in the program aborting its execution"?

That's literally the sole and entire subject of the article, what else would it mean?

> If so then that was a pretty useless tautology.

The wording is odd but it's a useful classification because it's an extremely uncommon behaviour.

> I had assumed it meant something like "like Java" meaning any language that uses the JVM.

That… doesn't make any sense.

Re:How expensive is integer-overflow trapping in C++? by quietbritishjim on Thursday September 24, 2020 @05:33PM (#24583945)
I don't see what your confusion is with my confusion!

Something like "this thing is true about those languages where it's true" would be a totally worthless thing to say: it communicates zero actual information. It doesn't even say there actually is any one language (apart from Swift itself) that satisfies it. Why would the article include an empty statement like that? Even if it's conceivable that it does, surely it's reasonable for me to ask if there's an alternative interpretation that actually had some useful meaning?

> what else would it mean?

It could be that "languages like Swift" refers to a collection of related languages which are pretty obvious if you're familiar with them regardless of this overflow stuff. That is actually the more obvious interpretation to me, because saying that they all share the same overflow behaviour would be meaningful non-trivial information.

I think that's a reasonable thing to think given that "language like X" makes sense for a lot of languages. Maybe Java wasn't the best example, but if someone said "lisp-like" languages or "JavaScript-like languages" you might have an idea what they mean. As I said, I'm not familiar with Swift so for all I know "Swift-like" could make sense too. But it raises the question: what languages would that phrase include? That's why I asked.

Re:How expensive is integer-overflow trapping in C++? by quietbritishjim on Friday September 25, 2020 @04:55AM (#24587933)
After all that mumbo-jumbo I now see your point (not that you're still reading...). I was reading it literally but it was just very badly written. It can be fixed up like this to have the meaning you suggested:

> In some programming languages, like Swift, an overflow will result in the program aborting its execution.

Re:How expensive is integer-overflow trapping in C++? by stabbles on Thursday September 24, 2020 @05:31AM (#24576857)
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)"
Re:How expensive is integer-overflow trapping in C++? by gumby on Thursday September 24, 2020 @07:14AM (#24577428)
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.
Re:How expensive is integer-overflow trapping in C++? by quietbritishjim on Thursday September 24, 2020 @12:59PM (#24580764)
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.

Re:How expensive is integer-overflow trapping in C++? by quietbritishjim on Thursday September 24, 2020 @10:34AM (#24578968)
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-unsig...

[2] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p090...

Re:How expensive is integer-overflow trapping in C++? by amelius on Thursday September 24, 2020 @05:19AM (#24576805)
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.

Re:How expensive is integer-overflow trapping in C++? by pjc50 on Thursday September 24, 2020 @06:00AM (#24577012)
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.

Re:How expensive is integer-overflow trapping in C++? by jandrewrogers on Thursday September 24, 2020 @07:49AM (#24577663)
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.

Re:How expensive is integer-overflow trapping in C++? by amelius on Thursday September 24, 2020 @08:42AM (#24578042)
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.
Re:How expensive is integer-overflow trapping in C++? by heavenlyblue on Thursday September 24, 2020 @09:38AM (#24578487)
> in figuring out how this zoo of exotic integer types interact with each other consistently and correctly

You just allow to copy them from one to another and allow other operations to only be done on the same types of integers.

Re:How expensive is integer-overflow trapping in C++? by loa_in_ on Thursday September 24, 2020 @05:12AM (#24576760)
So overflow means overflow, but underflow as well, while underflow means precision loss. What a bad case of misnomers.
Re:How expensive is integer-overflow trapping in C++? by tom_mellior on Thursday September 24, 2020 @08:23AM (#24577883)
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?
Re:How expensive is integer-overflow trapping in C++? by bregma on Thursday September 24, 2020 @07:15AM (#24577436)
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.