We Need Hardware Traps for Integer Overflow • Hacker News Board

Re: We Need Hardware Traps for Integer Overflow

#11

Post by maggit » Wed, Jun 04, 2014, 7:22 PM UTC

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

Re: We Need Hardware Traps for Integer Overflow

#12

Post by angersock » Wed, Jun 04, 2014, 7:28 PM UTC

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 that if you are dealing with a binary format--especially a sane one which has length headers and chunks for rapid seeking--and you aren't using something similar, you are doing it wrong.

EDIT:

For the curious, you may find some of these bit-twiddling hacks to be of some use.

http://graphics.stanford.edu/~seander/bithacks.html#IntegerL...

Re: We Need Hardware Traps for Integer Overflow

#13

Post by mmastrac » Wed, Jun 04, 2014, 7:34 PM UTC

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

Exactly -- the premise would be that non-overflowing arithmetic would be the "fast path" and overflow would be truly exceptional.

This is similar to null-reference protection in various languages and runtimes, where null dereferences are caught by mapping guard pages at the beginning of memory. Dereferencing a pointer is optimistic and assumes that it will succeed, the same as arithmetic operations would in this proposal.

Re: We Need Hardware Traps for Integer Overflow

#14

Post by rlpb » Wed, Jun 04, 2014, 7:38 PM UTC

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…

> Sure, you'll lose a bit of performance due to checks for overflow...

Which is why the author wants support for integer overflow traps. He even mentions Python, which does what you describe, and suggests that other languages don't do this precisely because of the performance hit for which he's proposing a solution.

Re: We Need Hardware Traps for Integer Overflow

#15

Post by Gracana » Wed, Jun 04, 2014, 7:41 PM UTC

ARMv5 and beyond have saturating arithmetic instructions, which can be pretty handy. It won't cause an exception, but it is at least one way to improve the situation.

and a sticky saturation flag in the status register

Re: We Need Hardware Traps for Integer Overflow

#16

Post by jjoonathan » Wed, Jun 04, 2014, 7:42 PM UTC

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 difficult-to-debug edge cases that slow your code to 1/3 or 1/5 (or 1/100th or 1/1000th) speed. I don't know about you, but I don't consider that "Just Working."

Don't get me wrong, they could be a useful feature, perhaps even one which should be enabled by default in Swift (I'd argue against them, but I wouldn't be entirely unsympathetic to their proponents). However, they aren't for everyone and they don't come cheap.

Re: We Need Hardware Traps for Integer Overflow

#17

Post by pjc50 » Wed, Jun 04, 2014, 7:42 PM UTC

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…

I suspect the best solution would be something like NaN behaviour: carry on with your performance-critical arithmetic and then examine the final result for validity.

Re: We Need Hardware Traps for Integer Overflow

#18

Post by [deleted] » Wed, Jun 04, 2014, 7:44 PM UTC

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

[deleted]

Re: We Need Hardware Traps for Integer Overflow

#19

Post by AnimalMuppet » Wed, Jun 04, 2014, 7:45 PM UTC

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…

You seem to be defining "current languages" to mean "languages that have recently originated" rather than "languages that are currently used". But the languages that are heavily used currently - C, C++, C#, and Java - while they have bignum packages available, the integers within the languages themselves are not arbitrary-precision.

Re: We Need Hardware Traps for Integer Overflow

#20

Post by taeric » Wed, Jun 04, 2014, 7:48 PM UTC

AnimalMuppet wrote: post #19

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…

You seem to be defining "current languages" to mean "languages that have recently originated" rather than "languages that are currently used". But the languages that are heavily used currently - C, C++, C#, and Java - while they have bignum packages available, the integers within the languages themselves are not arbitrary-precision.

It isn't just recent languages that have this. One of the confusions of many folks starting to use most lisps is actually that they typically have very solid number libraries. Such that it is sometimes confusing to see 1/3 as the number you are holding, instead of an approximation.