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

We Need Hardware Traps for Integer Overflow

blog.regehr.org

Post reply on HN
Print view View original

21–30 of 112 posts

Re: We Need Hardware Traps for Integer Overflow

#21

Post by vonmoltke »

maggit wrote: post #11
sounds wrote: post #9

Modern CPUs don't like traps ("exceptions"). The exception causes a pipeline flush which kills performance for math-intensive code. For example, detecting integer overflow on x86 and x86_64 CPUs is easy: check the overflow flag after every arithmetic operation. It would only be slightly more difficult to detect overflow for SSE (vector) operations, which would require doing some bit masking and shifting. For a langua…

The entire premise of the linked article is that doing it the way you suggest is too expensive for the common case, where no overflow happens. Further, it implicitly asserts that the cost of a hardware trap/exception, while great, will be offset by the savings from the common case. Now, it doesn't back these assertions with much data, but neither do you :)

The problem with a hardware implementation is that you break algorithms and coding systems for which integer overflow, or rather integer wrapping, is a necessary piece rather than an exception case. You could, in theory, add an instruction that disables integer exceptions, but that would make the hardware more complicated. You could also redesign the aforementioned algorithms and systems to not rely on the implicit wrapping, but then you make them more expensive.

Re: We Need Hardware Traps for Integer Overflow

#22

Post by metaphorm »

jjoonathan wrote: post #16
JoshTriplett wrote: post #7

Personally, I'd like to see more programming done in languages that simply don't allow integer overflow in the first place. Most current languages have arbitrary-precision integers; well-implemented arbitrary-precision integers are quite efficient when they fit in a machine word, and as efficient as possible when larger. Sure, you'll lose a bit of performance due to checks for overflow, but those checks need to exist…

Checks are the smallest cost of bignums. Dynamic allocation isn't free, it's terribly expensive. Dereferencing pointers isn't free, it's terribly expensive. It's one thing for a scripting language (where people expect poor, inconsistent performance) to have automatic bignums but it's quite another for a language in which people will be writing performant code to have automatic bignums. They introduce a thousand diffi…

context matters. most arithmetic operations are not performed in hot loops or are not performed on large vectors. I think its better to have a default where correctness and error prevention are gained at the cost of speed. When the speed is needed an explicit choice to use an unsafe but faster performing number type would be the prerogative of the programmer. Its important to have both options available, because context matters.

Re: We Need Hardware Traps for Integer Overflow

#23

Post by brigade »

vonmoltke wrote: post #21
maggit wrote: post #11

Earlier quoted context omitted.

The entire premise of the linked article is that doing it the way you suggest is too expensive for the common case, where no overflow happens. Further, it implicitly asserts that the cost of a hardware trap/exception, while great, will be offset by the savings from the common case. Now, it doesn't back these assertions with much data, but neither do you :)

The problem with a hardware implementation is that you break algorithms and coding systems for which integer overflow, or rather integer wrapping, is a necessary piece rather than an exception case. You could, in theory, add an instruction that disables integer exceptions, but that would make the hardware more complicated. You could also redesign the aforementioned algorithms and systems to not rely on the implicit w…

No one is advocating eliminating modulo arithmetic - the trapping instructions would be different ops, just like on architectures that already implement this such as MIPS.

Re: We Need Hardware Traps for Integer Overflow

#24

Post by mikeash »

jjoonathan wrote: post #16
JoshTriplett wrote: post #7

Personally, I'd like to see more programming done in languages that simply don't allow integer overflow in the first place. Most current languages have arbitrary-precision integers; well-implemented arbitrary-precision integers are quite efficient when they fit in a machine word, and as efficient as possible when larger. Sure, you'll lose a bit of performance due to checks for overflow, but those checks need to exist…

Checks are the smallest cost of bignums. Dynamic allocation isn't free, it's terribly expensive. Dereferencing pointers isn't free, it's terribly expensive. It's one thing for a scripting language (where people expect poor, inconsistent performance) to have automatic bignums but it's quite another for a language in which people will be writing performant code to have automatic bignums. They introduce a thousand diffi…

Isn't the alternative introducing a thousand difficult-to-debug edge cases that cause your code to produce incorrect output, or crash? I'd rather the default setup be "can be slow sometimes". If you're writing performance-sensitive code where you want to control the overflow behavior, make that an option, but not the default.

In the context of Swift, it would make a lot of sense to me for Int to be a bignum with no built-in limits on range. The common case of looping over a small set of values, computing indexes for UI elements, etc. will fall within the range of machine native integers and remain fast. If you blow out the limits, your code will still work. If you want control/speed, use one of the provided integer types with an explicit width.

Re: We Need Hardware Traps for Integer Overflow

#25

Post by TorKlingberg »

angersock wrote: post #12

One of the surprisingly annoying minor things we implemented for some safe code were C routines for "safe arithmetic"--explicitly and carefully catching overflows due to multiplication and addition, for example. This code proved invaluable when writing binary parsers designed to support "unsafe" mesh data coming off of the network--the file might be garbage, but we could at least safely parse it. I'd go so far to say…

Regehr, where this post is from, recently had an article about how to do safe arithmetic in C.

http://blog.regehr.org/archives/1139

As you say, it is surprisingly different to it get right, especially if you want good performance. A common mistake is checking for signed integer overflow after the fact. It is too late when undefined behavior has already happened.

Re: We Need Hardware Traps for Integer Overflow

#26

Post by zvrba »

Or you could have a "sticky" overflow flag, so that you could check for overflow after each complete expression instead of after every single math operation. This needs one new flag and one new conditional instruction. (Plus compiler modifications.)

Re: We Need Hardware Traps for Integer Overflow

#27

Post by zvrba »

angersock wrote: post #12

One of the surprisingly annoying minor things we implemented for some safe code were C routines for "safe arithmetic"--explicitly and carefully catching overflows due to multiplication and addition, for example. This code proved invaluable when writing binary parsers designed to support "unsafe" mesh data coming off of the network--the file might be garbage, but we could at least safely parse it. I'd go so far to say…

> One of the surprisingly annoying minor things we implemented for some safe code were C routines for "safe arithmetic"

I'm surprised that something that necessary and tricky to implement still hasn't been considered for the C standard library.

Re: We Need Hardware Traps for Integer Overflow

#28

Post by vonmoltke »

brigade wrote: post #23
vonmoltke wrote: post #21

Earlier quoted context omitted.

The problem with a hardware implementation is that you break algorithms and coding systems for which integer overflow, or rather integer wrapping, is a necessary piece rather than an exception case. You could, in theory, add an instruction that disables integer exceptions, but that would make the hardware more complicated. You could also redesign the aforementioned algorithms and systems to not rely on the implicit w…

No one is advocating eliminating modulo arithmetic - the trapping instructions would be different ops, just like on architectures that already implement this such as MIPS.

OK, so then its on the compiler to use the non-exception-generating instructions when generating the assembly.

Re: We Need Hardware Traps for Integer Overflow

#29

Post by pbsd »

zvrba wrote: post #26

Or you could have a "sticky" overflow flag, so that you could check for overflow after each complete expression instead of after every single math operation. This needs one new flag and one new conditional instruction. (Plus compiler modifications.)

x86-64 could repurpose the Adjust flag (bit 4 of EFLAGS) for this. It is not longer used, since BCD instructions were deprecated in the x86->x86-64 transition. There is also precedent in the last few years for new instructions that change flag semantics: ADCX and ADOX.
Post reply on HN