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

151–160 of 198 posts

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

#151

Post by R0b0t1 »

MaxBarraclough wrote: post #55
asveikau wrote: post #8

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? I guess languages with support for exceptions have a more natural action for this, that could be caught somewhere in a server's processing loop to not affe…

> Aborting the program on integer overflow seems so drastic. Disagree. Overflowing of a signed integer type is undefined behaviour, which deserves to be taken seriously. I was surprised to see that the article doesn't mention the signed/unsigned distinction, or undefined behaviour. Overflowing of a unsigned integer type is not a problem, it's defined to wrap around, and may be done intentionally.

Are you sure? IIRC overflow or underflow is always UB per the (earlier?) C standards; they did not expect a single popular representation system for numbers.

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

#152

Post by Someone »

BeeOnRope wrote: post #125
bleepblorp wrote: post #15

It's worth mentioning that x86 CPUs had a single instruction overflow test that would raise a hardware interrupt in response to an integer overflow. This allowed for extremely low cost integer overflow tests. Unfortunately, this capability was deleted from x86-64 and we're now stuck with either accepting the risks of integer overflows or suffering a performance hit to test for them by using multiple instructions. Ano…

It's still a single instruction in the hot path: jo. All such overflow jumps could go to the same handler, in which case it really would just be one instruction overall, but you'd lose the ability to report the exact location of the overflow. A small per-overflow thunk would solve that (it could be as small as a single call instruction). Currently the jo doesn't macro-fuse with the addition on Intel chip, but maybe t…

I don’t know x86, but, after googling, I would guess that trapping instruction was INTO.

Reading https://xem.github.io/minix86/manual/intel-x86-and-64-manual..., that would give the handler enough information to figure out where the overflow happened. Of course, that would be at the cost of some performance (setting those registers takes time)

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

#153

Post by scoutt »

jjnoakes wrote: post #143
scoutt wrote: post #140

Earlier quoted context omitted.

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

Sure but in 17 years writing C for a living, with lines of code by the millions, and (embedded) devices running my code all over the world I still have to know about an integer overflow bug.

Sure, I don't always write bug-free code (as anyone), but when I say it's not so terrible I mean that UD should be considered a rare case, and it's not worth even a single night of quiet sleep, let alone switching languages or overreacting. Hey, I am more afraid of a flipping bit due to power supply noises.

And I don't want to say either that my code is perfect, or since it never happened to me it will never happen to you and that you can go around triggering UD everywhere since it's not a big deal. But I also like to warn young players that "boooo UD!" is just part of a FUD tactic for them to adopt some shiny new language.

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

#154

Post by MaxBarraclough »

R0b0t1 wrote: post #151
MaxBarraclough wrote: post #55

Earlier quoted context omitted.

> Aborting the program on integer overflow seems so drastic. Disagree. Overflowing of a signed integer type is undefined behaviour, which deserves to be taken seriously. I was surprised to see that the article doesn't mention the signed/unsigned distinction, or undefined behaviour. Overflowing of a unsigned integer type is not a problem, it's defined to wrap around, and may be done intentionally.

Are you sure? IIRC overflow or underflow is always UB per the (earlier?) C standards; they did not expect a single popular representation system for numbers.

Yes, I'm quite sure. C mandates that unsigned integer types use the typical binary representation, and it mandates wrapping arithmetic. I don't know much about the early C standards, it's possible it wasn't always this way.

https://wiki.sei.cmu.edu/confluence/pages/viewpage.action?pa...

https://stackoverflow.com/a/18195756/

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

#155

Post by pjmlp »

gsg wrote: post #83
bleepblorp wrote: post #37

Earlier quoted context omitted.

I was thinking of BOUND[0] rather than MPX. It's a much lighter solution than MPX and didn't require OS support. [0] https://hjlebbink.github.io/x86doc/html/BOUND.html

BOUND is pretty slow, and requires an odd start/end pair to be placed in memory. I don't see any reason that it would be better than the usual unsigned comparison + branch that languages with bounds checking tend to use. Besides, much of the difficulty with memory safety in C and C++ is the existence of pointers (or wrappers around them, like iterators), which do not come with an associated length. Length checking ma…

Modern approaches take advantage of 64bit addressing modes to handle tagged pointers.

The irony that we need a Lisp Machines solution to fix C and its derived languages.

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

#156

Post by pjmlp »

scoutt wrote: post #153
jjnoakes wrote: post #143

Earlier quoted context omitted.

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

Sure but in 17 years writing C for a living, with lines of code by the millions, and (embedded) devices running my code all over the world I still have to know about an integer overflow bug. Sure, I don't always write bug-free code (as anyone), but when I say it's not so terrible I mean that UD should be considered a rare case, and it's not worth even a single night of quiet sleep, let alone switching languages or ov…

Would you feel the same way when we finally manage to get liability laws for security exploits, like we are now discussing in Germany?

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

#157

Post by gumby »

haberman wrote: post #13
nly wrote: post #9

I wish the author had dug a little deeper to see why this slowdown occurs. GCC seems to be generating an out-of-line function call to implement the trapped addition, which is going to inhibit a lot of other optimizations like vectorization: https://gcc.godbolt.org/z/zj6qbn By contrast, Clang is not: https://gcc.godbolt.org/z/r7avno Btw if you only need overflow checking in a few places, you can use overflow detecting…

From the article: > Looking at the assembly, I find that the clang compiler generates sensible code on x64 processor, with simple jumps added when the overflow is detected. Meanwhile, GCC seems to call poorly optimized runtime library functions.

...because he didn’t pass the correct options to gcc. Look at a comment parallel to yours for details.

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

#158

Post by fbkr »

scoutt wrote: post #126
MaxBarraclough wrote: post #55

Earlier quoted context omitted.

> Aborting the program on integer overflow seems so drastic. Disagree. Overflowing of a signed integer type is undefined behaviour, which deserves to be taken seriously. I was surprised to see that the article doesn't mention the signed/unsigned distinction, or undefined behaviour. Overflowing of a unsigned integer type is not a problem, it's defined to wrap around, and may be done intentionally.

I guess people overreact to "undefined behavior". If your software runs always on the same platform then you can know what the behavior would be. It might also be intentional and should not crash your program. Undefined behavior is used when doing a specification for a compiler that will be used in many architectures and they cannot clearly specify what would happen on ALL architectures for a given operation, because…

This is not correct, what you are thinking is implementation defined or maybe unspecified behavior.

Please do explain the behavior of calling an uninitialized function pointer on x86 if you insist.

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

#159

Post by quietbritishjim »

gumby wrote: post #106
stabbles wrote: post #76

Earlier quoted context omitted.

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

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.

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

#160

Post by BeeOnRope »

Someone wrote: post #152
BeeOnRope wrote: post #125

Earlier quoted context omitted.

It's still a single instruction in the hot path: jo. All such overflow jumps could go to the same handler, in which case it really would just be one instruction overall, but you'd lose the ability to report the exact location of the overflow. A small per-overflow thunk would solve that (it could be as small as a single call instruction). Currently the jo doesn't macro-fuse with the addition on Intel chip, but maybe t…

I don’t know x86, but, after googling, I would guess that trapping instruction was INTO. Reading https://xem.github.io/minix86/manual/intel-x86-and-64-manual... , that would give the handler enough information to figure out where the overflow happened. Of course, that would be at the cost of some performance (setting those registers takes time)

Yes, one advantage of INTO over JO is that the interrupt mechanism insures that you know where you came from, so you can build location reporting on top of that.

However, I would consider that advantage fairly small, and it's not easy to implement either in a modular way since the way interrupts or signals are handled is a shared global thing, so you have to have process-wide agreement on how this overflow trapping is going to work (or at least an agreement on how to disagree). In a shared runtime language where everything plays by the same rules, but in low level native langues like C, C++ and Rust it is more difficult.

A jump based approach has the advantage that is is standalone and really doesn't seem much more expensive than INTO. The single jump instruction, and a bit more cold, out of line, code if you want accurate location reporting.

If/when AMD and Intel start fusing JO with the preceding arithmetic operation, it will be have a non-trivial perf advantage over INTO.

Post reply on HN