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

Integer Overflow Checking Cost

danluu.com

Post reply on HN
Print view View original

11–17 of 17 posts

Re: Integer Overflow Checking Cost

#11

Post by ozgrakkurt »

mayoff wrote: post #6

In Swift (Apple’s C++ successor), the normal operators (`+`, `-`, `*`) trap on overflow for integer types. If you want twos complement wrapping, you can use `&+`, `&-`, and `&*`. Given that Apple has been making its own CPU cores for years now, I suspect overflowing checking on Apple CPUs is virtually free (aside from code size).

This approach isn’t good imo.

Zig also has a similar approach.

It is best to have ergonomic checked version of arithmetic functions and always use them when possible, and use the debug only checked versions on other places.

Performance of checked arithmetic will basically never matter around things like allocation in my experience

Re: Integer Overflow Checking Cost

#12

Post by debugnik »

qayxc wrote: post #8
mayoff wrote: post #6

In Swift (Apple’s C++ successor), the normal operators (`+`, `-`, `*`) trap on overflow for integer types. If you want twos complement wrapping, you can use `&+`, `&-`, and `&*`. Given that Apple has been making its own CPU cores for years now, I suspect overflowing checking on Apple CPUs is virtually free (aside from code size).

> Given that Apple has been making its own CPU cores for years now, I suspect overflowing checking on Apple CPUs is virtually free (aside from code size). Never make guesses based on a particular programming language. In Apple's own C documentation ( https://developer.apple.com/documentation/xcode/integer-over... ) it is stated that "Overflows result in undefined behavior." and enabling wrapping behaviour "may advers…

"Enabling wrapping behaviour" for signed integers disallows a lot of optimizations based on signed overflow being undefined behaviour, which is a matter of language and compiler design. This says nothing about the cost of checked arithmetic itself on the CPU.

Re: Integer Overflow Checking Cost

#13

Post by qayxc »

debugnik wrote: post #12
qayxc wrote: post #8

Earlier quoted context omitted.

> Given that Apple has been making its own CPU cores for years now, I suspect overflowing checking on Apple CPUs is virtually free (aside from code size). Never make guesses based on a particular programming language. In Apple's own C documentation ( https://developer.apple.com/documentation/xcode/integer-over... ) it is stated that "Overflows result in undefined behavior." and enabling wrapping behaviour "may advers…

"Enabling wrapping behaviour" for signed integers disallows a lot of optimizations based on signed overflow being undefined behaviour, which is a matter of language and compiler design. This says nothing about the cost of checked arithmetic itself on the CPU.

It does, though. UB and associated optimisations wouldn't be an issue if defined behaviour would not have an impact on performance. If the cost would be zero or negligible, the compiler wouldn't need to care and hence warnings like this wouldn't need to be explicitly stated.

Re: Integer Overflow Checking Cost

#14

Post by msichert »

Someone wrote: post #10
saagarjha wrote: post #9

Earlier quoted context omitted.

Code size (and branch table entries) are not free, of course. The other thing to note is that trapping operators often need to trap precisely which can lead to missed optimizations.

One example of such an optimization is that overflow checking can prevent vectorization of code. See for example this post: https://lemire.me/blog/2016/12/06/dont-assume-that-safety-co... . It is ancient, but I don’t see a reason why it would have become outdated.

Vector instructions usually don't have overflow flags, so a compiler can't easily vectorize loops containing overflow checks. However, detecting overflows in integer operations requires only a bit of bitwise arithmetic. In my experiments, this lead to an overhead of only 7% for vectorized additions with overflow checks: https://cedardb.com/blog/vectorized_overflows/

Re: Integer Overflow Checking Cost

#15

Post by ack_complete »

msichert wrote: post #14
Someone wrote: post #10

Earlier quoted context omitted.

One example of such an optimization is that overflow checking can prevent vectorization of code. See for example this post: https://lemire.me/blog/2016/12/06/dont-assume-that-safety-co... . It is ancient, but I don’t see a reason why it would have become outdated.

Vector instructions usually don't have overflow flags, so a compiler can't easily vectorize loops containing overflow checks. However, detecting overflows in integer operations requires only a bit of bitwise arithmetic. In my experiments, this lead to an overhead of only 7% for vectorized additions with overflow checks: https://cedardb.com/blog/vectorized_overflows/

That's with a simple data operation and using a recent x86 vector ISA (AVX-512) that is only available on some systems, notably excluding any current Intel desktop CPU.

The real killer isn't the data operations, though, it's if the overflow checks interfere with converting the loop logic or data addressing to vectorizable form. Indexing with 32-bit signed int vs. unsigned int on a 64-bit platform in C is a classic case -- with unsigned the compiler cannot assume that addressing offsets don't wrap, which then prevents coalescing data accesses into vector loads and stores.

Re: Integer Overflow Checking Cost

#16

Post by debugnik »

qayxc wrote: post #13
debugnik wrote: post #12

Earlier quoted context omitted.

"Enabling wrapping behaviour" for signed integers disallows a lot of optimizations based on signed overflow being undefined behaviour, which is a matter of language and compiler design. This says nothing about the cost of checked arithmetic itself on the CPU.

It does, though. UB and associated optimisations wouldn't be an issue if defined behaviour would not have an impact on performance. If the cost would be zero or negligible, the compiler wouldn't need to care and hence warnings like this wouldn't need to be explicitly stated.

And yet Swift doesn't rely on these optimizations, preferring to trap instead. Again, the guess above was about the CPU and we're conflating language-specific UB optimisations.
Post reply on HN