16 ms·
How expensive is integer-overflow trapping in C++?
- ma2rten 6y agoIt seems suspicious to me that clang is so much cheaper than gcc.
- formerly_proven 6y agoadd+jump for clang, jump to dynamically linked function for gcc.
- fluffy87 6y agoNote 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 causes an issue.
- lytigas 6y agoRust wraps in release mode and traps in debug mode[0][1]. All large projects that I know of ship in release mode. Though I'd be interested to see a source for it not pessimizing badly. [0] https://play.rust-lang.org/?version=stable&mode=release&edition=2018&gist=53775b20e6cee7611659aa44e63c2a4b https://play.rust-lang.org/?version=stable&mode=release&edit... [1] https://github.com/rust-lang/rfcs/pull/560 https://github.com/rust-lang/rfcs/pull/560
- sanxiyn 6y agoIt is quite believable that trapping does not slow down Firefox. GCC is part of SPECint, and trapping is known not to slow down SPECint GCC. (It does slow down other SPECint benchmarks.)
- fluffy87 6y agoSee my reply to masklin in this thread for why this is incorrect. In release mode, the behavior of integer overflow in Rust is not UB/cannot happen, but modulo two arithmetic. These two are not the same thing.
- tom_mellior 6y agoHuh? Parent wrote: >> Rust wraps in release mode and traps in debug mode You wrote: > In release mode, the behavior of integer overflow in Rust is not UB/cannot happen, but modulo two arithmetic. The parent didn't claim or imply that overflow is UB. The parent wrote that it "wraps", which is equivalent to your "modulo two arithmetic". You are not in disagreement, so why are you disagreeing?
- djrenren 6y agoI dont think Rust traps on overflow in release builds
- carlmr 6y agoThat's correct, it's not a zero-cost abstraction. Also the wrapping types aren't unsafe, they just make it explicit.
- fluffy87 6y ago. In release mode, the behavior of integer overflow in Rust is modulo two arithmetic instead of not UB/cannot happen. These two are not the same thing. See my reply to masklin.
- masklinn 6y ago> 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.
- fluffy87 6y agoThat’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 compiler AFAIK. If you believe this is incorrect, provide the flag that proves that (hint: such a flag makes safe Rust unsound and it therefore does not exist).
- masklinn 6y ago> 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.
- kevincox 6y agoI 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?
- eddyb 6y ago> 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.
- jojobas 6y agoFrom GCC documentation, >The compiler will attempt to use hardware instructions to implement these built-in functions where possible, like conditional jump on overflow after addition, conditional jump on carry etc. I suspect something's not exactly right with compiler flags. Then again, how much of your program is integer arithmetic? 12x slowdown on 0.1% is 1.2%.
- Deukhoofd 6y agoIt appears GCC doesn't call the builtin overflow functions with that flag on however.
- Gibbon1 6y agoWhat I find annoying is we go back and forth over this because the insistence on clinging to the one true holy int type as on Gods Blessed Machine the PDP 11. Instead of implementing proper variable types like you have with Ada. Seriously considering code can compiled for on 16, 32, and 64 bit machines 'int' is dodgy as hell.
- formerly_proven 6y agoI love typedefs for u8, u16, u32 and their signed brethren, because it's just as short as "int" but way more sane.
- gpderetta 6y agoIIRC -ftrap is basically unmaintained in GCC and you are supposed to use ubsan instead. edit: and it seems that ubsan does generate a simple jo: https://godbolt.org/z/88dE5G Don't use -ftrap I guess.
- asveikau 6y agoAborting 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 affect other clients.
- deleted 6y ago[deleted]
- alblue 6y agoThis is essentially Swift’s problem on the server. If you have a service running and serving hundreds of clients, then any one of those threads can cause a trivial panic if there’s an overflow and take the entire service down. As a result, a number of use cases for swift on the server actually use heavyweight out of process threads (i.e. one process per client) so that the failure of one of them doesn’t take down the rest. Unfortunately there’s no way of overriding the panic (is implemented as an in-line ud2 instruction rather than an overridable function) and while you can install a signal handler to catch it, resuming isn’t straightforward and there are some cases where you really can’t do anything about it (malloc failure). This works great for single user devices where there’s only one app running at once and when it crashes the user restarts it, but doesn’t work in the server case unless you are using a cgi-bin/lambda pattern when each request is processed by a new process each time, which is what TF and the AWS lambda approaches do.
- saagarjha 6y agoI’m curious if one could use a mildly-modified Swift compiler that converts all the different ways to abort execution into some sort of panic handler you can override would help work around this issue.
- wahern 6y agoThis reminds me of Rust unconditionally ignoring SIGPIPE. Except in this case there's a non-trivial amount of pre-existing (and even future) code that assumes a process will be terminated if it attempts to write to a closed pipe. One of Rust's selling points is ease of FFI, so it's largely irrelevant that Rust APIs wouldn't let you ignore write errors. Rust breaks the environment for libraries that rely on the behavior.
- nly 6y agoI 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 https://gcc.godbolt.org/z/zj6qbn By contrast, Clang is not: https://gcc.godbolt.org/z/r7avno https://gcc.godbolt.org/z/r7avno Btw if you only need overflow checking in a few places, you can use overflow detecting intrinsics: https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins... In C++, this is going to be way more useful than -ftrapv anyway, since in a lot of situations you're dealing with user input and you're probably going to want to throw, not abort. https://gcc.godbolt.org/z/5qvTf9 https://gcc.godbolt.org/z/5qvTf9
- haberman 6y agoFrom 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.
- colanderman 6y agoIndeed. -ftrapv is no longer the best choice for overflow trapping in GCC anyway; in my experience it's pretty inconsistent handling e.g. compile-time overflows. -fsanitize=signed-integer-overflow (part of UBSAN) produces more efficient code, provides better coverage, and is more flexible. By default it provides a diagnostic message; you can instead simply abort with -fno-sanitize-recover, or execute an undefined instruction with -fsanitize-undefined-trap-on-error (equivalent to Clang's -ftrapv). Regardless of choice, addition is performed inline. See: https://gcc.godbolt.org/z/aGo6WW https://gcc.godbolt.org/z/aGo6WW
- ot 6y agoThis blog post has a much more in-depth analysis of the cost of overflow checking: https://blog.regehr.org/archives/1384 https://blog.regehr.org/archives/1384 The tl;dr is that (on x86-64) the additional branch to trap has almost negligible cost (processor already sets the flag on overflow, jump is always predicted), but it completely breaks vectorization and loop optimizations, which significantly impacts certain benchmarks.
- wahern 6y agoBut see "Sentinels can be faster", https://lemire.me/blog/2020/09/03/sentinels-can-be-faster/ https://lemire.me/blog/2020/09/03/sentinels-can-be-faster/. HN discussion: https://news.ycombinator.com/item?id=24402763 https://news.ycombinator.com/item?id=24402763. I once worked on a project that compiled Perl-compatible regular expressions to C code using Ragel + custom modifications that could switch to NFA machines for subexpressions as required. The generated NFA machines required simple stack operations (push and pop of NFA state) on a preallocated array. Originally the PoC attempted no bounds checking, and so could theoretically overflow the array, possibly (likely) corrupting the heap. When I added bounds checking to each generated push operation (a simple test + goto), throughput plummeted by something very significant--two- or three-digit, not single-digit percentages. So I allocated the array with mmap and a guard page. And rather than pick a magic number and call it a day, on SIGSEGV (or SIGBUS?) I would longjmp back to a point where I could grow the array and restart match execution from the beginning. Performance returned to where it was originally. Fortunately, nothing in the code that might trigger SIGSEV could leave behind inconsistent state or orphaned resources that might need to be collected. The longjmp from the signal handler was perfectly safe and obeyed all relevant constraints; it didn't implicate undefined behavior. Unfortunately, neither POSIX nor Linux (nor any Unix, AFAIK) supports per-thread signal handlers, only a global handler per signal. And you can't safely access thread-local storage from a signal handler, anyhow.[1] To distinguish an expected SIGSEGV from an unexpected SIGSEGV, and to support multiple threads, I used sigaltstack. The SIGSEGV handler would query the alt stack. If there was no alt stack, it aborted. If there was an alt stack, it would derive a per-thread data structure stored in a page beyond the top of the stack with an intervening guard page of its own. (sigaltstack is per-thread.) The guard page stored the jmp_buf structure needed for the longjmp, and the array boundaries needed to distinguish NFA state overflow from a real bug. The siginfo_t reference passed to the signal handler provided the fault address. This was an interesting little subproject because it showed just how performant hardware-based exceptions could be (I never did much kernel or assembly programming), as well as how detrimental conditional branching could be to performance. And it was almost certainly the only time I'll have a truly legitimate reason to catch SIGSEGV, as opposed to previous cases I've seen in some other projects that had the horrible idea of attempting to recover from a truly invalid and uncontrolled memory access. [1] POSIX doesn't permit it, though in practice it depends on the libc. musl supports it because it preallocates all TLS when creating a thread, but it's unsafe on glibc as glibc lazily allocates TLS. We were using glibc, and while theoretically I could have induced TLS slot initialization, thread-safe reentrancy of internal machinery was an area where glibc actually had (and has, last time I checked) quite a few open bugs, so I wasn't about to play games there.
- noselasd 6y agoSo on my machine it's 0.72 ns/int (+/- 2.5 %) vs 0.90 ns/int (+/- 2.5 %) for normal cases when no overflow/traps actually occurs. When an overflow/trap occurs, a possible severe bug, it's 0.74 ns/int (+/- 2.5 %) vs 9.12 ns/int (+/- 2.1 %)
- BeeOnRope 6y agoHow did you measure the speed of the trapping scenario, since the program terminates in that case?
- andi999 6y agoI read the sourcecode and it seems the array is 1000 elements (with random elements). If each sum supposedly need 0,1ns then the whole process is around 100ns=0,1 ms. I do not think you can do benchmark on these timescales. Then the algo is repeated on the same data 40 times and averaged. This also doesnt help too much. So the first run puts everything in L1 cache and then it runs much faster. Anyway usually anything below 10ms is random, and one should go ar least for 1s (or even more).
- _hl_ 6y ago> each sum supposedly need 0,1ns Sub-cycle latency for an addition would be quite amazing... Nevertheless your point remains. > 100ns=0,1 ms 0.1μs, not 0.1ms
- andi999 6y agoOf course! Even worse. I need my coffee (and stop yelling at the students when they mess this up)
- titzer 6y agoModern superscalar processors have more than one execution unit. The latest Intel microarchitecture has 10 execution ports, which means it can theoretically execute 10 μ-ops per cycle. With a 200+ entry reorder buffer, the processor is trying hard to cram those execution units full every cycle. How successful it is depends on dynamic data dependencies and fetch/issue bandwidth. At 3ghz, to reach 0.1ns latency (on average), it only needs to achieve 3 instructions per clock.
- bleepblorp 6y agoIt'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. Another extremely useful instruction deleted from x86-64 tested if an array access was in bounds. Determining how many buffer overflow exploits could have been prevented if this instruction was widely used--and carried over to x64--is left as an exercise for the reader.
- chrisseaton 6y agoI wasn’t aware of this - which instruction do you mean?
- wmil 6y agoThere's an integer overflow flag that gets set after operations. My x86 books are all boxed up somewhere so I can't look up the details.
- gsg 6y agoThat still exists though? add rax, rbx/jo overflow_error is how you do overflow checking on x86-64.
- chrisseaton 6y agoThat doesn’t work with a lot of arithmetic, so you have to use slower arithmetic in order to use it.
- gsg 6y agoSure, but that didn't change much between x86 and x86-64. Perhaps it got a little worse because the SIMD instructions aren't overflow check friendly.
- xxs 6y agoWriting (compiler) microbenchmarks is notoriously hard. Overall no benchmark should run fewer than two mins or so to account for context switching noises at least. It should run on fixed CPU frequency (no turbo boost, etc), fixed CPU core(s) too. It should be aware of L1/L2 cache sizes - data crossing L1/L2 boundaries on different processors results in disproportional results. The difference in compilers is too high and the author should just disassembly of the generated code. Imo, a bad article.
- rocqua 6y agoAt what performance differential are those factors relevant? For a 5% difference I would share your sceptisism. However, the effect size is a 4x difference (3x slowdown vs 12x slowdown). To me, it seems very unlikely to be a result of inconsistent benchmarking. However, I am not an expert on the subject.
- mhh__ 6y agoI think unless you own the entire machine almost all microarchitecture level benchmarking is playing with fire because of all the things you've mentioned. Even if you use perf_event to get as low as the OS allows you to account for things that'll slow you down there's still overhead associated with that AFAIK Also, code disassembly is a fairly awful way of assessing performance unless you mean for the purposes of the article
- xxs 6y agoArticle in this case, hence the new paragraph. I used to routinely do for Java... with -XX:+PrintAssembly to ensure certain bound checks were eliminated by enforcing the index fell within the lattice [0-array.length). A simple test that always succeeded improved zip compression by 15% for instance. Not going in details but verifying results of microbenchmarks with assembly is quite useful - of course usually limited to very hot spots. Of course about owning the hardware and doing on bare metal with fixed freq (core/uncore) + set voltage(s). Removing as many variables as possible is important just as knowing what to test and how it gets affected by the hardware.
- olliej 6y agoThe problem with integer overflow, in the general context of UB, isn't that it's expensive to trap. The problem is that the C (and C++) specs insist on overflow being undefined behavior. Then compilers insist on abusing the UB as meaning that they get to do whatever they want. This particular case is only partially the compiler's fault, as the various specs should not be defining well specified behavior as being undefined. Fully in the compiler's fault is the treatment of UB meaning "now I can do whatever I want", which turns the compiler into a security adversary. I have yet to see a non-microbenchmark, non-spec benchmark, that demonstrates a real world win by subverting the developer's intent.
- formerly_proven 6y agoInteger overflow should have been implementation-defined behavior from day one, because that's what it actually is.
- saagarjha 6y agoImplementation defined means that the behavior is defined. This is patently not what the existing behavior of compilers in the face of integer overflow is.
- formerly_proven 6y agoI'm trying to say that integer overflow is architecture-specific, so it _should_ have been standardized as implementation defined.
- rocqua 6y agoYou probably know this, but by making it UB, compilers don't need to have the same behavior on every case of integer overflow. This allows compilers to apply much more optimizations.
- ChrisLomont 6y agoEvery implementation (compiler and arch combo) defines behavior as far as I know, and I’ve tested dozens of combos. What combo does not have implementation defined behavior for C/C++ signed overflow? Are there any?
- himinlomax 6y agoSo what's the correct way to tell the C++ compiler you want integer overflow to occur in a particular spot when overflow trapping is enabled?
- rocqua 6y agoUse `unsigned int` instead of `int` Overflow for signed types is undefined behavior. Hence the compiler can trap when it happens and remain standards compliant. For unsigned types, overflow is defined behavior, and hence -ftrap will not trigger on overflow. An interesting flip side of this is that using signed types can be a lot faster because the compiler is allowed to assume that overflow will not happen, which lets it apply more optimizations.
- bregma 6y agoSince most compiler vendors provide an implementation-specific way to define the undefined behaviour of signed integer overflow as a vendor extension, you will need to resort to compiler-specific means to control that. For example, in GCC you could use a `#pragma push_options("-fno-trapv")/#pragma GCC pop_options` pair to surround the offending code.
- quietbritishjim 6y ago> 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 agoSo overflow means overflow, but underflow as well, while underflow means precision loss. What a bad case of misnomers.
- bregma 6y agoTo 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.
- bregma 6y agoThe big thing that isn't talked about is the fact that the problem with forcing a vendor-specific definition on the undefined behaviour of signed integer overflow is that significant optimization opportunities are lost. The danger of signed integer overflow in C++ is not that your less-than-zero comparison is not working in a reverse for-loop (although, to be fair, that's a danger encountered by newbies). The big problem is that the compiler will optimize away huge chunks of code when it detects a possible signed integer overflow resulting in weird and unexpected behaviour at runtime. It's not really an exploitable security issue so much as a massive cost issue from stretched out development time or increased support costs (depending on how well your code gets tested before release).