Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How expensive is integer-overflow trapping in C++?

lemire.me

Post reply on HN
Print view View original

141–150 of 198 posts

Re: How expensive is integer-overflow trapping in C++?

#141

Post by brohee »

ordu wrote: post #130
brohee wrote: post #115

Earlier quoted context omitted.

It's also IMHO a failure of RISC-V. "We did not include special instruction set support for overflow checks on integer arithmetic operations in the base instruction set, as many overflow checks can be cheaply implemented using RISC-V branches" Cheaply is not freely.

I prefer branching. Interrupt is inconvenient especially if you mean not panic and die but do some recovery. Conditional jump after arithmetic operation could be as cheap as one instruction, branch prediction could make this instruction to cost almost nothing in terms of execution times (at least if overflows are a rare thing), and you could point this branch anywhere you like, so you could process overflow and try t…

Your comment actually swayed my opinion. If you are to do anything useful after the overflow, you'll need branching...

Re: How expensive is integer-overflow trapping in C++?

#142

Post by quietbritishjim »

stabbles wrote: post #76
quietbritishjim wrote: post #59

> 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 def…

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)"

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++?

#143

Post by jjnoakes »

scoutt wrote: post #140
jjnoakes wrote: post #135

Earlier quoted context omitted.

> If your software runs always on the same platform then you can know what the behavior would be. This is not necessarily true, and I consider it to be a harmful misconception. I think people under-react to "undefined behavior". What you think the platform would do if you overflowed an integer using machine instructions and what your C or C++ code ends up executing can be wildly different things because C and C++ com…

You are right. I might correct the sentence with "you can often know". Undefined behavior should be avoided but really is not that terrible.

We will have to agree to disagree.

Fully understanding what a program might do if there is undefined behavior is not trivial. It requires basically reviewing and fully understanding the output assembler for every single build.

Any change in system headers, compiler version, compiler flags, or source code might invalidate previous reviews.

And programs with lurking undefined behavior may not seem dangerous but sufficiently clever exploits can do quite amazing things with the smallest of attack surfaces.

Re: How expensive is integer-overflow trapping in C++?

#144

Post by kevincox »

fluffy87 wrote: post #2

Note that Rust also traps on integer overflow, and it is trivial to „hack“ the compiler to disable this, and many have done so. While on this microbenchmark you see a 3x slowdown with the LLVM backend, on large Rust projects like servo, Firefox, the rust compiler, etc. the slowdown is not even measurable. Also, Rust provides you with unsafe intrinsics to opt-out of trapping in the particular line of code in which it…

I find this decision frustrating. They made it clear by making it trap in debug that this is a "bug" but denied the optimization benefits of calling it undefined behaviour on release.

I'm assuming the rationalization is "wrapping is better than undefined behaviour" but I have not seen any evidence that the average program is actually more likely to behave correctly in the face of wrapping.

The combinations that make the most sense to me are:

1. debug: trap, release: trap. Bad performance, correct.

2. debug: wrap, release: wrap. Good performance

3. debug: trap, release: undefined. Great performance.

I guess my point is make up your mind. Is "overflow" allowed and wrapping or a bug?

Re: How expensive is integer-overflow trapping in C++?

#145

Post by masklinn »

fluffy87 wrote: post #101
masklinn wrote: post #81

Earlier quoted context omitted.

> Note that Rust also traps on integer overflow, and it is trivial to „hack“ the compiler to disable this, and many have done so. “Hack” is a completely unsuitable term, there’s a simple and official compilation flag which can be flipped on or off. It’s also misleading to say that Rust will trap on overflow: rustc enables overflow checking by default in debug mode, but disables it in release.

That’s unfortunately incorrect. That flag does not turn integer overflow into UB, which is what allows the C++ optimizations that assume it cannot happen, and can be used to prove that loops terminate, etc. That flag changes the behavior of integer overflow from trapping to “modulo 2 arithmetic”. If you want to change the behavior of integer overflow in Rust to “always assume it cannot happen”, you need to “hack” the…

> That’s unfortunately incorrect. That flag does not turn integer overflow into UB

I've never claimed any such thing. Integer overflow is defined in Rust.

> That flag changes the behavior of integer overflow from trapping to “modulo 2 arithmetic”.

Yes?

> If you want to change the behavior of integer overflow in Rust to “always assume it cannot happen”, you need to “hack” the compiler AFAIK.

What I quoted was about rust "trapping" on integer overflow and having to "hack" it in order to make it not trap.

Re: How expensive is integer-overflow trapping in C++?

#146

Post by masklinn »

bregma wrote: post #99
masklinn wrote: post #78

Earlier quoted context omitted.

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

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.

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++?

#147

Post by masklinn »

quietbritishjim wrote: post #104
masklinn wrote: post #78

Earlier quoted context omitted.

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

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

> 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++?

#148

Post by eddyb »

kevincox wrote: post #144
fluffy87 wrote: post #2

Note that Rust also traps on integer overflow, and it is trivial to „hack“ the compiler to disable this, and many have done so. While on this microbenchmark you see a 3x slowdown with the LLVM backend, on large Rust projects like servo, Firefox, the rust compiler, etc. the slowdown is not even measurable. Also, Rust provides you with unsafe intrinsics to opt-out of trapping in the particular line of code in which it…

I find this decision frustrating. They made it clear by making it trap in debug that this is a "bug" but denied the optimization benefits of calling it undefined behaviour on release. I'm assuming the rationalization is "wrapping is better than undefined behaviour" but I have not seen any evidence that the average program is actually more likely to behave correctly in the face of wrapping. The combinations that make…

> but I have not seen any evidence that the average program is actually more likely to behave correctly in the face of wrapping.

Rust takes a simple stance of "safe code should be UB-free".

Yes, you may have logic bugs with wrapping, but you can't cause memory unsafety with it in, because things like array/slice bound checks aren't ever disabled.

Also, C relies on undefined signed overflow for things like "`for` loops incorrectly using `int` instead of `size_t` because it's easier to type", which doesn't really apply to Rust (which require `usize`, the `size_t` equivalent, for indexing, and has pointer-range-based iterators for slices), so I doubt UB overflow in Rust would help performance much.

It would be trivial to change `rustc_codegen_llvm` to set LLVM's `nsw`/`nuw` (in order to make signed/unsigned overflow UB), if you want to prove it improves performance somewhere.

Re: How expensive is integer-overflow trapping in C++?

#149

Post by asveikau »

higerordermap wrote: post #97
lmm wrote: post #62

Earlier quoted context omitted.

> Aborting the program on integer overflow seems so drastic. Say you do that in a server program. Then convincing it to overflow an integer somewhere (possibly somewhere where it is harmless) causes denial of service and all unrelated connections in the process die? If you don't abort then you probably have an arbitrary code execution vulnerability. Overflow is undefined behaviour in C++, your code is in an unanticip…

He is saying it should raise an exception which can be caught somewhere up the stack.

Yes, but I would take minor issue in that I wasn't saying what should happen so much as what the options are given various tradeoffs.

There are programming communities that have criticisms of exceptions and would like to avoid them. I am sympathetic to that. But if you do have exceptions, this is a good candidate. If you don't have exceptions, making integer overflow trap seems problematic. Posix signals may be another solution, with its own problems and ugliness.

Re: How expensive is integer-overflow trapping in C++?

#150

Post by R0b0t1 »

brohee wrote: post #141
ordu wrote: post #130

Earlier quoted context omitted.

I prefer branching. Interrupt is inconvenient especially if you mean not panic and die but do some recovery. Conditional jump after arithmetic operation could be as cheap as one instruction, branch prediction could make this instruction to cost almost nothing in terms of execution times (at least if overflows are a rare thing), and you could point this branch anywhere you like, so you could process overflow and try t…

Your comment actually swayed my opinion. If you are to do anything useful after the overflow, you'll need branching...

No, sometimes overflow is so rare the trap saves you time in the majority case. Also sometimes panicking on hardware trap is the useful thing.

If we had more ALU variety these discussions wouldn't pop up. Saturating arithmetic, bounded arithmetic, etc are all useful and safer by default in most cases.

Post reply on HN