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

121–130 of 198 posts

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

#121

Post by gpderetta »

zeotroph wrote: post #119
tom_mellior wrote: post #114

Earlier quoted context omitted.

That wouldn't work well for C since signed overflow is undefined, but unsigned overflow is well-defined, with wrapping semantics. Making all existing arithmetic instructions trapping would mean paying trapping costs for well-defined unsigned overflow.

I think this would be a per-thread state which you toggle, defaulting to "off". Then instead of checking and branching after each operation you flip it on/off depending on the type of arithmetic you want. The trick would be to get to the minimal number of toggles and not do the "safe" thing and set it to on/off for each operation.

Generally this sort of global states are considered a misfeature. They are hard to use and impede cpu design (they are particularly bad for OoO). It is better to have per instruction flags.

For exemple while SSE still has an fpu control word, explicit instructions were added for some stuff that historically was handled by the control register (rounding for example).

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

#122

Post by amelius »

jandrewrogers wrote: post #113
pjc50 wrote: post #91

Earlier quoted context omitted.

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

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…

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

#123

Post by secondcoming »

saagarjha wrote: post #43
formerly_proven wrote: post #32

Earlier quoted context omitted.

Integer overflow should have been implementation-defined behavior from day one, because that's what it actually is.

Implementation defined means that the behavior is defined. This is patently not what the existing behavior of compilers in the face of integer overflow is.

It means that the behaviour is defined for a particular compiler and architecture target.

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

#124

Post by account42 »

andi999 wrote: post #12

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

> Anyway usually anything below 10ms is random.

I don't think you realize how much time 10ms is for a computer. Games need to render an entire frame in under 7 ms to hit my monitor's max refresh rate.

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

#125

Post by BeeOnRope »

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 that will change in the future.

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

#126

Post by scoutt »

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.

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 the result might change among these architectures.

Undefined behavior doesn't mean that your CPU has either a chance to suddenly blow away or that it would gain self-awareness and destroy the world.

You can actually predict what would happen if you throw away a rock on earth. You cannot predict it for every planet in the universe, so theoretically "throwing a rock" produces undefined behavior.

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

#127

Post by BeeOnRope »

chrisseaton wrote: post #38
bleepblorp wrote: post #34

Earlier quoted context omitted.

INTO. It signals int 0x04 if the instruction is executed while the overflow flag is set due to a prior signed arithmetic operation wrapping. It seems I misspoke somewhat; there is somewhat equivalent functionality in x64 in the JO instructions, but they're six bytes rather than one and the extra size could have cache and/or memory bandwidth impacts under demanding circumstances.

Yeah I knew about jo, and I think add-jo is even fused, but without a trap you have to write code everywhere to handle the overflow which you wouldn’t need if you had a trap. And of course jo doesn’t work for address arithmetic. That’s where the real overhead is.

Unfortunately jo is not fused on Intel chips, which is a bit surprising.

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

#128

Post by heavenlyblue »

jandrewrogers wrote: post #113
pjc50 wrote: post #91

Earlier quoted context omitted.

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

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…

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

#129

Post by colanderman »

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…

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

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

#130

Post by ordu »

brohee wrote: post #115
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 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 to recover from error without going outside of a current stack frame.

It could be ugly in a high-level languages though. Instead of (a+b)*c you might get something like

    a.checked_add(b)
     .map(|x| x.checked_mul(c))
     .flatten()
     .unwrap_or_else(|| do_something_to_recover(a, b, c));
At the same time there is nothing to forbid a syntax like:

   ((a⊕b)⊙c).flatten().unwrap_or_else(|| do_something to recover(a, b, c));
Just people do not like to use unicode in programming languages.
Post reply on HN